Cycles of given length in oriented graphs

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

We show that for each l >= 4 every sufficiently large oriented graph G with delta(+)(G), delta(-) (G) >= [vertical bar G vertical bar/3] + 1 contains an l-cycle. This is best possible for all those l >= 4 which are not divisible by 3. Surprisingly, for some other values of e., an e-cycle is forced by a much weaker minimum degree condition. We propose and discuss a conjecture regarding the precise minimum degree which forces an l-cycle (with l >= 4 divisible by 3) in an oriented graph. We also give an application of our results to pancyclicity and consider l-cycles in general digraphs. (C) 2009 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)251-264
Number of pages14
JournalJournal of Combinatorial Theory. Series B
Volume100
Issue number3
DOIs
Publication statusPublished - 1 May 2010

Keywords

  • Short cycles
  • Digraphs
  • Oriented graphs
  • Semidegree

Fingerprint

Dive into the research topics of 'Cycles of given length in oriented graphs'. Together they form a unique fingerprint.

Cite this