On the maximum number of minimum total dominating sets in forests

Abstract

We propose the conjecture that every tree with order $n$ at least $2$ and total domination number ${\gamma }_t$ has at most ${\left(\frac{n-\frac{{\gamma }_t}{2}}{\frac{{\gamma }_t}{2}}\right)}^{\frac{{\gamma }_t}{2}}$ minimum total dominating sets. As a relaxation of this conjecture, we show that every forest $F$ with order $n$, no isolated vertex, and total domination number ${\gamma }_t$ has at most $\min \left\{{\left(8\sqrt{e}\right)}^{{\gamma }_t}{\left(\frac{n-\frac{{\gamma }_t}{2}}{\frac{{\gamma }_t}{2}}\right)}^{\frac{{\gamma }_t}{2}},(1+\sqrt{2}{)}^{n-{\gamma }_t},1.4865^n\right\}$ minimum total dominating sets.

Cited by in corpus (1)

• Graphs with unique Grundy dominating sets