کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647849 | 1342380 | 2012 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Solution to an open problem on 4-ordered Hamiltonian graphs Solution to an open problem on 4-ordered Hamiltonian graphs](/preview/png/4647849.png)
A graph GG is kk-ordered if for any sequence of kk distinct vertices of GG, there exists a cycle in GG containing these kk vertices in the specified order. It is kk-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 K4K4 and K3,3K3,3. Some progress was made in Mészáros (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.
Journal: Discrete Mathematics - Volume 312, Issue 15, 6 August 2012, Pages 2356–2370