Girth and Total Domination in Graphs

摘要

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 ${gamma_t(G)le(frac{1}{2}+frac{1}{g})n}$ , and this bound is sharp for cycles of length congruent to two modulo four. In this paper we show that ${gamma_t(G)lefrac{n}{2}+max(1,frac{n}{2(g+1)})}$ , and this bound is sharp.