|国家预印本平台
首页|Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree

Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree

Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree

来源:Arxiv_logoArxiv
英文摘要

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.点此复制

评论