Long cycles in subgraphs of (pseudo)random directed graphs

DOI10.1002/JGT.20616zbMATH Open1244.05195arXiv1009.3721OpenAlexW1935724303MaRDI QIDQ2897207FDOQ2897207

Authors: Ido Ben-Eliezer, Michael Krivelevich, Benny Sudakov 

Publication date: 10 July 2012

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

Abstract: We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every $0<gamma<1/2$ we find a constant $c=c(gamma)$ such that the following holds. Let $G=(V,E)$ be a (pseudo)random directed graph on $n$ vertices, and let $G^{\prime }$ be a subgraph of $G$ with $(1/2+gamma)|E|$ edges. Then $G^{\prime }$ contains a directed cycle of length at least $(c-o(1))n$. Moreover, there is a subgraph $G^{″}$ of $G$ with $(1/2+gamma-o(1))|E|$ edges that does not contain a cycle of length at least $cn$.

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

Recommendations

• On the resilience of long cycles in random graphs
• Resilient pancyclicity of random and pseudorandom graphs
• Random directed graphs are robustly Hamiltonian
• Longest cycles in sparse random digraphs
• Turán‐type problems for long cycles in random and pseudo‐random graphs

zbMATH Keywords

long cyclesresiliencepseudorandom digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38)

Cites Work

• The size Ramsey number of a directed path
• On the resilience of long cycles in random graphs
• On maximal circuits in directed graphs
• Local resilience of almost spanning trees in random graphs
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Global connectivity and expansion: long cycles and factors in \(f\)-connected graphs
• Local resilience of graphs
• Sufficient Conditions for Circuits in Graphs^†
• Resilient pancyclicity of random and pseudorandom graphs
• Cycles in digraphs– a survey
• Increasing the chromatic number of a random graph
• A density result for random sparse oriented graphs and its relation to a conjecture of Woodall

Cited In (15)

• Long paths and cycles in random subgraphs of graphs with large minimum degree
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• Covering cycles in sparse graphs
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• Colorful Hamilton Cycles in Random Graphs
• Resilient pancyclicity of random and pseudorandom graphs
• Longest cycles in sparse random digraphs
• On some multicolor Ramsey properties of random graphs
• Towards the Erdős-Gallai cycle decomposition conjecture
• On the resilience of long cycles in random graphs
• The phase transition in random graphs: a simple proof
• Towards the Erdős-Gallai cycle decomposition conjecture
• Size-Ramsey numbers of cycles versus a path
• Dirac's theorem for random graphs

This page was built for publication: Long cycles in subgraphs of (pseudo)random directed graphs

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