A new lower bound on the total domination number of a graph

  • Majid Henning Henning
  • Michael A. Henning
  • Nader Jafari Rad


A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The total domination number, γt(G), is the minimum cardinality of a total dominating set of G. Chellali and Haynes [J. Combin. Math. Combin. Comput. 58 (2006), 189-193] showed that if T is a nontrivial tree of order n, with ℓ leaves, then γt(T) = ⌈(n - ℓ+2)/2⌉. In this paper, we first characterize all trees T of order n with ℓ leaves satisfying γt(T) = ⌈(n - ℓ+2)=2⌉. We then generalize this result to connected graphs and show that if G is a connected graph of order n ≥ 2 with k ≥ 0 cycles and ℓ leaves, then γ](G) ≥ ⌈(n-ℓ+2)=2⌉ - k. We also characterize the graphs G achieving equality for this new bound.


Journal Identifiers

eISSN: 1727-933X
print ISSN: 1607-3606