Michael A. Henning ; Elena Mohr ; Dieter Rautenbach - 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 - https://doi.org/10.23638/DMTCS-21-3-3
On the maximum number of minimum total dominating sets in forestsArticle

Authors: Michael A. Henning ; Elena Mohr ; Dieter Rautenbach

    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.


    Volume: Vol. 21 no. 3
    Section: Graph Theory
    Published on: January 23, 2019
    Accepted on: January 11, 2019
    Submitted on: August 29, 2018
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 1240 times.
    This article's PDF has been downloaded 689 times.