中文

Operations Research Transactions >

2017 , Vol. 21 >Issue 1: 125 - 128

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2017.01.013

A note on total domination in 5-regular graphs

Expand
  • 1. Department of Mathematics,   Shanghai University,  Shanghai 200444,  China; 2. School of Management,   Shanghai University, Shanghai 200444,  China

Received date: 2016-07-24

  Online published: 2017-03-15

Fold

Abstract

Let G be a graph without isolated vertices. A total dominating set of G is a subset S of V(G) such that every vertex of G is adjacent to a vertex in S. The minimum cardinality of a total dominating set of G is denoted by \gamma_t(G). Recently, Thomass\'e and Yeo showed that \gamma_t(G)\le 17n/44 for a connected graph G of order n with minimum degree at least five. In this paper we prove that \gamma_t(G)\le 106n/275 for a 5-regular graph G of order n, which improves sightly the bound of Thomass\'e and Yeo.

Key words： total domination; regular graph; hypergraph; bound

Cite this article

LI Shan, SHAN Erfang, ZHANG Lin . A note on total domination in 5-regular graphs[J]. Operations Research Transactions, 2017 , 21(1) : 125 -128 . DOI: 10.15960/j.cnki.issn.1007-6093.2017.01.013

References

[1] Haynes T W, Hedetniemi S T, Slater P J. Fundamentals of Domination in Graphs [M]. New York: Marcel Dekker, 1998.
[2] Haynes T W, Hedetniemi S T, Slater P J. Domination in Graphs: Advanced Topics [M]. New York: Marcel Dekker, 1998.
[3] Cockayne E, Dawes R, Hedetniemi S. Total domination in graphs [J]. Networks, 1980, 10: 211-219.
[4] Henning M A, Yeo A.  Total Domination in Graphs [M]. New York: Springer, 2013.
[5] Dorfling M, Henning M A. Transversals in 5-uniform hypergraphs and total domination in graphs with minimum degree five [J]. Quaestiones Mathematicae, 2015, 38(2): 155-180.
[6] Brooks R L. On colouring the nodes of a network [J]. Mathematical Proceedings of the Cambridge Philosophical Society, 1941, 37: 194-197.
[7] Chv\'atal V, McDiarmid C. Small transversals in hypergraphs [J]. Combinatorica, 1992, 12: 19-26.
[8] Thomass\'e S, Yeo A. Total domination of graphs and small transversals of hypergraphs [J]. Combinatorica, 2007, 27: 473-487.
Options
Outlines

/

〈 〉