Random directed graphs are robustly Hamiltonian1. Issue 2 (24th December 2015)

• Record Type: Journal Article
• Authors: Hefetz, Dan; Steger, Angelika; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 49:Issue 2(2016)
• Page Start: 345
• Page End: 362
• Publication Date: 2015-12-24
• Subjects: random digraph -- Hamilton cycle -- resilience; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20631
• Languages: English
• ISSNs: 1042-9832

Abstract

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 D ( 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 p ≫ log n / n, then a.a.s. every subdigraph of D ( n, p ) with minimum out‐degree and in‐degree at least ( 1 / 2 + o ( 1 ) ) n p 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. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 345–362, 2016