On the maximum number of minimum dominating sets in forests

Abstract

Fricke, Hedetniemi, Hedetniemi, and Hutson asked whether every tree with domination number $\gamma$ has at most $2^{\gamma }$ minimum dominating sets. Bien gave a counterexample, which allows to construct forests with domination number $\gamma$ and $2.0598^{\gamma }$ minimum dominating sets. We show that every forest with domination number $\gamma$ has at most $2.4606^{\gamma }$ minimum dominating sets, and that every tree with independence number $\alpha$ has at most $2^{\alpha -1}+1$ maximum independent sets.