Full Information Model: A Comprehensive Approach to Zero Forcing
Open Access
Author:
Willman, Mason
Area of Honors:
Mathematics
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Thomas Robert Cameron, Thesis Supervisor Wen-Li Wang, Thesis Honors Advisor Joseph Peter Previte, Faculty Reader
Keywords:
graph theory zero forcing integer programming
Abstract:
Zero forcing is a coloring game on a graph where gray vertices can force their white neighbors
based on a color change rule. A set of initial vertices is colored gray and, by a color change rule,
iteratively force neighboring white vertices until only gray vertices are left. A zero forcing set is
the set of initially colored vertices that force the entire graph to become gray. The zero forcing
number is the minimum cardinality of the zero forcing set. Related graph parameters, such as
propagation time and throttling number, provide additional information on the zero forcing game.
Despite this, an integer programming model that can calculate the zero forcing number and all
related graph parameters has yet to be developed. Therefore, we present a full information model
that stores all information regarding the game of zero forcing. Furthermore, we prove that our
model can compute optimal solutions for the zero forcing number, minimum propagation time,
maximum propagation time, and throttling number. We motivate its formulation through analysis
of related integer programming models and numerical experiments showcasing its computational
efficiency on all isomorphic graphs of orders 3-8.
