Probabilistic Zero Forcing on Random Graphs

Zero forcing is a deterministic iterative graph coloring process in which vertices are colored either blue or white, and in every round, any blue vertices that have a single white neighbor force these white vertices to become blue. Here we study probabilistic zero forcing, where blue vertices have a non-zero probability of forcing each white neighbor to become blue. We explore the propagation time for probabilistic zero forcing on the Erd\H{o}s-R'eyni random graph $\text{Gnp}$ when we start with a single vertex colored blue. We show that when $p={\log }^{-o(1)}n$, then with high probability it takes $(1+o(1)){\log }_2{\log }_{2}n$ rounds for all the vertices in $\text{Gnp}$ to become blue, and when $\log n\mathrm{/}n\ll p\le {\log }^{-O(1)}n$, then with high probability it takes $\mathrm{\Theta }(\log (1\mathrm{/}p))$ rounds.