Optimization Applied in Graph Theory: Zero-forcing Diameter
Open Access
Author:
Loedding, Jakob
Area of Honors:
Mathematics (Behrend)
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Thomas Robert Cameron, Thesis Supervisor Daniel Joseph Galiffa, Thesis Honors Advisor
Keywords:
Optimization Integer Programming Graph Theory Zero-forcing Zero-forcing Diameter
Abstract:
Zero-forcing is a coloring game on a graph in which an initial set of vertices is colored gray while the remaining vertices are colored white. An iterative color change rule, where some vertices have the ability to force others to change their color to gray, is then applied until no more vertices may be forced. A zero-forcing set of a graph G is defined as an initial set of gray vertices in which the remaining white vertices are forced gray after some number of iterations of the color change rule. The minimum cardinality of a zero-forcing set is defined as the zero-forcing number of G.
In this thesis, we define a new graph parameter called the zero-forcing diameter, which quan- tifies the minimum intersection of two minimum zero-forcing sets of a graph with respect to its zero-forcing number. Furthermore, we present the numerical bounds of the zero-forcing diameter and find its value, with theoretical proof, for specific graph families. We then introduce an integer programming model for calculating the zero-forcing number of a graph. Finally, we build upon this model to develop our own integer program for calculating the zero-forcing diameter of a graph.
