On the Number of Minimum Total Dominating Sets in Trees

Abstract— The minimum total dominating set (MTDS) of a graph is a vertex subset \( D \) of minimum cardinality such that every vertex of the graph is adjacent to at least one vertex of \( D \) . In this paper we obtain a sharp upper bound for the number of MTDSs in the class of \( n \) -vertex 2-caterpillars. We also show that for all \( n \geq 1 \) every \( n \) -vertex tree has less than \( (\sqrt {2})^n \) MTDSs.