Degree sums for edges and cycle lengths in graphs

Stephan Brandt, H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
85 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

Brandt, Stephan ; Veldman, H.J. / Degree sums for edges and cycle lengths in graphs. In: Journal of graph theory. 1997 ; Vol. 25, No. 4. pp. 253-256.
@article{b618479e197e40b79d59f5edde85c0be,
title = "Degree sums for edges and cycle lengths in graphs",
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.",
keywords = "Circumference, Closure, Cycle, Graph, Degree, IR-71423, pancyclic, sum, tough, METIS-140776, Hamiltonian",
author = "Stephan Brandt and H.J. Veldman",
year = "1997",
doi = "10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J",
language = "Undefined",
volume = "25",
pages = "253--256",
journal = "Journal of graph theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "4",

}

Degree sums for edges and cycle lengths in graphs. / Brandt, Stephan; Veldman, H.J.

In: Journal of graph theory, Vol. 25, No. 4, 1997, p. 253-256.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Degree sums for edges and cycle lengths in graphs

AU - Brandt, Stephan

AU - Veldman, H.J.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

KW - Circumference

KW - Closure

KW - Cycle

KW - Graph

KW - Degree

KW - IR-71423

KW - pancyclic

KW - sum

KW - tough

KW - METIS-140776

KW - Hamiltonian

U2 - 10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J

DO - 10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J

M3 - Article

VL - 25

SP - 253

EP - 256

JO - Journal of graph theory

JF - Journal of graph theory

SN - 0364-9024

IS - 4

ER -