Four Dominion Growth Regimes in Trees: Forcing, Fibonacci Enumeration, Periodicity, and Stability
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909983254249472 |
|---|---|
| author | Allagan, Julian Gray, Erin Sawyer, Jennifer Morgan, Gabrielle |
| author_facet | Allagan, Julian Gray, Erin Sawyer, Jennifer Morgan, Gabrielle |
| contents | 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) <= 2^{m_1(X)} zeta(T_h), where m_1(X) counts parents that lose exactly one child; in particular, deleting a single leaf preserves the domination number and exactly doubles the dominion. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03485 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Four Dominion Growth Regimes in Trees: Forcing, Fibonacci Enumeration, Periodicity, and Stability Allagan, Julian Gray, Erin Sawyer, Jennifer Morgan, Gabrielle Combinatorics Discrete Mathematics 05C69, 05C05, 05C85, 05A15 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) <= 2^{m_1(X)} zeta(T_h), where m_1(X) counts parents that lose exactly one child; in particular, deleting a single leaf preserves the domination number and exactly doubles the dominion. |
| title | Four Dominion Growth Regimes in Trees: Forcing, Fibonacci Enumeration, Periodicity, and Stability |
| topic | Combinatorics Discrete Mathematics 05C69, 05C05, 05C85, 05A15 |
| url | https://arxiv.org/abs/2601.03485 |