Previous |  Up |  Next


Title: The crossing number of the generalized Petersen graph $P[3k,k]$ (English)
Author: Fiorini, Stanley
Author: Gauci, John Baptist
Language: English
Journal: Mathematica Bohemica
ISSN: 0862-7959 (print)
ISSN: 2464-7136 (online)
Volume: 128
Issue: 4
Year: 2003
Pages: 337-347
Summary lang: English
Category: math
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$. (English)
Keyword: graph
Keyword: drawing
Keyword: crossing number
Keyword: generalized Petersen graph
Keyword: Cartesian product
MSC: 05C10
idZBL: Zbl 1050.05034
idMR: MR2032472
DOI: 10.21136/MB.2003.134001
Date available: 2009-09-24T22:10:31Z
Last updated: 2020-07-29
Stable URL:
Reference: [1] Exoo G., Harary F., Kabell J.: The crossing numbers of some generalized Petersen graphs.Math. Scand. 48 (1981), 184–188. MR 0631334, 10.7146/math.scand.a-11910
Reference: [2] Fiorini S.: On the crossing number of generalized Petersen graphs.Ann. Discrete Math. 30 (1986), 225–242. Zbl 0595.05030, MR 0861299
Reference: [3] Guy R. K., Harary F.: On the Möbius ladders.Canad. Math. Bull. 10 (1967), 493–496. MR 0224499, 10.4153/CMB-1967-046-4
Reference: [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
Reference: [5] Kuratowski K.: Sur le problème des courbes gauches en topologie.Fund. Math. 15 (1930), 271–283. 10.4064/fm-15-1-271-283
Reference: [6] Richter R. B., Salazar G.: The crossing number of $P(n,3)$.Graphs Combin. 18 (2002), 381–394. MR 1913677, 10.1007/s003730200028


Files Size Format View
MathBohem_128-2003-4_1.pdf 389.8Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo