Bounds on expected propagation time of probabilistic zero forcing
arXiv:1909.04482 · doi:10.1016/j.ejc.2021.103405
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 is connected, if at least one 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 starting from a given vertex of In this paper we improve on upper bounds for the expected propagation time by Geneson and Hogben and Chan et al. in terms of a graph's order and radius. In particular, for a connected graph of order and radius we prove the bound We also show using Doob's Optional Stopping Theorem and a combinatorial object known as a cornerstone that Finally, we derive an explicit lower bound
16 pages