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

Fiorini, Stanley ; Gauci, John Baptist

Mathematica Bohemica, Tome 128 (2003) no. 4, pp. 337-347.

Résumé

Guy and Harary (1967) have shown that, for $k\ge 3$, the graph $P[2k,k]$ is homeomorphic to the Möbius ladder ${M_{2k}}$, so that its crossing number is one; it is well known that $P[2k,2]$ is planar. Exoo, Harary and Kabell (1981) have shown hat the crossing number of $P[2k+1,2]$ is three, for $k\ge 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\ge 4$. We extend this result by showing that $P[3k,k]$ also has crossing number $k$ for all $k\ge 4$.

Détail

DOI : 10.21136/MB.2003.134001

Classification : 05C10
Keywords: graph; drawing; crossing number; generalized Petersen graph; Cartesian product