Degree sums for edges and cycle lengths in graphs

Stephan Brandt, Henk Jan Veldman

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
326 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 languageEnglish
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
  • Pancyclic
  • Sum
  • Tough
  • Hamiltonian

Fingerprint

Dive into the research topics of 'Degree sums for edges and cycle lengths in graphs'. Together they form a unique fingerprint.

Cite this