Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651345 | Discrete Mathematics | 2006 | 7 Pages |
Abstract
Pósa proved that a random graph with cnlogncnlogn edges is Hamiltonian with probability tending to 1 if c>3c>3. Korsunov improved this by showing that, if GnGn is a random graph with 12nlogn+12nloglogn+f(n)n edges and f(n)→∞f(n)→∞, then GnGn is Hamiltonian, with probability tending to 1. We shall prove that if a graph GnGn has n vertices and 12nlogn+12nloglogn+cn edges, then it is Hamiltonian with probability PcPc tending to expexp(-2c) as n→∞n→∞.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
János Komlós, Endre Szemerédi,