Broadcasting in random graphs (Q5906597)

The broadcast problem is, given a graph \(G = (V,E)\) and a starting vertex \(v \in V\) that holds a piece \(i\) of information, to distribute \(i\) to all vertices. It is assumed, that at each time step any vertex knowing \(i\) can share it with at most one of its neighbours. A graph has property \(\mathcal B\) if it is possible to distribute a piece of information in \(\lceil \log_ 2 n\rceil\) time steps from everu possible starting vertex. The authors investigate the probability that a random graph \(G_{n,p}\) with edge density \(p\) has property \(\mathcal B\). Improving older upper bounds they show that there exists a constant \(c > 0\) (\(c = 18\) will work) such that if \(p \geq (c \ln n)/n\) then \(G_{n,p}\) has property \(\mathcal B\) with high probability (i.e. with probability \(1 - o(1)\) as \(n \to \infty\)).