# Degree sums for edges and cycle lengths in graphs

Stephan Brandt, H.J. Veldman

6 Citations (Scopus)

### 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 language Undefined 253-256 4 Journal of graph theory 25 4 https://doi.org/10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J Published - 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.

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 -