The crossing number of the generalized Petersen graph P[3k, k]

Abstract

Guy and Harary (1967) have shown that, for k ≥ 3, the graph P[2k, k] is homeomorphic to the Möbius ladder M2k, so that its crossing number is one; it is well known that P[2k, 2] is planar. Exoo, Harary and Kabell (1981) have shown that the crossing number of P[2k + 1, 2] is three, for k ≥ 2. Fiorini (1986) and Richter and Salazar (2002) have shown that P[9, 3] has crossing number two and that P[3k, 3] has crossing number k, provided k ≥ 4. We extend this result by showing that P[3k, k] also has crossing number k for all k ≥ 4.