The maximum genus of the generalized Petersen Graph, GP (n, k) for the cases k = 1, 2

In Topological graph theory, the maximum genus of graphs has been a fascinating subject. For a simple connected graph G, the maximum genus γM (G) is the largest genus of an orientable surface on which G has a 2-cell embedding. γM (G) has the upper bound, γM (G) ≤β/2, where β (G) denotes the Betti number and G is said to be upper embeddable if the equality holds. In this study, the maximum genus of GP (n, k) is established as γM (GP (n, k) ) = (n+1) /2 for k = 1 and k = 2 by proving the upper embeddability of generalized Petersen graph, GP (n, k) for the cases k = 1 and k = 2. The proof is done by obtaining spanning trees T and examining the components in the edge complements GP (n, k) for the cases k = 1 and k = 2 of GP (n, k).