2025/12/01 by Mehdi Jelassi, Jelassi, Mehdi, Julien Portier +3
Mathematics · #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2512.01429
We study the probabilistic zero forcing process, a probabilistic variant of the classical zero forcing process. We show that for every connected graph G on n vertices, there exists an initial set consisting of a single vertex such that the expected propagation time is n/2 + O(1). This result is tight and confirms a conjecture posed by Narayanan and Sun. Additionally, we show tight bounds on the probabilistic throttling number, which captures the trade-off between the size of the initial set and the speed of propagation. Namely, we show that for every connected graph G on n vertices, there exists an initial set consisting of O(√(n)) vertices such that the expected propagation time is O(√(n)). This improves upon previous results by Geneson and Hogben, and confirms another conjecture by Narayanan and Sun.