Premium
Hamilton cycles in random graphs with minimum degree at least 3: An improved analysis
Author(s) -
Anastos Michael,
Frieze Alan
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20978
Subject(s) - combinatorics , mathematics , random graph , upper and lower bounds , frieze , hamiltonian path , vertex (graph theory) , degree (music) , graph , random regular graph , discrete mathematics , line graph , pathwidth , mathematical analysis , physics , archaeology , acoustics , history
In this paper we consider the existence of Hamilton cycles in the random graph G = G n , m δ ≥ 3 . This random graph is chosen uniformly from n , m δ ≥ 3 , the set of graphs with vertex set [ n ], m edges and minimum degree at least 3. Our ultimate goal is to prove that if m = cn and c > 3/2 is constant then G is Hamiltonian w.h.p. In Frieze (2014), the second author showed that c ≥ 10 is sufficient for this and in this paper we reduce the lower bound to c > 2.662…. This new lower bound is the same lower bound found in Frieze and Pittel (2013) for the expansion of so‐called Pósa sets.