Full metadata record
DC FieldValueLanguage
dc.contributor.authorHung, Chun-Nanen_US
dc.contributor.authorLu, Daviden_US
dc.contributor.authorJia, Randyen_US
dc.contributor.authorLin, Cheng-Kuanen_US
dc.contributor.authorLiptak, Laszloen_US
dc.contributor.authorCheng, Eddieen_US
dc.contributor.authorTan, Jimmy J. M.en_US
dc.contributor.authorHsu, Lih-Hsingen_US
dc.date.accessioned2014-12-08T15:28:25Z-
dc.date.available2014-12-08T15:28:25Z-
dc.date.issued2013-02-01en_US
dc.identifier.issn0895-7177en_US
dc.identifier.urihttp://dx.doi.org/10.1016/j.mcm.2012.07.022en_US
dc.identifier.urihttp://hdl.handle.net/11536/20572-
dc.description.abstractA 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.en_US
dc.language.isoen_USen_US
dc.subjectPetersen graphen_US
dc.subject4-ordereden_US
dc.subjectHamiltonianen_US
dc.subjectHamiltonian-connecteden_US
dc.title4-ordered-Hamiltonian problems of the generalized Petersen graph GP(n, 4)en_US
dc.typeArticleen_US
dc.identifier.doi10.1016/j.mcm.2012.07.022en_US
dc.identifier.journalMATHEMATICAL AND COMPUTER MODELLINGen_US
dc.citation.volume57en_US
dc.citation.issue3-4en_US
dc.citation.spage595en_US
dc.citation.epage601en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000311911700026-
dc.citation.woscount0-
Appears in Collections:Articles


Files in This Item:

  1. 000311911700026.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.