Günter Rote:

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

In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA19), San Diego, January 2019, Editor: Timothy Chan. pp. 1201–1214. doi:10.1137/1.9781611975482.73→BibTeX

2. Minimal dominating sets in a tree: counting, enumeration, and extremal results

Manuscript, March 2019, submitted for publication. arXiv:1903.04517 [cs.DM].  →BibTeX


A tree with n vertices has at most 95n/13 minimal dominating sets. The growth constant λ=13√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.

  pdf file
other papers about this subject
Last update: March 22, 2019.