|国家预印本平台
首页|Arbitrary orientations of cycles in oriented graphs

Arbitrary orientations of cycles in oriented graphs

Arbitrary orientations of cycles in oriented graphs

来源:Arxiv_logoArxiv
英文摘要

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

评论