We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Girth and Total Domination in Graphs.
- Authors
Henning, Michael; Yeo, Anders
- 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 γ( 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, ) 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)\le\frac{n}{2}+\max(1,\frac{n}{2(g+1)})}$$, and this bound is sharp.
- Subjects
DOMINATING set; GRAPH theory; SET theory; GRAPH connectivity; ALGEBRAIC cycles
- Publication
Graphs & Combinatorics, 2012, Vol 28, Issue 2, p199
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-011-1033-2