Pancyclic subgraphs of random graphs

Details Pancyclic subgraphs of random graphs Pancyclic subgraphs of random graphs

2010-05-31

arxiv.org/abs/1005.5716v2

Mathematics

Combinatorics

19 pages, 4 figures

Scientific paper

An $n$-vertex graph is called pancyclic if it contains a cycle of length $t$ for all $3 \leq t \leq n$. In this paper, we study pancyclicity of random graphs in the context of resilience, and prove that if $p \gg 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 $(1/2 + o(1)){n \choose 2}p$ edges is pancyclic. This result is best possible in two ways. First, the range of $p$ is asymptotically tight; second, the proportion 1/2 of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich, Lee, and Sudakov. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers).

Affiliated with

Also associated with

No associations

Rating

Pancyclic subgraphs of random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pancyclic subgraphs of random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pancyclic subgraphs of random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-628043