Hyper-Hamiltonian generalized Petersen graphs

AbstractAssume that n and k are positive integers with n≥2k+1. A non-Hamiltonian graph G is hypo-Hamiltonian if G−v is Hamiltonian for any v∈V(G). It is proved that the generalized Petersen graph P(n,k) is hypo-Hamiltonian if and only if k=2 and n≡5(mod6). Similarly, a Hamiltonian graph G is hyper-Hamiltonian if G−v is Hamiltonian for any v∈V(G). In this paper, we will give some necessary conditions and some sufficient conditions for the hyper-Hamiltonian generalized Petersen graphs. In particular, P(n,k) is not hyper-Hamiltonian if n is even and k is odd. We also prove that P(3k,k) is hyper-Hamiltonian if and only if k is odd. Moreover, P(n,3) is hyper-Hamiltonian if and only if n is odd and P(n,4) is hyper-Hamiltonian if and only if n≠12. Furthermore, P(n,k) is hyper-Hamiltonian if k is even with k≥6 and n≥2k+2+(4k−1)(4k+1), and P(n,k) is hyper-Hamiltonian if k≥5 is odd and n is odd with n≥6k−3+2k(6k−2)