標題: 4-ordered-Hamiltonian problems of the generalized Petersen graph GP(n, 4)
作者: Hung, Chun-Nan
Lu, David
Jia, Randy
Lin, Cheng-Kuan
Liptak, Laszlo
Cheng, Eddie
Tan, Jimmy J. M.
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
關鍵字: Petersen graph;4-ordered;Hamiltonian;Hamiltonian-connected
公開日期: 1-二月-2013
摘要: A graph G is k-ordered if for every 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 a Hamiltonian cycle in G. The question of the existence of an infinite class of 3-regular 4-ordered-Hamiltonian graphs was posed in Ng and Schultz in 1997 [2]. At the time, the only known examples of such graphs were K-4 and K-3,K-3. Some progress was made by Meszaros in 2008 [21] when the Petersen 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 2010, a subclass of the generalized Petersen graphs was shown to be 4-ordered in Hsu et al. [9], with an infinite subset of this subclass being 4-ordered-Hamiltonian, thus answering the open question. However, these graphs are bipartite. In this paper we extend the result to another subclass of the generalized Petersen graphs. In particular, we find the first class of infinite non-bipartite graphs that are both 4-ordered-Hamiltonian and 4-ordered-Hamiltonian-connected, which can be seen as a solution to an extension of the question posted in Ng and Schultz in 1997 [2]. (A graph G is k-ordered-Hamiltonian-connected if for every sequence of k distinct vertices a(1), a(2),..., a(k) of G, there exists a Hamiltonian path in G from a(1) to a(k) where these k vertices appear in the specified order.) (C) 2012 Elsevier Ltd. All rights reserved.
URI: http://dx.doi.org/10.1016/j.mcm.2012.07.022
http://hdl.handle.net/11536/20572
ISSN: 0895-7177
DOI: 10.1016/j.mcm.2012.07.022
期刊: MATHEMATICAL AND COMPUTER MODELLING
Volume: 57
Issue: 3-4
起始頁: 595
結束頁: 601
顯示於類別:期刊論文


文件中的檔案:

  1. 000311911700026.pdf