Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles
- 19 July 2008
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 60 (1) , 55-79
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, 2009Keywords
This publication has 14 references indexed in Scilit:
- Restricted domination parameters in graphsJournal of Combinatorial Optimization, 2006
- Restricted total domination in graphsDiscrete Mathematics, 2004
- Some remarks on dominationJournal of Graph Theory, 2004
- Restricted domination in graphsDiscrete Mathematics, 2002
- Graphs with large total domination numberJournal of Graph Theory, 2000
- Total domination in graphs with minimum degree threeJournal of Graph Theory, 2000
- Bounds related to domination in graphs with minimum degree twoJournal of Graph Theory, 1997
- Small transversals in hypergraphsCombinatorica, 1992
- Transversal numbers of uniform hypergraphsGraphs and Combinatorics, 1990
- Total domination in graphsNetworks, 1980