Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S . The minimum cardinality of a total dominating set of G is the total domination number γ t ( G ) of G . It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n  > 10 with minimum degree at least 2, then γ t ( G ) ≤ 4 n /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 4 n /7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n  > 18, then γ t ( G ) ≤ 6 n /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 ) ≤ 6 n /11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009