Authors: Alan Frieze Michael Krivelevich
Publish Date: 2008/08/14
Volume: 166, Issue: 1, Pages: 221-234
Abstract
We study two problems related to the existence of Hamilton cycles in random graphs The first question relates to the number of edge disjoint Hamilton cycles that the random graph G np contains δG/2 is an upper bound and we show that if p ≤ 1 + o1 ln n/n then this upper bound is tight whp The second question relates to how many edges can be adversarially removed from G np without destroying Hamiltonicity We show that if p ≥ K ln n/n then there exists a constant α 0 such that whp G − H is Hamiltonian for all choices of H as an nvertex graph with maximum degree ΔH ≤ αK ln n
Keywords: