Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles |
| |
Authors: | Michael A. Henning Anders Yeo |
| |
Affiliation: | 1. School of Mathematical Sciences, University of Kwazulu‐Natal, Pietermaritzburg 3209, South Africa;2. Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 OEX, UK |
| |
Abstract: | 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) ≤ 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 4n/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) ≤ 6n/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. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009 |
| |
Keywords: | bounds 2‐connected C6‐free total domination transversals |
|
|