Premium
Pancyclic subgraphs of random graphs
Author(s) -
Lee Choongbum,
Samotij Wojciech
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20638
Subject(s) - combinatorics , mathematics , pancyclic graph , random graph , vertex (graph theory) , discrete mathematics , graph , pathwidth , line graph
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.