Long cycles in subgraphs of (pseudo)random directed graphs

DOI10.1002/jgt.20616zbMath1244.05195arXiv1009.3721OpenAlexW1935724303MaRDI QIDQ2897207

Ido Ben-Eliezer, Michael Krivelevich, Benjamin 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

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

Related Items (13)

Colorful Hamilton Cycles in Random Graphs ⋮ Dirac's theorem for random graphs ⋮ Large monochromatic components and long monochromatic cycles in random hypergraphs ⋮ Covering cycles in sparse graphs ⋮ Monochromatic paths in random tournaments ⋮ On some Multicolor Ramsey Properties of Random Graphs ⋮ Towards the Erdős-Gallai cycle decomposition conjecture ⋮ Perfect matchings and Hamiltonian cycles in the preferential attachment model ⋮ Size-Ramsey numbers of cycles versus a path ⋮ Directed Ramsey number for trees ⋮ Long paths and cycles in random subgraphs of graphs with large minimum degree ⋮ Longest cycles in sparse random digraphs ⋮ The phase transition in random graphs: A simple proof

Cites Work

• The size Ramsey number of a directed path
• Increasing the chromatic number of a random graph
• On the resilience of long cycles in random graphs
• On maximal circuits in directed graphs
• A density result for random sparse oriented graphs and its relation to a conjecture of Woodall
• Global connectivity and expansion: long cycles and factors in \(f\)-connected graphs
• Almost spanning subgraphs of random graphs after adversarial edge removal
• Local resilience of almost spanning trees in random graphs
• Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs
• Resilient Pancyclicity of Random and Pseudorandom Graphs
• Local resilience of graphs
• Cycles in digraphs– a survey
• Sufficient Conditions for Circuits in Graphs^†

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