Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
graph; drawing; crossing number; generalized Petersen graph; Cartesian product
graph; drawing; crossing number; generalized Petersen graph; Cartesian product
Summary:
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$.
References:
[1] Exoo G., Harary F., Kabell J.: The crossing numbers of some generalized Petersen graphs. Math. Scand. 48 (1981), 184–188. DOI 10.7146/math.scand.a-11910 | MR 0631334
[2] Fiorini S.: On the crossing number of generalized Petersen graphs. Ann. Discrete Math. 30 (1986), 225–242. MR 0861299 | Zbl 0595.05030
[3] Guy R. K., Harary F.: On the Möbius ladders. Canad. Math. Bull. 10 (1967), 493–496. DOI 10.4153/CMB-1967-046-4 | MR 0224499
[4] Jendrol’ S., Ščerbová M.: On the crossing numbers of ${S_m}\times {C_n}$. Čas. Pěst. Mat. 107 (1982), 225–230. MR 0673046
[5] Kuratowski K.: Sur le problème des courbes gauches en topologie. Fund. Math. 15 (1930), 271–283. DOI 10.4064/fm-15-1-271-283
[6] Richter R. B., Salazar G.: The crossing number of $P(n,3)$. Graphs Combin. 18 (2002), 381–394. DOI 10.1007/s003730200028 | MR 1913677
Search
Partner of
