Resilient pancyclicity of random and pseudorandom graphs

DOI10.1137/090761148MaRDI QIDQ3084209zbMATH OpenOpenAlexWikidataFDO

Authors Michael Krivelevich, Choongbum Lee, Benny Sudakov

Publication date 15 March 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0906.1397

zbMATH Keywords

pancyclicityrandom graphsresilience

Mathematics Subject Classification ID

Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Abstract: A graph $G$ on $n$ vertices is extit{pancyclic} if it contains cycles of length $t$ for all $3leqtleqn$. 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 $pgg{n}^{-1+1/(l-1)}$ for some integer $lgeq3$ 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 $lleqtleqn$. 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.

Recommendations

• On the resilience of long cycles in random graphs
• Pancyclic subgraphs of random graphs
• Cycles in random graphs
• scientific article; zbMATH DE number 17673
• Long cycles in subgraphs of (pseudo)random directed graphs

Cited in

(29)

• On the resilience of long cycles in random graphs
• A Dirac-type theorem for Berge cycles in random hypergraphs
• Robust Hamiltonicity of random directed graphs
• On the Hamiltonicity of random bipartite graphs
• Triangle resilience of the square of a Hamilton cycle in random graphs
• Corrádi and Hajnal's theorem for sparse random graphs
• Long cycles in subgraphs of (pseudo)random directed graphs
• Pancyclic subgraphs of random graphs
• Local resilience of almost spanning trees in random graphs
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Dirac's theorem for random graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Generating random graphs in biased maker-breaker games
• Local resilience of graphs
• Embedding cycles in finite planes
• Local resilience of an almost spanning k‐cycle in random graphs
• Extremal results for odd cycles in sparse pseudorandom graphs
• Hamiltonicity in random directed graphs is born resilient
• Dirac's theorem for random regular graphs
• Spanning Structures in Walker–Breaker Games
• A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• Robust Hamiltonicity of Dirac graphs
• Graph Tilings in Incompatibility Systems
• Coprime networks of the composite numbers: pseudo-randomness and synchronizability
• Walker-breaker games on \(G_{n, p}\)
• Counting odd cycles in sparse pseudorandom graphs
• Cyclic subsets in regular Dirac graphs
• Bandwidth theorem for random graphs

This page was built for publication: Resilient pancyclicity of random and pseudorandom graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3084209)