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 Gn,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 Gn,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 Gn,p random graphs with edge probability p=c log2 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.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics