## Optimal and near-optimal broadcast in random graphs.(English)Zbl 0709.05031

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.$$
Reviewer: G.Grimmett

### MSC:

 05C80 Random graphs (graph-theoretic aspects)