Random directed graphs are robustly Hamiltonian

DOI10.1002/RSA.20631MaRDI QIDQ2820274zbMATH OpenOpenAlexFDO

Authors Dan Hefetz, Angelika Steger, Benny 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

Hamilton cycleresiliencerandom digraph

Mathematics Subject Classification ID

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

Abstract: A classical theorem of Ghouila-Houri from 1960 asserts that every directed graph on $n$ vertices with minimum out-degree and in-degree at least $n/2$ contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph $mathcalD(n,p)$, that is, a directed graph in which every ordered pair $(u,v)$ becomes an arc with probability $p$ independently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if $pgglogn/sqrtn$, then a.a.s. every subdigraph of $mathcalD(n,p)$ with minimum out-degree and in-degree at least $(1/2+o(1))np$ contains a directed Hamilton cycle. The constant $1/2$ is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs.

Recommendations

• Robust Hamiltonicity of random directed graphs
• Robust Hamiltonicity of random directed graphs: extended abstract
• Dirac's theorem for random graphs
• Hamiltonicity in random directed graphs is born resilient
• Hamilton cycles in a class of random directed graphs

Cites work

• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• An algorithm for finding hamilton cycles in random directed graphs
• Biased games on random boards
• Clutter percolation and random graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Dirac's theorem for random graphs
• Edge-disjoint Hamilton cycles in random graphs
• Hamiltonian circuits in random graphs
• Hamiltonian cycles in Dirac graphs
• Hitting time results for maker-breaker games
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Local resilience of graphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• On the Number of Hamilton Cycles in Sparse Random Graphs
• On the number of hamilton cycles in a random graph
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On two Hamilton cycle problems in random graphs
• Optimal packings of Hamilton cycles in graphs of high minimum degree
• Optimal packings of Hamilton cycles in sparse random graphs
• Positional games on random graphs
• Random directed graphs are robustly Hamiltonian
• Robust Hamiltonicity of Dirac graphs
• Small subsets inherit sparse \(\varepsilon\)-regularity
• Some Theorems on Abstract Graphs
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph

Cited in

(15)

• Random directed graphs are robustly Hamiltonian
• Dirac's theorem for random regular graphs
• A Dirac-type theorem for Berge cycles in random hypergraphs
• Hamiltonicity in random graphs is born resilient
• Robust Hamiltonicity of random directed graphs
• How many random edges make a dense graph hamiltonian?
• Compatible Hamilton cycles in random graphs
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• Long cycles in subgraphs of (pseudo)random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Robust Hamiltonicity of random directed graphs: extended abstract
• Hamiltonicity in random directed graphs is born resilient
• Dirac's theorem for random graphs
• Robust Hamiltonicity of Dirac graphs
• The birth of the strong components

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

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