Robust Hamiltonicity of random directed graphs

DOI10.1016/J.JCTB.2017.03.006zbMATH Open1368.05090arXiv1410.2198OpenAlexW2340963721WikidataQ105583657 ScholiaQ105583657MaRDI QIDQ2399348FDOQ2399348

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

Publication date: 22 August 2017

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

Abstract: In his seminal paper from 1952 Dirac showed that the complete graph on $ngeq3$ vertices remains Hamiltonian even if we allow an adversary to remove $lfloorn/2floor$ edges touching each vertex. In 1960 Ghouila-Houri obtained an analogue statement for digraphs by showing that every directed graph on $ngeq3$ vertices with minimum in- and out-degree at least $n/2$ contains a directed Hamilton cycle. Both statements quantify the robustness of complete graphs (digraphs) with respect to the property of containing a Hamilton cycle. A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of emph{local resilience}. The local resilience of a graph (digraph) $G$ with respect to a property $mathcalP$ is the maximum number $r$ such that $G$ has the property $mathcalP$ even if we allow an adversary to remove an $r$-fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is $1/2$. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability $p=omega(logn/n)$ with respect to Hamiltonicity is $1/2pmo(1)$. For random directed graphs, Hefetz, Steger and Sudakov (2014+) proved an analogue statement, but only for edge probability $p=omega(logn/sqrtn)$. In this paper we significantly improve their result to $p=omega(lo{g}^{8}n/n)$, which is optimal up to the polylogarithmic factor.

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

Recommendations

• Robust Hamiltonicity of random directed graphs: extended abstract
• Random directed graphs are robustly Hamiltonian
• Hamiltonicity in random directed graphs is born resilient
• Dirac's theorem for random regular graphs
• Dirac's theorem for random graphs

zbMATH Keywords

random digraphslocal resiliencedirected Hamilton cycle

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Some Theorems on Abstract Graphs
• Dirac's theorem for random graphs
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• Hamiltonian circuits in random 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
• Local resilience of graphs
• Resilient pancyclicity of random and pseudorandom graphs
• An algorithm for finding hamilton cycles in random directed graphs
• On two Hamilton cycle problems in random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• Random directed graphs are robustly Hamiltonian

Cited In (18)

• Packing trees of unbounded degrees in random graphs
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
• Random directed graphs are robustly Hamiltonian
• Dirac-type theorems in random hypergraphs
• Covering cycles in sparse graphs
• Dirac's theorem for random regular graphs
• A Dirac-type theorem for Berge cycles in random hypergraphs
• Hamiltonicity in random graphs is born resilient
• Packing arborescences in random digraphs
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• The bandwidth theorem for locally dense 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
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Dirac's theorem for random graphs
• Robust Hamiltonicity of Dirac graphs
• The birth of the strong components

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

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