Probabilistic zero forcing on random graphs (Q2225411): Difference between revisions

This paper studies probabilistic zero forcing on ER random graphs. Given a graph \(G\) and a set of blue vertices \(Z\) in \(G\), the process of zero forcing involves a coloring process in which a blue vertex \(u\) formes a white vertex \(v\) to become blue if \(v\) is the only neighbor of \(u\) that is white. In probabilistic zero forcing of forcing to become blue is given by \(|N(u)\cap Z|/d_u\), where \(d_u\) is the degree of \(u\) and \(N(u)\) is the neighborhood. Let \(\operatorname{pt}(G,Z)\) be the propagation time of a probabilistic zero forcing with initial blue set \(Z\). If \(pn\gg \ln n\) then for any vertex \(v\) in the random graph \(G(n,p)\), it is shown that almost surely \(\operatorname{pt}(G(n,p),v)\le(1+o(1))(\log_2\log_2 n+\log_3(1/p))\) and \(\operatorname{pt}(G(n,p),v)\ge(1+o(1))\max(\log_2\log_2 n, \log_4(1/p))\).