2019/09/14 by English, Sean, MacRury, Calum, Pralat, Pawel
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1909.06568
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))log2log2n rounds for all the vertices in \Gnp to become blue, and when log n/n≪ p≤ log-O(1)n, then with high probability it takes Θ(log(1/p)) rounds.