Arbitrary orientations of cycles in oriented graphs
Arbitrary orientations of cycles in oriented graphs
We show that every sufficiently large oriented graph $G$ with both minimum indegree and outdegree at least $(3|V(G)|-1)/8$ contains every possible orientation of a Hamilton cycle. This improves on an approximate result by Kelly and solves a problem of H\"aggkvist and Thomason from 1995. Moreover the bound is best possible. We also obtain a pancyclicity result for arbitrary orientations. More precisely, we show that the above degree condition is sufficient to guarantee a cycle of every possible orientation and of every possible length unless $G$ is isomorphic to one of exceptional oriented graphs.
Guanghui Wang、Yun Wang、Zhiwei Zhang
数学
Guanghui Wang,Yun Wang,Zhiwei Zhang.Arbitrary orientations of cycles in oriented graphs[EB/OL].(2025-04-13)[2025-04-29].https://arxiv.org/abs/2504.09794.点此复制
评论