Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree
Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree
In 1960, Ghouila-Houri proved that every strongly connected directed graph $G$ on $n$ vertices with minimum degree at least $n$ contains a directed Hamilton cycle. We asymptotically generalize this result by proving the following: every directed graph $G$ on $n$ vertices and with minimum degree at least $(1+o(1))n$ contains every orientation of a Hamilton cycle, except for the directed Hamilton cycle in the case when $G$ is not strongly connected. In fact, this minimum degree condition forces every orientation of a cycle in $G$ of every possible length, other than perhaps the directed cycles.
Louis DeBiasio、Andrew Treglown
数学
Louis DeBiasio,Andrew Treglown.Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree[EB/OL].(2025-05-14)[2025-06-22].https://arxiv.org/abs/2505.09793.点此复制
评论