Pancyclic subgraphs of random graphs

DOI10.1002/JGT.20638MaRDI QIDQ2911059zbMATH OpenOpenAlexFDO

Authors Choongbum Lee, Wojciech Samotij

Publication date 12 September 2012

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

Hamiltonicitypancyclicityrandom graph

Mathematics Subject Classification ID

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

Abstract: An $n$-vertex graph is called pancyclic if it contains a cycle of length $t$ for all $3leqtleqn$. In this paper, we study pancyclicity of random graphs in the context of resilience, and prove that if $pgg{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))nchoose2p$ 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).

Review text

The authors study pancyclic subgraphs of classical random graph \(G(n,p)\). A graph of order \(n\) is called pancyclic if it contains a cycle of length \(t\) for all \(3\leq t\leq n\). It is shown that, if \(p\geq n^{-1/2}\), then a.a.s. every Hamiltonian subgraph \(G'\) of \(G(n,p)\) with more than \((\frac12+o(1))n^2p/2\) edges is pancyclic. The proof heavily relies on the fact that \(G'\) contains a Hamilton cycle. The prefactor \(1/2\) is shown to be optimal.

Recommendations

• Pancyclic Hamilton cycles in random graphs
• Resilient pancyclicity of random and pseudorandom graphs
• 1-Pancyclic Hamilton Cycles in Random Graphs
• Hamiltonicity, independence number, and pancyclicity
• scientific article; zbMATH DE number 17673

Cites work

• 1-Pancyclic Hamilton Cycles in Random Graphs
• Bandwidth theorem for random graphs
• Combinatorial theorems in sparse random sets
• Cycles in random graphs
• Cycles of even length in graphs
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Local resilience of almost spanning trees in random graphs
• On the asymmetry of random regular graphs and random graphs
• On the resilience of long cycles in random graphs
• On two Hamilton cycle problems in random graphs
• Pancyclic graphs. I
• Pancyclic Hamilton cycles in random graphs
• Resilient pancyclicity of random and pseudorandom graphs
• Turán's extremal problem in random graphs: Forbidding odd cycles

Cited in

(4)

• Pancyclic Hamilton cycles in random graphs
• Cycles in random graphs
• Resilient pancyclicity of random and pseudorandom graphs
• 1-Pancyclic Hamilton Cycles in Random Graphs

This page was built for publication: Pancyclic subgraphs of random graphs

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