Premium
Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles
Author(s) -
Henning Michael A.,
Yeo Anders
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20345
Subject(s) - combinatorics , mathematics , domination analysis , dominating set , vertex (graph theory) , connectivity , discrete mathematics , graph , bound graph , graph power , line graph
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