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,\dots ,u_{n-1}\}$, $W=\{v_0,v_1,\dots ,v_{n-1}\}$; and whose edge set is $\{u_i{u}_{i+1},u_i{v}_i,v_i{v}_{i+k}\mid i=0,1,\dots ,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\ge 4$) is studied, and it is proved that $\text{cr}(P(3k,k))=k$ ($k\ge 4$).