Pancyclic subgraphs of random graphs |
| |
Authors: | Choongbum Lee Wojciech Samotij |
| |
Affiliation: | 1. Department of Mathematics, Ucla Los Angeles, , California, 90095;2. Department of Mathematics, University of Illinois Urbana, , Illinois, 61801 |
| |
Abstract: | 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. |
| |
Keywords: | random graph pancyclicity resilience Hamiltonicity |
|
|