Günter Rote:

1. The maximum number of minimal dominating sets in a tree

2. 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 λ=¹³√95 ≈ 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. The core of the method tries to enclose a set of sextuples in a six-dimensional geometric body with certain properties, which depend on some putative value of λ. This technique is generalizable to other counting problems, and it raises questions about the "growth" of a general bilinear operation.

We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions.

The upper-bound proof on λ requires a computer calculation, for which a Python program is provided.