Spanning subgraphs of random graphs

Noga Alon, Zoltán Füredi

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


We propose a problem concerning the determination of the threshold function for the edge probability that guarantees, almost surely, the existence of various sparse spanning subgraphs in random graphs. We prove some bounds and demonstrate them in the cases of a d-cube and a two dimensional lattice.

Original languageEnglish (US)
Pages (from-to)91-94
Number of pages4
JournalGraphs and Combinatorics
Issue number1
StatePublished - Mar 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


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

Cite this