The Hamiltonian and Hypohamiltonian of Generalized Petersen Graph (GP_(n,9))

Abstract

The study of Hamiltonian and Hypohamiltonian properties in the generalized Petersen graph GP_{n,k} is interesting due to the unique structure and characteristics of these graphs. The method employed in this study involves searching for Hamiltonian cycles within the generalized Petersen graph GP_{n,9}. Not all of GP_{n,9} graphs are Hamiltonian. For certain values of n, if the graph does not contain a Hamiltonian cycle, then one vertex should be removed from the graph to become Hamiltonian or neither. This research specifically investigates the Hypohamiltonian property of GP_{n,9}. The results show that for n ≡ 3 (mod 19) and n ≡ 5 (mod 19), GP_{n,9} is Hamiltonian. Meanwhile, for n ≡ 0 (mod 19), GP_{n,9} is Hypohamiltonian. Furthermore, for n ≡ 1 (mod 19), n ≡ 2 (mod 19), and n ≡ 4 (mod 19), GP_{n,9} is neither Hamiltonian nor Hypohamiltonian.

Keywords

• simple graph
• petersen graph
• generalized petersen graph
• hamiltonian
• hypohamiltonian