Bounds on the Number of Minimal Forts of Trees

open_access
Open Access
Author:
Li, Kelvin
Area of Honors:
Mathematics
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Thomas Robert Cameron, Thesis Supervisor
Daniel Joseph Galiffa, Thesis Honors Advisor
Keywords:
Zero forcing
Minimal forts
Graph theory
Trees
Abstract:
In discrete mathematics, a graph is a collection of vertices connected to each other by edges. Zero forcing is a coloring game played on graphs. Introduced in 2007 in the study of quantum mechanical systems, zero forcing has since found applications in electrical engineering, logic circuits, theoretical computer science, and networks modeling the spread of information and diseases. In 2008, the zero forcing number of a graph was shown to be an upper bound on the graph's maximum nullity. In 2018, the concept of forts was introduced to provide a set covering characterization of zero forcing sets. Since then, forts have been integrated into integer programming models for zero forcing and have been used to yield bounds on the zero forcing number. In 2025, researchers explored the combinatorial question of how many minimal forts a graph can have. They demonstrated that the number of minimal forts in a graph with an order of at least six is strictly less than Sperner's bound. Moreover, the authors derived an explicit formula for the number of minimal forts in path, cycle, and spider graphs. In this thesis, we demonstrate that any tree with n vertices must have at least n/3 minimal forts. In doing so, we prove several results on the structures and enumeration of minimal forts of trees. In addition, we provide a characterization of trees with exactly $n/3$ minimal forts. We conjecture that the n/3 bound holds for graphs in general, and we prove the inequality for Eulerian graphs.