Four Dominion Growth Regimes in Trees: Forcing, Fibonacci Enumeration, Periodicity, and Stability
Abstract
We study the dominion zeta(G), defined as the number of minimum dominating sets of a graph G, and analyze how local forcing and boundary effects control the flexibility of optimal domination in trees. For path-based pendant constructions, we identify a sharp forcing threshold: attaching a single pendant vertex to each path vertex yields complete independence with zeta = 2^gamma, whereas attaching two or more pendant vertices forces a unique minimum dominating set. Between these extremes, sparse pendant patterns produce intermediate behavior: removing endpoint pendants gives zeta = 2^(gamma - 2), while alternating pendant attachments induce Fibonacci growth zeta asymptotic to phi^gamma, where phi is the golden ratio. For complete binary trees T_h, we establish a rigid period-3 law zeta(T_h) in {1, 3} despite exponential growth in |V(T_h)|. We further prove a sharp stability bound under leaf deletions, zeta(T_h - X)
Fields of Study & Subjects
Advanced Graph Theory Research
Graph theory and applications
Stochastic processes and statistical mechanics
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 7 January 2026
- Document type
- Preprint