Hamiltonicity in random graphs is born resilient

摘要

Let {G(M)}(M >= 0) be the random graph process, where G(0) is the empty graph on n vertices and subsequent graphs in the sequence are obtained by adding a new edge uniformly at random. For each epsilon > 0, we show that, almost surely, any graph G(M) with minimum degree at least 2 is not only Hamiltonian (as shown independently by Bollobas, and Ajtai, Komi& and Szemeredi), but remains Hamiltonian despite the removal of any set of edges, as long as at most (1/2 - epsilon) of the edges incident to each vertex are removed. We say that such a graph is (1/2-epsilon)-resiliently Hamiltonian. Furthermore, for each epsilon > 0, we show that, almost surely, each graph G(M) is not (1/2 + epsilon)-resiliently Hamiltonian. These results strengthen those by Lee and Sudakov on the likely resilience of Hamiltonicity in the binomial random graph.