Random Graph's Hamiltonicity is Strongly Tied to its Minimum Degree

  • Yahav Alon
  • Michael Krivelevich
DOI: https://doi.org/10.37236/8339

Abstract

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.

Published
2020-01-24
Issue
Volume 27, Issue 1 (2020)
Article Number
P1.30