Title: Solution to an open problem on 4-ordered Hamiltonian graphs
Authors: Hsu, Lih-Hsing
Tan, Jimmy J. M.
Cheng, Eddie
Liptak, Laszlo
Lin, Cheng-Kuan
Tsai, Ming
Department of Computer Science
Keywords: Generalized Petersen graphs;Hamiltonian;4-ordered
Issue Date: 6-Aug-2012
Abstract: A graph G is k-ordered if for any sequence of k distinct vertices of G, there exists a cycle in G containing these k vertices in the specified order. It is k-ordered Hamiltonian if, in addition, the required cycle is Hamiltonian. The question of the existence of an infinite class of 3-regular 4-ordered Hamiltonian graphs was posed in Ng and Schultz (1997) [10]. At the time, the only known examples were K-4 and K-3.3. Some progress was made in Meszaros (2008) [9] when the Peterson graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered Hamiltonian: moreover an infinite class of 3-regular 4-ordered graphs was found. In this paper we show that a subclass of generalized Petersen graphs are 4-ordered and give a complete classification for which of these graphs are 4-ordered Hamiltonian. In particular, this answers the open question regarding the existence of an infinite class of 3-regular 4-ordered Hamiltonian graphs. Moreover, a number of results related to other open problems are presented. (C) 2012 Elsevier B.V. All rights reserved.
URI: http://hdl.handle.net/11536/16416
ISSN: 0012-365X
Volume: 312
Issue: 15
End Page: 2356
Appears in Collections:Articles

Files in This Item:

  1. 000305724900018.pdf