We show that the probability that a random graph $G\sim G(n,p)$ contains no Hamilton cycle is $(1+o(1))Pr(\delta (G) < 2)$ for all values of $p = p(n)$. We also prove an analogous result for perfect matchings.
@article{10_37236_8339,
author = {Yahav Alon and Michael Krivelevich},
title = {Random graph's {Hamiltonicity} is strongly tied to its minimum degree},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {1},
doi = {10.37236/8339},
zbl = {1431.05136},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8339/}
}
TY - JOUR
AU - Yahav Alon
AU - Michael Krivelevich
TI - Random graph's Hamiltonicity is strongly tied to its minimum degree
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/8339/
DO - 10.37236/8339
ID - 10_37236_8339
ER -
%0 Journal Article
%A Yahav Alon
%A Michael Krivelevich
%T Random graph's Hamiltonicity is strongly tied to its minimum degree
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8339/
%R 10.37236/8339
%F 10_37236_8339
Yahav Alon; Michael Krivelevich. Random graph's Hamiltonicity is strongly tied to its minimum degree. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/8339
