On k-ordered Hamiltonian Graphs

Abstract: A Hamiltonian graph

G

of order

n

is

k

-ordered,

2 l e q k l e q n

, if for every sequence

v_{1}, v_{2}, l d o t s, v_{k}

of

k

distinct vertices of

G

, there exists a Hamiltonian cycle that encounters

v_{1}, v_{2}, l d o t s, v_{k}

in this order. In this paper, answering a question of Ng and Schultz, we give a sharp bound for the minimum degree guaranteeing that a graph is a

k

-ordered Hamiltonian graph under some mild restrictions. More precisely, we show that there are

v a r e p s i l o n, n_{0} > 0

such that if

G

is a graph of order

n g e q n_{0}

with minimum degree at least

l c e i l f r a c n 2 c e i l + l f l o o r f r a c k 2 f l o o r - 1

and

2 l e q k l e q e p s n

, then

G

is a

k

-ordered Hamiltonian graph. It is also shown that this bound is sharp for every

2 l e q k l e q l f l o o r f r a c n 2 f l o o r

.

This page was built for publication: On $k$-ordered Hamiltonian Graphs