Degree sums for edges and cycle lengths in graphs

Stephan Brandt, H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
165 Downloads (Pure)

Abstract

Let G be a graph of order n satisfying d(u) + d(v) n for every edge uv of G. We show that the circumference - the length of a longest cycle - of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length between 3 and the circumference, unless G is complete bipartite. If G is 1-tough then it is pancyclic or G = Kr,r with r = n/2.
Original languageUndefined
Pages (from-to)253-256
Number of pages4
JournalJournal of graph theory
Volume25
Issue number4
DOIs
Publication statusPublished - 1997

Keywords

  • Circumference
  • Closure
  • Cycle
  • Graph
  • Degree
  • IR-71423
  • pancyclic
  • sum
  • tough
  • METIS-140776
  • Hamiltonian

Cite this