ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Combinatorial Matrix Theory

Tue 17:00–17:30, Room AV 04.17
Zero forcing propagation time on oriented graphs
Brenda K. Kroschel (Univ. of St. Thomas)
Joint work with Adam Berliner (St. Olaf); Chassidy Bozeman (Iowa State University); Steve Butler (Iowa State University); Minnie Catral (Xavier University); Leslie Hogben (Iowa State University); Jephian Chin-Hung Lin (Iowa State University); Nathan Warnberg (Univer

Zero forcing is an iterative coloring procedure on a graph, $G$, that starts by initially coloring vertices white and blue and then repeatedly applies the following rule: if any blue vertex has a unique (out-)neighbor that is colored white, then that neighbor is forced to change color from white to blue. An initial set of blue vertices that can force the entire graph to blue is called a zero forcing set. The minimum cardinality of a zero forcing set on a graph, $G$, is the zero forcing number, $Z(G)$. This graph parameter was first introduced by the AIM Special Graphs Work Group in 2008 for undirected graphs and later extended to simple digraphs. It is of interest because there is a relationship between the zero forcing number and the geometric multiplicity of the eigenvalue $0$ for a matrix associated with the graph. In this talk the minimum number of iterations needed for this color change rule to color all of the vertices blue, also known as the propagation time, for oriented graphs are considered. For non-oriented graphs, some results on the zero-forcing number as well as the propagation time of circulant graphs are discussed.