Abstract:
 A graph G is kordered if for any sequence of k distinct vertices of G,
there exists a cycle in G containing these k vertices in the specied order.
It is kordered Hamiltonian if, in addition, the required cycle is Hamiltonian. The question of the existence of an innite class of 3regular 4ordered
Hamiltonian graphs was posed in 1997. At the time, the only known examples were K4 and K3;3. Some progress was made in 2008 when the
Peterson graph was found to be 4ordered and the Heawood graph was
proved to be 4ordered Hamiltonian; moreover an innite class of 3regular
4ordered graphs was found. In this paper we show that a subclass of generalized Petersen graphs are 4ordered and give a complete classication
for which of these graphs are 4ordered Hamiltonian. In particular, this
answers the open question regarding the existence of an innite class of
3regular 4ordered Hamiltonian graphs. Moreover, a number of results
related to other open problems are presented.
