Lecture by Günter Rote (Freie Universität Berlin): The maximum number of minimal dominating sets in a tree
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 sextuples 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 interesting 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.
Time & Location
Jan 24, 2022 | 02:15 PM
Online via Zoom
participate via Zoom