Broadcasting in random graphs

One of the major problems that have arisen in communication networks is that of broadcasting, namely the dissemination of a message possessed initially by a given vertex to all the vertices of a network. It is assumed that at any time step a given vertex can transmit to or receive from some other vertex exactly one message. We are interested in the minimum time needed to broadcast a message from one vertex to all the vertices of G_n,p random graphs. We are also interested in the broadcast number of such graphs. The problem of broadcasting in random graphs was studied by Scheinerman and Wierman in (1989), where they proved that it was possible to perform, with high probability, near-optimal broadcast in G_n,p random graphs for p=ω_nlog n n with ω_n→∞ as n→∞. They also proved that, for a given algorithm, it was possible, with probability, to optimally broadcast a message from any given vertex to all the vertices of G_n,p random graphs with edge probability p=c log² n n, for a properly chosen constant c, in exactly ⌈lgn⌉ time steps. We prove here results related to two conjectures posed by them regarding the optimality of the edge probabilities they used in their paper.