Alvarado et al.'s conjecture on minimum dominating sets in trees
Let be a tree with domination number , and let the number of its minimum dominating sets be measured as a function of . Alvarado et al.'s conjecture. A tree with domination number has minimum dominating sets. The conjecture was disproved by the explicit construction in this paper, which gives trees with more than minimum dominating sets; thus the claimed asymptotic upper bound is false.
References
- Jan Petr, Julien Portier and Leo Versteegen, “On the number of minimum dominating sets and total dominating sets in forests”, arXiv:2206.13182 (2022).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.