Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2605.07298 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909025792163840 |
|---|---|
| author | Dat, Nguyen Hoang Kenter, Franklin H. J. |
| author_facet | Dat, Nguyen Hoang Kenter, Franklin H. J. |
| contents | We solve a conjecture by Becker et al. (arXiv:2404.05963) on the topic of zero forcing regarding the number of minimal forts of a tree. They conjectured and we prove $\mathcal{F}_{T_n} \le \binom{n}{2} \mathcal{F}_{P_n}$ where $\mathcal{F}_{T_n}$ is the maximum number of minimal forts on a tree on $n$ vertices and $\mathcal{F}_{P_n}$ is the number of minimal forts of the path graph on $n$ vertices. Our solution relies on both a computational and theoretical approach. Computationally, we introduce and implement an efficient algorithm to compute the exact number of minimal forts for small trees; this is used to establish the large base case required for our strong induction. Theoretically, we provide an adaptation of the recursion relation that defines $\mathcal{F}_{P_n}$ that applies for all forests; this is used in the induction step to establish the result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07298 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Number of Zero Forcing Minimal Forts on Trees Dat, Nguyen Hoang Kenter, Franklin H. J. Combinatorics We solve a conjecture by Becker et al. (arXiv:2404.05963) on the topic of zero forcing regarding the number of minimal forts of a tree. They conjectured and we prove $\mathcal{F}_{T_n} \le \binom{n}{2} \mathcal{F}_{P_n}$ where $\mathcal{F}_{T_n}$ is the maximum number of minimal forts on a tree on $n$ vertices and $\mathcal{F}_{P_n}$ is the number of minimal forts of the path graph on $n$ vertices. Our solution relies on both a computational and theoretical approach. Computationally, we introduce and implement an efficient algorithm to compute the exact number of minimal forts for small trees; this is used to establish the large base case required for our strong induction. Theoretically, we provide an adaptation of the recursion relation that defines $\mathcal{F}_{P_n}$ that applies for all forests; this is used in the induction step to establish the result. |
| title | On the Number of Zero Forcing Minimal Forts on Trees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.07298 |