Propagation Time of Graphs

Zero forcing (also called graph infection) on a simple, undirected graph G is based on the color-change rule. The color-change rule states that if each vertex of G colored either white or black and vertex v is a black vertex with only one white neighbor u then v forces u to become black.  A zero forcing set is a set of black vertices that can force all vertices of the graph G to turn black under the color-change rule.  A minimum zero forcing set of G is a zero forcing set with the minimum order. Our research focuses on the propagation time of a graph G, pt(G), which is the minimum amount of time that it takes to force all the vertices of G black. The study of propagation time of the graph G is in conjunction with the study of quantum control systems. We introduce examples that demonstrate various features of the propagation time of a graph G such as minimum zero forcing sets having different propagation times. Furthermore, we present bounds on propagation time and results of graphs with propagation time 0, 1, order minus 1 and order minus 2.