Robust Hamiltonicity of random directed graphs

DOI10.1016/j.jctb.2017.03.006zbMath1368.05090arXiv1410.2198OpenAlexW2340963721WikidataQ105583657 ScholiaQ105583657MaRDI QIDQ2399348

Nemanja Škorić, Ueli Peter, Rajko Nenadov, Andreas Noever, Asaf Ferber

Publication date: 22 August 2017

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

random digraphslocal resiliencedirected Hamilton cycle

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (12)

Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs ⋮ Dirac-type theorems in random hypergraphs ⋮ Covering cycles in sparse graphs ⋮ The birth of the strong components ⋮ A Dirac-type theorem for Berge cycles in random hypergraphs ⋮ The bandwidth theorem for locally dense graphs ⋮ Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs ⋮ Packing Arborescences in Random Digraphs ⋮ Packing, counting and covering Hamilton cycles in random directed graphs ⋮ Packing trees of unbounded degrees in random graphs ⋮ Hamiltonicity in random directed graphs is born resilient ⋮ Dirac’s theorem for random regular graphs

Cites Work

• On two Hamilton cycle problems in random graphs
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• Hamiltonian circuits in random graphs
• Random directed graphs are robustly Hamiltonian
• 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
• Dirac's theorem for random graphs
• On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs
• Local resilience of graphs
• An algorithm for finding hamilton cycles in random directed graphs
• Some Theorems on Abstract Graphs
• Unnamed Item

This page was built for publication: Robust Hamiltonicity of random directed graphs