Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
474327 | Computers & Mathematics with Applications | 2008 | 10 Pages |
Assume that nn and kk are positive integers with n≥2k+1n≥2k+1. A non-Hamiltonian graph GG is hypo-Hamiltonian if G−vG−v is Hamiltonian for any v∈V(G)v∈V(G). It is proved that the generalized Petersen graph P(n,k)P(n,k) is hypo-Hamiltonian if and only if k=2k=2 and n≡5(mod6). Similarly, a Hamiltonian graph GG is hyper-Hamiltonian if G−vG−v is Hamiltonian for any v∈V(G)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)P(n,k) is not hyper-Hamiltonian if nn is even and kk is odd. We also prove that P(3k,k)P(3k,k) is hyper-Hamiltonian if and only if kk is odd. Moreover, P(n,3)P(n,3) is hyper-Hamiltonian if and only if nn is odd and P(n,4)P(n,4) is hyper-Hamiltonian if and only if n≠12n≠12. Furthermore, P(n,k)P(n,k) is hyper-Hamiltonian if kk is even with k≥6k≥6 and n≥2k+2+(4k−1)(4k+1)n≥2k+2+(4k−1)(4k+1), and P(n,k)P(n,k) is hyper-Hamiltonian if k≥5k≥5 is odd and nn is odd with n≥6k−3+2k(6k−2)n≥6k−3+2k(6k−2).