Degree Conditions Forcing Directed Cycles

DOI10.1093/IMRN/RNAC114MaRDI QIDQ6097876zbMATH OpenOpenAlexFDO

Authors A. Grzesik, Jan Volec

Publication date 7 June 2023

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.12830

zbMATH Keywords

Caccetta-Häggkvist conjecturesemidegreeshort cycles

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Abstract: Caccetta-H"aggkvist conjecture is a longstanding open problem on degree conditions that force an oriented graph to contain a directed cycle of a bounded length. Motivated by this conjecture, Kelly, K"uhn and Osthus initiated a study of degree conditions forcing the containment of a directed cycle of a given length. In particular, they found the optimal minimum semidegree, i.e., the smaller of the minimum indegree and the minimum outdegree, that forces a large oriented graph to contain a directed cycle of a given length not divisible by $3$, and conjectured the optimal minimum semidegree for all the other cycles except the directed triangle. In this paper, we establish the best possible minimum semidegree that forces a large oriented graph to contain a directed cycle of a given length divisible by $3$ yet not equal to $3$, hence fully resolve the conjecture of Kelly, K"uhn and Osthus. We also find an asymptotically optimal semidegree threshold of any cycle with a given orientation of its edges with the sole exception of a directed triangle.

Recommendations

• Cycles of given length in oriented graphs
• Short cycles in oriented graphs
• Embedding cycles of given length in oriented graphs
• On the Caccetta-Häggkvist conjecture
• scientific article; zbMATH DE number 6263412

Cited in

(4)

• Short cycles in oriented graphs
• Degree conditions forcing oriented cycles
• Embedding cycles of given length in oriented graphs
• Cycles of given length in oriented graphs

This page was built for publication: Degree Conditions Forcing Directed Cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6097876)