Minimal Dominating Sets in a Tree: Counting, Enumeration, and Extremal Results

Abstract

A tree with $n$ vertices has at most $95^{n/13}$ minimal dominating sets. The growth constant $\lambda =\sqrt[13]{95}\approx 1.4194908$ is best possible. It is obtained in a semi-automatic way as a kind of "dominant eigenvalue" of a bilinear operation on sixtuples that is derived from the dynamic-programming recursion for computing the number of minimal dominating sets of a tree. We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions.

41 pages, 21 figures, 4 tables; Python programs for certifying the upper-bound proof of Theorem 1.1 are included in the source bundle