On the maximum number of minimum total dominating sets in forests
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2019-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/4787/pdf |
| Summary: | 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. |
|---|---|
| ISSN: | 1365-8050 |