A Note on the Total Domination Number of a Tree

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)⩾\frac{n+2–\ell }{2}$, and we characterize the trees attaining this lower bound.