A note on a degree sum condition for long cycles in graphs

Publication date: 27 November 2007

Abstract: We conjecture that a 2-connected graph

G

of order

n

, in which

d (x) + d (y) g e q n - k

for every pair of non-adjacent vertices

x

and

y

, contains a cycle of length

n - k

(

k < n / 2

), unless

G

is bipartite and

n - k

is odd. This generalizes to long cycles a well-known degree sum condition for hamiltonicity of Ore. The conjecture is shown to hold for

k = 1

.

This page was built for publication: A note on a degree sum condition for long cycles in graphs