Propagation time for zero forcing on a graph.

*(English)*Zbl 1246.05056Summary: 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.

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.

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

PDF
BibTeX
XML
Cite

\textit{L. Hogben} et al., Discrete Appl. Math. 160, No. 13--14, 1994--2005 (2012; Zbl 1246.05056)

**OpenURL**

##### References:

[1] | Barioli, F.; Barrett, W.; Butler, S.; Cioabă, S.M.; Cvetković, D.; Fallat, S.M.; Godsil, C.; Haemers, W.; Hogben, L.; Mikkelson, R.; Narayan, S.; Pryporova, O.; Sciriha, I.; So, W.; Stevanović, D.; van der Holst, H.; Vander Meulen, K.; Wangsness, A., Zero forcing sets and the minimum rank of graphs, Linear algebra and its applications, 428, 1628-1648, (2008), AIM Minimum Rank-Special Graphs Work Group · Zbl 1135.05035 |

[2] | Barioli, F.; Barrett, W.; Fallat, S.; Hall, H.T.; Hogben, L.; Shader, B.; van den Driessche, P.; van der Holst, H., Zero forcing parameters and minimum rank problems, Linear algebra and its applications, 433, 401-411, (2010) · Zbl 1209.05139 |

[3] | Burgarth, D.; Giovannetti, V., Full control by locally induced relaxation, Physical review letters, 99, 100-501, (2007) |

[4] | Chilakamarri, K.B.; Dean, N.; Kang, C.X.; Yi, E., Iteration index of a zero forcing set in a graph, Bulletin of the institute of combinatorics and its applications, 64, 57-72, (2012) · Zbl 1251.05149 |

[5] | Edholm, C.J.; Hogben, L.; Huynh, M.; LaGrange, J.; Row, D.D., Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph, Linear algebra and its applications, 436, 12, 4352-4372, (2012) · Zbl 1241.05076 |

[6] | Hogben, L., Minimum rank problems, Linear algebra and its applications, 432, 1961-1974, (2010) · Zbl 1213.05036 |

[7] | Row, D.D., A technique for computing the zero forcing number of a graph with a cut-vertex, Linear algebra and its applications, 436, 12, 4423-4432, (2012) · Zbl 1241.05086 |

[8] | Severini, S., Nondiscriminatory propagation on trees, Journal of physics A, 41, 482002, (2008), (Fast Track Communication) · Zbl 1156.81357 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.