Random directed graphs are robustly Hamiltonian

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 order...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2016-09, Vol.49 (2), p.345-362
Main Authors: Hefetz, Dan, Steger, Angelika, Sudakov, Benny
Format: Article
Language:English
Subjects:
Algorithms
Asymptotic properties
Constants
Graph theory
Graphs
Hamilton cycle
random digraph
Resilience
Theorems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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≫logn/n, then a.a.s. every subdigraph of D(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. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 345–362, 2016
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.20631