- This event has passed.
Atlantic Graph Theory Seminar
January 17, 2024 @ 3:30 pm - 4:30 pm
Speaker: Leslie Hogben, Iowa State University
Title: Forts, (fractional) zero forcing, and Cartesian products of graphs
Abstract: Zero forcing is an iterative process that repeatedly applies a rule to change the color of vertices of a graph $G$ from white to blue. The zero forcing number is the minimum number of initially blue vertices that are needed to color all vertices blue through this process. Standard zero forcing was introduced about fifteen years ago in the control of quantum systems and as an upper bound for maximum multiplicity of an eigenvalue (or maximum nullity) among matrices having off-diagonal nonzero pattern described by the edges of the graph $G$, and rediscovered later both as part of power domination and as fast-mixed graph searching.
Whether a set is a zero forcing set can be tested using a certain type of set called a fort, which obstructs zero forcing. The maximum number of disjoint forts (fort number) provides another lower bound for the zero forcing number; results about fort number will be discussed. Forts can be used in integer programs to determine the zero forcing number and fort number. The relaxation of these integer programs leads to dual linear programs that define the fractional zero forcing number, or equivalently, the fractional fort number, and results about these parameters will be discussed.
There is a well-known upper bound for the zero forcing number of a Cartesian product in terms of the zero forcing numbers and orders of the constituent graphs. The question of a lower bound for the zero forcing number of a Cartesian product has recently been studied. It is easy to see that there is a Vizing-like lower bound when the constituent graphs of the Cartesian product both have maximum nullity equal to zero forcing number. Fractional zero forcing and fort number provide additional lower bounds on the the zero forcing number of a Cartesian product in terms of parameters of the constituent graphs.
______________________________________________________________________________
Jeannette Janssen is inviting you to a scheduled Zoom meeting.
Topic: Atlantic Graph Theory Seminar
Join Zoom Meeting
https://us02web.zoom.us/j/86415230827?pwd=QUxLUnlMdWYzL05zSUJ4bnBCOUJnZz09
Meeting ID: 864 1523 0827
Passcode: 835547