On the minimal forts of trees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910048947535872 |
|---|---|
| author | Cameron, Thomas R. Li, Kelvin |
| author_facet | Cameron, Thomas R. Li, Kelvin |
| contents | In 2018, the concept of a fort in graph theory was introduced as a non-empty subset of vertices satisfying the condition that no vertex outside the set has exactly one neighbor in the set. Since then, forts have played a significant role in characterizing zero forcing sets, modeling the zero forcing number as an integer program, and generating lower bounds for the zero forcing number of Cartesian products. Recent research has focused on the number of minimal forts, defined as those for which no proper subset is a fort. Notably, it has been established that the number of minimal forts in any graph is strictly less than Sperner's bound, a famous bound due to Emanuel Sperner (1928) on the size of a collection of subsets where no subset contains another. Moreover, lower bounds on the number of minimal forts for several families of graphs were established, and it was shown that certain families have an exponential number of minimal forts. In this article, we provide a combinatorial-cut characterization of the minimal forts in trees. Using this characterization, we derive an upper bound on the cardinality of minimal forts and a lower bound on the number of minimal forts in trees. We also characterize the trees that attain this lower bound through a four-part equivalence theorem that provides a connection to other graph parameters, such as star centers, the fort number, and the zero forcing number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_12874 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the minimal forts of trees Cameron, Thomas R. Li, Kelvin Combinatorics 05C05, 05C15, 05C30, 05C57 In 2018, the concept of a fort in graph theory was introduced as a non-empty subset of vertices satisfying the condition that no vertex outside the set has exactly one neighbor in the set. Since then, forts have played a significant role in characterizing zero forcing sets, modeling the zero forcing number as an integer program, and generating lower bounds for the zero forcing number of Cartesian products. Recent research has focused on the number of minimal forts, defined as those for which no proper subset is a fort. Notably, it has been established that the number of minimal forts in any graph is strictly less than Sperner's bound, a famous bound due to Emanuel Sperner (1928) on the size of a collection of subsets where no subset contains another. Moreover, lower bounds on the number of minimal forts for several families of graphs were established, and it was shown that certain families have an exponential number of minimal forts. In this article, we provide a combinatorial-cut characterization of the minimal forts in trees. Using this characterization, we derive an upper bound on the cardinality of minimal forts and a lower bound on the number of minimal forts in trees. We also characterize the trees that attain this lower bound through a four-part equivalence theorem that provides a connection to other graph parameters, such as star centers, the fort number, and the zero forcing number. |
| title | On the minimal forts of trees |
| topic | Combinatorics 05C05, 05C15, 05C30, 05C57 |
| url | https://arxiv.org/abs/2512.12874 |