Bounds on expected propagation time of probabilistic zero forcing. (December 2021)

• Record Type: Journal Article
• Authors: Narayanan, Shyam; Sun, Alec
• Is Part Of: European journal of combinatorics. Volume 98(2021)
• Publication Date: 2021-12
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103405
• Languages: English
• ISSNs: 0195-6698

Abstract

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 ) .