























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\times n$ grid graphs. We prove an upper bound of $O \left(\frac{\log d}{d} \cdot n \right)$ for $d$-regular graphs on $n$ vertices and provide a graph construction that exhibits a lower bound of $Ω\left(\frac{\log \log d}{d} \cdot n \right)$. Finally, we prove an asymptotic upper bound of $O(n \log n)$ for hypercube graphs on $2^n$ vertices.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。