Solution to an open problem on 4-ordered Hamiltonian graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Lih-Hsing Hsu^a ; ^{lhhsu@pu.edu.tw} ; Jimmy J.M. Tan^b ; ^{jmtan@cs.nctu.edu.tw} ; Eddie Cheng^c ; ^{echeng@oakland.edu} ; Lá ; szló ; Liptá ; k^c ; ^{liptak@oakland.edu} ; Cheng-Kuan Lin^b ; ^{cklin@cs.nctu.edu.tw} ; Ming Tsai^a ; ^{cater_home@hotmail.com}
• 关键词：Generalized Petersen graphs ; Hamiltonian ; 4-ordered
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：6 August, 2012
• 卷：312
• 期：15
• 页码：2356-2370
• 文件大小：746 K

摘要

A graph is -ordered if for any sequence of distinct vertices of , there exists a聽cycle in containing these vertices in the specified order. It is -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)聽. At the time, the only known examples were and . Some progress was made in M茅sz谩ros (2008) 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.