Article ID Journal Published Year Pages File Type
4651345 Discrete Mathematics 2006 7 Pages PDF
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
, ,