Skip to main content
Minimum Degree and Even Cycle Lengths
Bulletin of the Institute of Combinatorics and its Applications
  • Ralph J. Faudree, University of Memphis
  • Ronald Gould, Emory University
  • Michael S. Jacobson, University of Colorado at Denver
  • Colton Magnant, Georgia Southern University
Document Type
Publication Date

A classic result of Dirac states that if G is a 2-connected graph of order n with minimum degree δ ≥ 3, then G contains a cycle of length at least min{n, 2δ}. In this paper, we consider the problem of determining the number of different odd or even cycle lengths that must exist under the minimum degree condition. We conjecture that there are δ − 1 even cycles of different lengths, and when G is nonbipartite, that there are δ− 1 odd cycles of different lengths. We prove this conjecture when δ = 3. Related results concerning the number of different even cycle lengths supporting the conjecture are also included. In particular, we show that there are always at least (δ − 1)/2 even cycles of different lengths.

Citation Information
Ralph J. Faudree, Ronald Gould, Michael S. Jacobson and Colton Magnant. "Minimum Degree and Even Cycle Lengths" Bulletin of the Institute of Combinatorics and its Applications Vol. 77 (2016) p. 59 - 70
Available at: