Resilient pancyclicity of random and pseudo-random graphs

Details Resilient pancyclicity of random and pseudo-random graphs Resilient pancyclicity of random and pseudo-random graphs

2009-06-07

arxiv.org/abs/0906.1397v1

Mathematics

Combinatorics

17 pages

Scientific paper

A graph $G$ on $n$ vertices is \textit{pancyclic} if it contains cycles of length $t$ for all $3 \leq t \leq n$. In this paper we prove that for any fixed $\epsilon>0$, the random graph $G(n,p)$ with $p(n)\gg n^{-1/2}$ asymptotically almost surely has the following resilience property. If $H$ is a subgraph of $G$ with maximum degree at most $(1/2 - \epsilon)np$ then $G-H$ is pancyclic. In fact, we prove a more general result which says that if $p \gg n^{-1+1/(l-1)}$ for some integer $l \geq 3$ then for any $\epsilon>0$, asymptotically almost surely every subgraph of $G(n,p)$ with minimum degree greater than $(1/2+\epsilon)np$ contains cycles of length $t$ for all $l \leq t \leq n$. These results are tight in two ways. First, the condition on $p$ essentially cannot be relaxed. Second, it is impossible to improve the constant 1/2 in the assumption for the minimum degree. We also prove corresponding results for pseudo-random graphs.

Affiliated with

Also associated with

No associations

Rating

Resilient pancyclicity of random and pseudo-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 Resilient pancyclicity of random and pseudo-random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resilient pancyclicity of random and pseudo-random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-231577