完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Hsu, Lih-Hsing | en_US |
dc.contributor.author | Tan, Jimmy J. M. | en_US |
dc.contributor.author | Cheng, Eddie | en_US |
dc.contributor.author | Liptak, Laszlo | en_US |
dc.contributor.author | Lin, Cheng-Kuan | en_US |
dc.contributor.author | Tsai, Ming | en_US |
dc.date.accessioned | 2014-12-08T15:23:26Z | - |
dc.date.available | 2014-12-08T15:23:26Z | - |
dc.date.issued | 2012-08-06 | en_US |
dc.identifier.issn | 0012-365X | en_US |
dc.identifier.uri | http://hdl.handle.net/11536/16416 | - |
dc.description.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. | en_US |
dc.language.iso | en_US | en_US |
dc.subject | Generalized Petersen graphs | en_US |
dc.subject | Hamiltonian | en_US |
dc.subject | 4-ordered | en_US |
dc.title | Solution to an open problem on 4-ordered Hamiltonian graphs | en_US |
dc.type | Article | en_US |
dc.identifier.journal | DISCRETE MATHEMATICS | en_US |
dc.citation.volume | 312 | en_US |
dc.citation.issue | 15 | en_US |
dc.citation.epage | 2356 | en_US |
dc.contributor.department | 資訊工程學系 | zh_TW |
dc.contributor.department | Department of Computer Science | en_US |
dc.identifier.wosnumber | WOS:000305724900018 | - |
dc.citation.woscount | 1 | - |
顯示於類別: | 期刊論文 |