Solution to an open problem on 4-ordered Hamiltonian graphs

Lih-Hsing Hsu, Jiann-Mean Tan, Eddie Cheng, Liptak Laszlo, Cheng-Kuan Lin, Ming Tsai

Research output: Contribution to journalArticle

3 Scopus citations

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.
Original languageEnglish
Pages (from-to)2356-2370
Number of pages15
JournalDiscrete Mathematics
Volume312
Issue number15
DOIs
StatePublished - 6 Aug 2012

Keywords

  • Generalized Petersen graphs
  • Hamiltonian
  • 4-ordered

Fingerprint Dive into the research topics of 'Solution to an open problem on 4-ordered Hamiltonian graphs'. Together they form a unique fingerprint.

  • Cite this

    Hsu, L-H., Tan, J-M., Cheng, E., Laszlo, L., Lin, C-K., & Tsai, M. (2012). Solution to an open problem on 4-ordered Hamiltonian graphs. Discrete Mathematics, 312(15), 2356-2370. https://doi.org/10.1016/j.disc.2012.04.003