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

2019/03/11 by Rote, Günter
#05C30 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1903.04517

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. We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions.

Related

• Bounding the number of (σ,ρ)-dominating sets in trees, forests and graphs of bounded pathwidth
• The growth rate over trees of any family of set defined by a monadic second order formula is semi-computable
• On the maximum number of minimum dominating sets in forests
• Linear algorithms on Steiner domination of trees
• Laplacian Spectrum and Domination in Trees