zbMATH — the first resource for mathematics

Iteration index of a zero forcing set in a graph. (English) Zbl 1251.05149
Summary: 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.

05C76 Graph operations (line graphs, products, etc.)
05C38 Paths and cycles
05C90 Applications of graph theory
05C75 Structural characterization of families of graphs
Full Text: arXiv