Premium
Random directed graphs are robustly Hamiltonian
Author(s) -
Hefetz Dan,
Steger Angelika,
Sudakov Benny
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20631
Subject(s) - mathematics , directed graph , combinatorics , random graph , hamiltonian path , random regular graph , discrete mathematics , degree (music) , feedback arc set , hamiltonian (control theory) , graph , line graph , pathwidth , voltage graph , mathematical optimization , physics , acoustics
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