Alvarado et al.'s conjecture on minimum dominating sets in trees

From papers

Let TT be a tree with domination number γ\gamma, and let the number of its minimum dominating sets be measured as a function of γ\gamma. Alvarado et al.'s conjecture. A tree with domination number γ\gamma has O(γ2γ\lngamma)O(\frac{\gamma2^\gamma}{\lngamma}) minimum dominating sets. The conjecture was disproved by the explicit construction in this paper, which gives trees with more than 255γ\frac{2}{5}\sqrt{5}^{\gamma} minimum dominating sets; thus the claimed asymptotic upper bound is false.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Jan Petr, Julien Portier and Leo Versteegen, “On the number of minimum dominating sets and total dominating sets in forests”, arXiv:2206.13182 (2022).

Solutions 0

No solutions have been posted yet.