Random directed graphs are robustly Hamiltonian

DOI10.1002/rsa.20631zbMath1346.05271arXiv1404.4734OpenAlexW217363743MaRDI QIDQ2820274

Angelika Steger, Dan Hefetz, Benjamin Sudakov

Publication date: 15 September 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random digraphHamilton cycleresilience

Mathematics Subject Classification ID

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

Related Items (9)

Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs ⋮ Robust Hamiltonicity of random directed graphs ⋮ The birth of the strong components ⋮ A Dirac-type theorem for Berge cycles in random hypergraphs ⋮ Packing, counting and covering Hamilton cycles in random directed graphs ⋮ Random directed graphs are robustly Hamiltonian ⋮ Compatible Hamilton cycles in random graphs ⋮ Hamiltonicity in random directed graphs is born resilient ⋮ Dirac’s theorem for random regular graphs

Cites Work

• Unnamed Item
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Small subsets inherit sparse \(\varepsilon\)-regularity
• On two Hamilton cycle problems in random graphs
• Hamiltonian cycles in Dirac graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Hamiltonian circuits in random graphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Random directed graphs are robustly Hamiltonian
• Hitting time results for Maker-Breaker games
• Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs
• Dirac's theorem for random graphs
• On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs
• On the number of hamilton cycles in a random graph
• Local resilience of graphs
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• An algorithm for finding hamilton cycles in random directed graphs
• Clutter percolation and random graphs
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
• Positional games on random graphs
• Optimal Packings of Hamilton Cycles in Sparse Random Graphs
• Optimal Packings of Hamilton Cycles in Graphs of High Minimum Degree
• Edge-disjoint Hamilton cycles in random graphs
• Biased games on random boards
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Robust Hamiltonicity of Dirac graphs
• Some Theorems on Abstract Graphs

This page was built for publication: Random directed graphs are robustly Hamiltonian