Girth and Total Domination in Graphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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
JournalGraphs and Combinatorics
Volume28
Issue number2
Pages (from-to)199-214
ISSN0911-0119
DOIs
Publication statusPublished - 2012
Externally publishedYes

Keywords

  • Girth
  • Total domination

Fingerprint

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

Cite this