Discrete Mathematics & Theoretical Computer Science |

4787

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: arXiv.org:1804.10476

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

This page has been seen 1119 times.

This article's PDF has been downloaded 628 times.