A stability version for a theorem of Erdős on nonhamiltonian graphs

Abstract: Let

n, d

be integers with

1 l e q d l e q l e f t l f l o o r f r a c n - 1 2 i g h t f l o o r

, and set

h (n, d) := n - d c h o o s e 2 + d^{2}

and

e (n, d) := m a x h (n, d), h (n, l e f t l f l o o r f r a c n - 1 2 i g h t f l o o r)

. Because

h (n, d)

is quadratic in

d

, there exists a

d_{0} (n) = (n / 6) + O (1)

such that

e (n, 1) > e (n, 2) > d o t s > e (n, d_{0}) = e (n, d_{0} + 1) = d o t s = e (n, l e f t l f l o o r f r a c n - 1 2 i g h t f l o o r)

. A theorem by ErdH{o}s states that for

d l e q l e f t l f l o o r f r a c n - 1 2 i g h t f l o o r

, any

n

-vertex nonhamiltonian graph

G

with minimum degree

d e l t a (G) g e q d

has at most

e (n, d)

edges, and for

d > d_{0} (n)

the unique sharpness example is simply the graph

K_{n} - E (K_{l c e i l (n + 1) / 2 c e i l})

. ErdH{o}s also presented a sharpness example

H_{n, d}

for each

1 l e q d l e q d_{0} (n)

. We show that if

d < d_{0} (n)

and a

2

-connected, nonhamiltonian

n

-vertex graph

G

with

d e l t a (G) g e q d

has more than

e (n, d + 1)

edges, then

G

is a subgraph of

H_{n, d}

. Note that

e (n, d) - e (n, d + 1) = n - 3 d - 2 g e q n / 2

whenever

d < d_{0} (n) - 1

.

Recommendations

Cites Work

Cited In (12)

This page was built for publication: A stability version for a theorem of Erdős on nonhamiltonian graphs