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


05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI


[1] Bollobás, B., Random graphs, (1985), Academic Press New York · Zbl 0567.05042
[2] Erdős, P.; Rényi, A., On random graphs I, Publ. math. debrecen, 6, 290-297, (1959)
[3] Erdős, P.; Rényi, A., On the evolution of random graphs, Publ. math. inst. hungar. acad. sci., 5, 17-61, (1960)
[4] Farley, A.; Hedetniemi, S.; Mitchell, S.; Proskurowski, A., Minimum broadcast number, Discrete math., 25, 189-193, (1979) · Zbl 0404.05038
[5] Ore, O., Graphs and matching theorems, Duke math. J., 2, 625-639, (1955) · Zbl 0068.16301
[6] Weber, K., Problem session, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.