Total domination in graphs with given girth

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)


A set 5 of vertices in a graph G without isolated vertices 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. In this paper, we establish an upper bound on the total domination number of a graph with minimum degree at least two in terms of its order and girth. We prove that if G is a graph of order n with minimum degree at least two and girth g. then γt(G) ≤ n/2 + n/g, and this bound is sharp. Our proof is an interplay between graph theory and transversals in hypergraphs.

Original languageEnglish
Pages (from-to)333-348
Number of pages16
JournalGraphs and Combinatorics
Issue number4
Publication statusPublished - Sept 2008
Externally publishedYes


  • Girth
  • Graphs
  • Hypergraphs
  • Total domination number
  • Transversals

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Total domination in graphs with given girth'. Together they form a unique fingerprint.

Cite this