Date of Award
2024
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Applied Mathematics
Committee Chair
Guo-Hui Zhang
Committee Member
Dongsheng Wu
Committee Member
Huaming Zhang
Committee Member
John Mayer
Committee Member
Kyungyong Lee
Research Advisor
Guo-Hui Zhang
Subject(s)
Graph theory, Combinatorial analysis, Mathematics--Charts Diagrams etc.
Abstract
The zero forcing number is a graph parameter that was introduced in 2008 to study the minimum rank of matrices. Since then, it has garnered attention due to its applications in search problems, control theory, and power grid monitoring as well as a subject of theoretical interest in its own right. We denote the zero forcing number of a graph Z(G). Consider a subset Z of the vertex set of a simple graph G and color the vertices in Z pink. If a pink vertex has exactly one uncolored neighbor, then that pink vertex forces its sole uncolored neighbor to turn pink. If, through repeated forces, every vertex of G is eventually colored pink, then we call Z a Zero Forcing Set of G. Z(G) is the smallest cardinality of a zero forcing set of G. The girth of a graph is the order of the smallest cycle in G. In this dissertation we will study using the girth and minimum degree of a graph G to bound Z(G) from below. First, we discuss a lower bound first conjectured by Davila and Kenter and proven . We then characterize the girth and minimum degree of graphs that achieve this bound. Next, we prove two improved lower bounds for graphs with girth five and six. Additionally, we discuss the connections between the zero forcing number and the well studied theory of cages. We then use the Z-Grundy domination number and a well known rank result from KCJ Smith to find the value of several small Levi graphs of projective planes as well as establish general upper and lower bounds for the Levi graphs of projective planes.
Recommended Citation
Gant, Paige, "The zero forcing number of graphs with prescribed girth" (2024). Dissertations. 435.
https://louis.uah.edu/uah-dissertations/435
Comments
Submitted in ... the Joint Applied Mathematics Program.