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

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)

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 languageEnglish
Pages (from-to)55-79
Number of pages25
JournalJournal of Graph Theory
Volume60
Issue number1
DOIs
Publication statusPublished - Jan 2009
Externally publishedYes

Keywords

  • 2-connected
  • Bounds
  • C-free
  • Total domination
  • Transversals

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Total domination in 2-connected graphs and in graphs with no induced 6-cycles'. Together they form a unique fingerprint.

Cite this