Abstract
A set S of vertices in a graph 6 is a total dominating set of 6 if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of 6 is the total domination number Γt(G) of G. It is known [J Graph Theory 35 (2000), 21-45] that if 6 is a connected graph of order n > 10 with minimum degree at least 2, then Γt(G) = 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of An/1 for 2-connected graphs, as well as for connected graphs with no induced 6-cycle. We prove that if 6 is a 2-connected graph of order n > 18, then Γt(G) = 6/7/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6-cycle, then Γt(G) = 6n/11. Both bounds are shown to be sharp.
Original language | English |
---|---|
Pages (from-to) | 55-79 |
Number of pages | 25 |
Journal | Journal of Graph Theory |
Volume | 60 |
Issue number | 1 |
DOIs | |
Publication status | Published - Jan 2009 |
Externally published | Yes |
Keywords
- 2-connected
- Bounds
- C-free
- Total domination
- Transversals
ASJC Scopus subject areas
- Geometry and Topology