Bounds on expected propagation time of probabilistic zero forcing. (December 2021) - Narayanan, Shyam; Sun, Alec
Abstract: Probabilistic zero forcing is a coloring game played on a graph where the goal is to color every vertex blue starting with an initial blue vertex set. As long as the graph G is connected, if at least 1 vertex is blue then eventually all of the vertices will be colored blue. The most studied parameter in probabilistic zero forcing is the expected propagation time ept ( G ) . We significantly improve on upper bounds for ept ( G ) by Geneson and Hogben and by Chan et al. in terms of a graph's order and radius. We prove the bound ept ( G ) = O r log n r . We also show using Doob's Optional Stopping Theorem that ept ( G ) ≤ n 2 + O ( log n ) . Finally, we derive an explicit lower bound ept ( G ) ≥ log 2 log 2 ( 2 n ) .