Probabilistic Zero Forcing on Random Graphs

Abstract

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ős-Réyni random graph $\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 $\Gnp$ to become blue, and when $\log n/n\ll p\le {\log }^{-O(1)}n$, then with high probability it takes $\Theta (\log (1/p))$ rounds.