Relative Length of Long Paths and Cycles in Graphs

Abstract: For a graph

G

,

n

denotes the order of

G

,

p

the order of a longest path in

G

and

c

the order of a longest cycle. We show that if

G

is a 2-connected graph such that

d (x) + d (y) + d (z) g e p + 2

for all triples

x, y, z

of independent vertices, then

c g e p - 1

. This improves results of Nash-Williams (in terms of minimum degree

d e l t a

and order

n

), Bondy (in terms of degree sum

s i g m a_{3}

and order

n

), and Enomoto, Heuvel, Kaneko and Saito (in terms of degree sum

s i g m a_{3}

, order

n

and relative length

d i f f (G) = p - c

).

This page was built for publication: Relative Length of Long Paths and Cycles in Graphs