Embedding cycles of given length in oriented graphs

DOI10.1016/J.EJC.2012.10.002zbMATH Open1254.05086arXiv1110.5669OpenAlexW2010672409MaRDI QIDQ691601FDOQ691601

Authors: Daniela Kühn, Deryk Osthus, Diana Piguet 

Publication date: 3 December 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Kelly, Kuehn and Osthus conjectured that for any l>3 and the smallest number k>2 that does not divide l, any large enough oriented graph G with minimum indegree and minimum outdegree at least lfloor |V(G)|/k floor +1 contains a directed cycle of length l. We prove this conjecture asymptotically for the case when l is large enough compared to k and k>6. The case when k<7 was already settled asymptotically by Kelly, Kuehn and Osthus.

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

Recommendations

• Cycles of given length in oriented graphs
• Short cycles in oriented graphs
• Degree Conditions Forcing Directed Cycles
• Oriented hamilton cycles in digraphs
• scientific article; zbMATH DE number 1047732

zbMATH Keywords

short cyclessemidegree

Mathematics Subject Classification ID

Vertex degrees (05C07) Paths and cycles (05C38)

Cited In (8)

• A density result for random sparse oriented graphs and its relation to a conjecture of Woodall
• Embeddings of planar graphs that minimize the number of long-face cycles
• Cycles in \(k\)-traceable oriented graphs
• Cycles of given length in oriented graphs
• Degree conditions forcing oriented cycles
• On cyclically embeddable \((n,n-1)\)-graphs
• Cycle contraction in oriented graphs
• Degree Conditions Forcing Directed Cycles

This page was built for publication: Embedding cycles of given length in oriented graphs

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