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 γ _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.