On the Number of Minimum Total Dominating Sets in Trees
Dmitrii Sergeevich Taletskii · Journal of Applied and Industrial Mathematics · 2023
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.