Spanning subgraphs of random graphs

Noga Alon, Zoltán Füredi

Research output: Contribution to journalArticle

29 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 1 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

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

  • Cite this