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 |
| _version_ | 1827323739001323520 |
|---|---|
| author | Michael A. Henning Elena Mohr Dieter Rautenbach |
| author_facet | Michael A. Henning Elena Mohr Dieter Rautenbach |
| author_sort | Michael A. Henning |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:57:17Z |
| format | Article |
| id | doaj.art-4382b087fc17461dbbe325fd482c3b81 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:17Z |
| publishDate | 2019-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-4382b087fc17461dbbe325fd482c3b812024-03-07T15:39:17ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-01-01Vol. 21 no. 3Graph Theory10.23638/DMTCS-21-3-34787On the maximum number of minimum total dominating sets in forestsMichael A. HenningElena MohrDieter RautenbachWe 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.https://dmtcs.episciences.org/4787/pdfmathematics - combinatorics |
| spellingShingle | Michael A. Henning Elena Mohr Dieter Rautenbach On the maximum number of minimum total dominating sets in forests Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | On the maximum number of minimum total dominating sets in forests |
| title_full | On the maximum number of minimum total dominating sets in forests |
| title_fullStr | On the maximum number of minimum total dominating sets in forests |
| title_full_unstemmed | On the maximum number of minimum total dominating sets in forests |
| title_short | On the maximum number of minimum total dominating sets in forests |
| title_sort | on the maximum number of minimum total dominating sets in forests |
| topic | mathematics - combinatorics |
| url | https://dmtcs.episciences.org/4787/pdf |
| work_keys_str_mv | AT michaelahenning onthemaximumnumberofminimumtotaldominatingsetsinforests AT elenamohr onthemaximumnumberofminimumtotaldominatingsetsinforests AT dieterrautenbach onthemaximumnumberofminimumtotaldominatingsetsinforests |