Random directed graphs are robustly Hamiltonian

Dan Hefetz, Angelika Steger, Benny Sudakov

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

7 ציטוטים ‏(Scopus)

תקציר

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

שפה מקוריתאנגלית
עמודים (מ-עד)345-362
מספר עמודים18
כתב עתRandom Structures and Algorithms
כרך49
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ספט׳ 2016
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Random directed graphs are robustly Hamiltonian'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי