Propagation time for zero forcing on a graph

Abstract

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.

Poster Presentation Presented at USTARS 2012

References in corpus (3)

• Full control by locally induced relaxation
• Nondiscriminatory Propagation on Trees
• Iteration Index of a Zero Forcing Set in a Graph

Cited by in corpus (25)

• Strong Structural Controllability of Networks under Time-Invariant and Time-Varying Topological Perturbations
• A Comparison between the Metric Dimension and Zero Forcing Number of Trees and Unicyclic Graphs
• Throttling positive semidefinite zero forcing propagation time on graphs
• The zero forcing polynomial of a graph
• Upper bounds on the k-forcing number of a graph
• Fractional Zero Forcing via Three-color Forcing Games
• Metric Dimension and Zero Forcing Number of Two Families of Line Graphs
• On Zero Forcing Number of Graphs and Their Complements
• Minimum rank and zero forcing number for butterfly networks
• Bounds on expected propagation time of probabilistic zero forcing
• Using Markov chains to determine expected propagation time for probabilistic zero forcing
• Power propagation time and lower bounds for power domination number
• On the power domination number of de Bruijn and Kautz digraphs
• Total Forcing Sets in Trees
• Graphs with Extremal Connected Forcing Numbers
• Probabilistic Zero Forcing on Grid, Regular, and Hypercube Graphs
• Zero Forcing Number of Random Regular Graphs
• Product throttling for power domination
• Proof of a conjecture on the zero forcing number of a graph
• Throttling for standard zero forcing on directed graphs
• The zero forcing numbers and propagation times of gear graphs and helm graphs
• Properties of a $q$-analogue of zero forcing
• Propagation time for weighted zero forcing
• A Comparison between the Zero Forcing Number and the Strong Metric Dimension of Graphs
• Edge Forcing in Butterfly Networks