On the Crossing Number of the Generalized Petersen Graph \(P(3k, k)\)

Abstract

The generalized Petersen graph \(P(n, k)\) is the graph whose vertex set is \(U \cup W\), where \(U = \{u_0, u_1, \ldots, u_{n-1}\}\), \(W = \{v_0, v_1, \ldots, v_{n-1}\}\); and whose edge set is \(\{u_iu_{i+1},u_iv_{i}, v_iv_{i+k} \mid i = 0, 1, \ldots, n-1\}\), where \(n, k\) are positive integers, addition is modulo \(n\), and \(2 < k < n/2\). G. Exoo, F. Harary, and J. Kabell have determined the crossing number of \(P(n, 2)\); Richter and Salazar have determined the crossing number of the generalized Petersen graph \(P(n, 3)\). In this paper, the crossing number of the generalized Petersen graph \(P(3k, k)\) (\(k \geq 4\)) is studied, and it is proved that \(\text{cr}(P(3k,k)) = k\) (\(k \geq 4\)).