2020/10/22 by David L. Hu, Hu, David, Alec Sun +1
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2010.12343
openalex publication_date 2020/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Probabilistic zero-forcing is a coloring process on a graph. In this process, an initial set of vertices is colored blue, and the remaining vertices are colored white. At each time step, blue vertices have a non-zero probability of forcing white neighbors to blue. The expected propagation time is the expected amount of time needed for every vertex to be colored blue. We derive asymptotic bounds for the expected propagation time of several families of graphs. We prove the optimal asymptotic bound of Θ(m+n) for m× n grid graphs. We prove an upper bound of O ((log d)/(d) ⋅ n ) for d-regular graphs on n vertices and provide a graph construction that exhibits a lower bound of Ω((log log d)/(d) ⋅ n ). Finally, we prove an asymptotic upper bound of O(n log n) for hypercube graphs on 2n vertices.