Trees having many minimal dominating sets

We disprove a conjecture by Skupień that every tree of order n   has at most 2n/22n/2 minimal dominating sets. We construct a family of trees of both parities of the order for which the number of minimal dominating sets exceeds 1.4167n1.4167n. We also provide an algorithm for listing all minimal dominating sets of a tree in time O(1.4656n)O(1.4656n). This implies that every tree has at most 1.4656n1.4656n minimal dominating sets.

► We disprove a conjecture that every tree of order n   has at most 2n/22n/2 minimal dominating sets. ► We establish 1.4167n1.4167n to be a lower bound on the running time of an algorithm for listing all m-d sets of a given tree. ► We provide an algorithm for listing all m-d sets of a tree of order n   in time O(1.4656n)O(1.4656n). ► The above implies that every tree has at most 1.4656n1.4656n minimal dominating sets.