Henning, Michael A. and Mohr, Elena and Rautenbach, Dieter - On the maximum number of minimum total dominating sets in forests

dmtcs:4787 - Discrete Mathematics & Theoretical Computer Science, January 23, 2019, Vol. 21 no. 3
On the maximum number of minimum total dominating sets in forests

Authors: Henning, Michael A. and Mohr, Elena and Rautenbach, Dieter

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.


Source : oai:arXiv.org:1804.10476
Volume: Vol. 21 no. 3
Section: Graph Theory
Published on: January 23, 2019
Submitted on: August 29, 2018
Keywords: Mathematics - Combinatorics


Share