Random directed graphs are robustly Hamiltonian

DOI10.1002/RSA.20631zbMATH Open1346.05271arXiv1404.4734OpenAlexW217363743MaRDI QIDQ2820274FDOQ2820274

Authors: Dan Hefetz, Angelika Steger, Benny Sudakov 

Publication date: 15 September 2016

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

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.

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

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

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)

Cites Work

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

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)