A Note on the Total Domination Number of a Tree

Mustapha Chellali1, Teresa W. Haynes2
1Department of Mathematics, University of Blida. B.P. 270, Blida, Algeria.
2Department of Mathematics, East Tennessee State University Johnson City, TN 37614 USA

Abstract

A set \( S \) of vertices is a total dominating set of a graph \( G \) if every vertex of \( G \) is adjacent to some vertex in \( S \). The minimum cardinality of a total dominating set is the total domination number \( \gamma_t(G) \). We show that for a nontrivial tree \( T \) of order \( n \) and with \( \ell \) leaves, \( \gamma_t(T) \geqslant \frac{n + 2 – \ell}{2} \), and we characterize the trees attaining this lower bound.