K-ORDERED HAMILTONIAN GRAPHS

A hamiltonian graph G of order n is k-ordered, 2 less than or equal to k less than or equal to n, if for every sequence v(1), v(2),..., v(k) of k distinct vertices of G, there exists a hamiltonian cycle that en counters v(1), v(2),..., v(k) in this order. Theorems by Dirac and Ore , presenting sufficient conditions for a graph to be hamiltonian, are generalized to k-ordered hamiltonian graphs. The existence of k-ordere d graphs with small maximum degree is investigated; in particular, a f amily of 4-regular 4-ordered graphs is described. A graph G of order n greater than or equal to 3 is k-hamiltonian-connected, 2 less than or equal to k less than or equal to n, if for every sequence v(1), v(2), ..., v(k) of k distinct vertices, G contains a v(1)-v(k) hamiltonian p ath that encounters v(1), v(2),..., v(k) in this order. It is shown th at for k greater than or equal to 3, every (k + 1)-hamiltonian-connect ed graph is k-ordered and a result of Ore on hamiltonian-connected gra phs is generalized to k-hamiltonian-connected graphs. (C) 1997 John Wi ley & Sons, Inc.