Pancyclic subgraphs of random graphs
An n-vertex graph is called pancyclic if it contains a cycle of length t for all 3?t?n. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if p>n?1/2, then the random graph G(n, p) a.a.s. satisfies the following property: Every Hamiltonian subgraph of G(n, p) with more than edges is pancyclic. This result is best possible in two ways. First, the range of p is asymptotically tight; second, the proportion of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich et al. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers).  2011 Wiley Periodicals, Inc.
pancyclicity random graph resilience hamiltonicity