Long cycles in subgraphs of (pseudo)random directed graphs

DOI10.1002/JGT.20616MaRDI QIDQ2897207zbMATH OpenOpenAlexFDO

Authors Ido Ben-Eliezer, Michael Krivelevich, Benny Sudakov

Publication date 10 July 2012

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

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

zbMATH Keywords

long cyclesresiliencepseudorandom digraphs

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

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
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• Resilient pancyclicity of random and pseudorandom graphs
• Colorful Hamilton Cycles in Random 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)