کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1136620 | 1489137 | 2013 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
4-ordered-Hamiltonian problems of the generalized Petersen graph GP(n,4)
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
کنترل و سیستم های مهندسی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: 4-ordered-Hamiltonian problems of the generalized Petersen graph GP(n,4) 4-ordered-Hamiltonian problems of the generalized Petersen graph GP(n,4)](/preview/png/1136620.png)
چکیده انگلیسی
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 K4 and K3,3. Some progress was made by Mészáros 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 a1,a2,â¦,ak of G, there exists a Hamiltonian path in G from a1 to ak where these k vertices appear in the specified order.)
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Mathematical and Computer Modelling - Volume 57, Issues 3â4, February 2013, Pages 595-601
Journal: Mathematical and Computer Modelling - Volume 57, Issues 3â4, February 2013, Pages 595-601
نویسندگان
Chun-Nan Hung, David Lu, Randy Jia, Cheng-Kuan Lin, László Lipták, Eddie Cheng, Jimmy J.M. Tan, Lih-Hsing Hsu,