Limit distribution for the existence of hamiltonian cycles in a random graph

János Komlós, Endre Szemerédi

Research output: Contribution to journalArticle

141 Scopus citations

Abstract

Pósa proved that a random graph with cn log n edges is Hamiltonian with probability tending to 1 if c > 3. Korsunov improved this by showing that, if Gn is a random graph with 1 2nlogn+ 1 2nlogn+f(n)n edges and f(n>)→∞, then Gn is Hamiltonian, with probability tending to 1. We shall prove that if a graph Gn has n vertices and 1 2nlogn+ 1 2nlogn+cn edges, then it is Hamiltonian with probability Pc tending to exp exp(-2c) as n→∞.

Original languageEnglish (US)
Pages (from-to)55-63
Number of pages9
JournalDiscrete Mathematics
Volume43
Issue number1
DOIs
StatePublished - 1983

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this