Cycles of given length in oriented graphs

DOI10.1016/J.JCTB.2009.08.002MaRDI QIDQ965252zbMATH OpenOpenAlexFDO

Authors Daniela Kühn, Deryk Osthus, Luke Kelly

Publication date 21 April 2010

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

digraphsshort cyclesoriented graphssemidegree

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Abstract: We show that for each ellgeq 4 every sufficiently large oriented graph G with delta^+(G), delta^-(G) geq lfloor |G|/3 floor +1 contains an ell-cycle. This is best possible for all those ellgeq 4 which are not divisible by 3. Surprisingly, for some other values of ell, an ell-cycle is forced by a much weaker minimum degree condition. We propose and discuss a conjecture regarding the precise minimum degree which forces an ell-cycle (with ell geq 4 divisible by 3) in an oriented graph. We also give an application of our results to pancyclicity and consider ell-cycles in general digraphs.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• scientific article; zbMATH DE number 5528972 (Why is no real title available?)
• scientific article; zbMATH DE number 3916300 (Why is no real title available?)
• scientific article; zbMATH DE number 3630786 (Why is no real title available?)
• scientific article; zbMATH DE number 1067836 (Why is no real title available?)
• scientific article; zbMATH DE number 1943959 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3333210 (Why is no real title available?)
• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
• An Ore-type condition implying a digraph to be pancyclic
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Directed triangles in digraphs
• Embedding large subgraphs into dense graphs
• Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
• On directed triangles in digraphs
• On minimal regular digraphs with given girth
• On pancyclic digraphs
• On the Caccetta-Häggkvist conjecture
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the girth of digraphs
• Pancyclic oriented graphs
• Short cycles in digraphs
• Short cycles in directed graphs
• Testing subgraphs in directed graphs

Cited in

(13)

• A density result for random sparse oriented graphs and its relation to a conjecture of Woodall
• Cycles in \(k\)-traceable oriented graphs
• Cycle-factors in oriented graphs
• A survey on Hamilton cycles in directed graphs
• Degree conditions forcing oriented cycles
• Improved sufficient conditions for the existence of anti-directed Hamiltonian cycles in digraphs
• Antidirected subgraphs of oriented graphs
• Hamiltonian degree sequences in digraphs
• Cycle contraction in oriented graphs
• Embedding cycles of given length in oriented graphs
• Degree Conditions Forcing Directed Cycles
• Short cycles in oriented graphs
• Cycles in oriented 3-graphs

This page was built for publication: 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 Q965252)