Iteration Index of a Zero Forcing Set in a Graph

Abstract

Let each vertex of a graph G = (V(G), E(G)) be given one of two colors, say, "black" and "white". Let Z denote the (initial) set of black vertices of G. The color-change rule converts the color of a vertex from white to black if the white vertex is the only white neighbor of a black vertex. The set Z is said to be a zero forcing set of G if all vertices of G will be turned black after finitely many applications of the color-change rule. The zero forcing number of G is the minimum of |Z| over all zero forcing sets Z \subseteq V (G). Zero forcing parameters have been studied and applied to the minimum rank problem for graphs in numerous articles. We define the iteration index of a zero forcing set of a graph G to be the number of (global) applications of the color-change rule required to turn all vertices of G black; this leads to a new graph invariant, the iteration index of G - it is the minimum of iteration indices of all minimum zero forcing sets of G. We present some basic properties of the iteration index and discuss some preliminary results on certain graphs.

13 pages, 12 figures

References in corpus (1)

• Periods, Lefschetz numbers and entropy for a class of maps on a bouquet of circles

Cited by in corpus (9)

• Propagation time for zero forcing on a graph
• Metric Dimension and Zero Forcing Number of Two Families of Line Graphs
• Bounds on expected propagation time of probabilistic zero forcing
• Using Markov chains to determine expected propagation time for probabilistic zero forcing
• Extremal $k$-forcing sets in oriented graphs
• Connected zero forcing sets and connected propagation time of graphs
• Multi-color forcing in graphs
• On the zero forcing number of corona and lexicographic product of graphs
• A Comparison between the Zero Forcing Number and the Strong Metric Dimension of Graphs