Propagation time for zero forcing on a graph

Thumbnail Image
Huynh, My
Kingsley, Nicole
Meyer, Sarah
Walker, Shanise
Young, Michael
Major Professor
Committee Member
Journal Title
Journal ISSN
Volume Title
Hogben, Leslie
Associate Dean
Research Projects
Organizational Units
Organizational Unit
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of

Zero forcing (also called graph infection) on a simple, undirected graph G is based on the color-change rule: if each vertex of G is colored either white or black, and vertex v is a black vertex with only one white neighbor w, then change the color of w to black. A minimum zero forcing set is a set of black vertices of minimum cardinality that can color the entire graph black using the color change rule. The propagation time of a zero forcing set B of graph G is the minimum number of steps that it takes to force all the vertices of G black, starting with the vertices in B black and performing independent forces simultaneously. The minimum and maximum propagation times of a graph are taken over all minimum zero forcing sets of the graph. It is shown that a connected graph of order at least two has more than one minimum zero forcing set realizing minimum propagation time. Graphs G having extreme minimum propagation times |G|−1, |G|−2, and 0 are characterized, and results regarding graphs having minimum propagation time 1 are established. It is shown that the diameter is an upper bound for maximum propagation time for a tree, but in general propagation time and diameter of a graph are not comparable.


This is a manuscript of an article from Discrete Applied Mathematics 26 (2012): 1994, doi:10.1016/j.dam.2012.04.003. Posted with permission.

Sun Jan 01 00:00:00 UTC 2012