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

Scheinerman, Edward R.; Wierman, John C.

Discrete Appl. Math. 25, No. 3, 289-297 (1989).

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)

Keywords:

random graph; broadcast number

References:

[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, ()