Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652367 | Electronic Notes in Discrete Mathematics | 2009 | 5 Pages |
Abstract
We show that for each ℓ⩾4 every sufficiently large oriented graph G whose minimum out- and indegrees satisfy δ+(G), δ−(G)⩾⌊|G|/3⌋+1 contains an ℓ-cycle. This is best possible for all those ℓ⩾4 which are not divisible by 3. Surprisingly, for some other values of ℓ, an ℓ-cycle is forced by a much weaker minimum degree condition. We propose and discuss a conjecture regarding the precise minimum degree which forces an ℓ-cycle (with ℓ⩾4 divisible by 3) in an oriented graph. We also give an application of our results to pancyclicity.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics