Girth and Total Domination in Graphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


A set S 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. The girth of G is the length of a shortest cycle in G. Let G be a connected graph with minimum degree at least 2, order n and girth g ≥ 3. It was shown in an earlier manuscript (Henning and Yeo in Graphs Combin 24:333-348, 2008) that γ t(G)≤(1/2+1/g)n, and this bound is sharp for cycles of length congruent to two modulo four.In this paper we show that γ t(G)≤n/2+max(1,n/2(g+1)), and this bound is sharp.

Original languageEnglish
Pages (from-to)199-214
Number of pages16
JournalGraphs and Combinatorics
Issue number2
Publication statusPublished - Mar 2012


  • Girth
  • Total domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Girth and Total Domination in Graphs'. Together they form a unique fingerprint.

Cite this