Broadcasting in random graphs

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)149-170
Number of pages22
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - Sep 14 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Broadcasting in random graphs'. Together they form a unique fingerprint.

Cite this