2-HC- extendability of generalized Petersen graphs(广义Petersen图的2-HC-可扩性)

Abstract

In 2012, MIKLAVIC et al gave the definition of the l-HC- extendability by combining the extendability of connected graphs with hamiltonicity. Based on their study, a connected graph Γ is l-HC- extendable if it contains a path of length l and every such path could be extended to a Hamilton cycle in Γ. In this paper, inspired by their study, we aim to study the l-HC- extendability of the generalized Petersen graphs GP(n,k). We prove that the generalized Petersen graphs GP(n,k) is 2-HC- extendable, where k=1,2,3.(结合连通图的可扩性和哈密尔顿性，2012年MIKLAVIC等提出了连通图的可扩性。如果连通图Γ包含l- 路且每条l- 路均可扩充为Γ的一条哈密尔顿圈，那么称Γ是l- HC-可扩的。利用连通图的圈的对称差构造哈密尔顿圈，并证明了广义Petersen图GP(n,k)是2- HC-可扩的，其中k=1，2和3。)

Keywords

• generalized petersen graph(广义petersen图)
• l- path(l-路)
• automorphism(自同构)
• hamilton cycle(哈密尔顿圈)
• hc-extendability(hc-可扩性)