## 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
### Abstract

A tree with `n` vertices has at most
95^{n/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.

Last update: March 22, 2019.