论文标题
概率零强迫在网格，常规和超立方体图上
Probabilistic Zero Forcing on Grid, Regular, and Hypercube Graphs
论文作者
论文摘要
概率零效力是图形上的着色过程。在此过程中，一组初始的顶点是彩色的，其余的顶点是彩色的。在每个时间步骤中，蓝色顶点都有将白人邻居迫使蓝色的非零概率。预期的传播时间是每个顶点颜色蓝色所需的预期时间。我们得出了几个图族的预期传播时间的渐近界限。我们证明了$ M \ times n $网格图的$θ（m+n）$的最佳渐近线。我们证明了$ o \ left的上限（\ frac {\ log d} {d} \ cdot n \ right）$ for $ d $ - $ n $ dertices上的grage graphs，并提供了图形结构，并提供了$ω\ left（\ frac {\ frac {\ log log \ log \ log \ log \ log \ log \ log \ log \ log \ d} d} d} \ cdot n \ cdot n \ cdot $ weft的下限。最后，我们证明了$ o（n \ log n）$的渐近上限，用于$ 2^n $顶点的HyperCube图。
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.
