Optimal and near-optimal broadcast in random graphs (Q921019)

One vertex of a graph has a message which it wishes to transmit to all other vertices. At each discrete time unit, a vertex can send the message to one of its neighbours. Writing \(b_ v\) for the minimum time necessary for a message originating at v to reach all other vertices, the broadcast number \(b=\max_{v}b_ v\). Call a graph on n vertices broadcast optimal if \(b=\lceil \log_ 2n\rceil\). Consider the graph G on n vertices, each pair of which is joined by an edge with probability \(p_ n\). It is shown that, with large probability, G is broadcast optimal if \(p_ n=c(\log n)^ 2n\) where c is sufficiently large, and `near optimal' if \(p_ n=w_ n\) log n/n where \(w_ n\to \infty\) and \(n\to \infty\); `near optimal' means that \(b=\lceil \log_ 2n\rceil (1+o(1))\) as \(n\to \infty\). Certain conjectures are made for the case \(p_ n=\alpha\log n/n.\)