




















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。