Geodesic
The crossing number of the generalized Petersen graph $P[3k,k]$
Mathematica Bohemica, Tome 128 (2003) no. 4, pp. 337-347

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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$.
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$.
DOI : 10.21136/MB.2003.134001
Classification : 05C10
Keywords: graph; drawing; crossing number; generalized Petersen graph; Cartesian product 
Fiorini, Stanley; Gauci, John Baptist. The crossing number of the generalized Petersen graph $P[3k,k]$. Mathematica Bohemica, Tome 128 (2003) no. 4, pp. 337-347. doi: 10.21136/MB.2003.134001
@article{10_21136_MB_2003_134001,
     author = {Fiorini, Stanley and Gauci, John Baptist},
     title = {The crossing number of the generalized {Petersen} graph $P[3k,k]$},
     journal = {Mathematica Bohemica},
     pages = {337--347},
     year = {2003},
     volume = {128},
     number = {4},
     doi = {10.21136/MB.2003.134001},
     mrnumber = {2032472},
     zbl = {1050.05034},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.134001/}
}
TY  - JOUR
AU  - Fiorini, Stanley
AU  - Gauci, John Baptist
TI  - The crossing number of the generalized Petersen graph $P[3k,k]$
JO  - Mathematica Bohemica
PY  - 2003
SP  - 337
EP  - 347
VL  - 128
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.134001/
DO  - 10.21136/MB.2003.134001
LA  - en
ID  - 10_21136_MB_2003_134001
ER  - 
%0 Journal Article
%A Fiorini, Stanley
%A Gauci, John Baptist
%T The crossing number of the generalized Petersen graph $P[3k,k]$
%J Mathematica Bohemica
%D 2003
%P 337-347
%V 128
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.134001/
%R 10.21136/MB.2003.134001
%G en
%F 10_21136_MB_2003_134001

[1] Exoo G., Harary F., Kabell J.: The crossing numbers of some generalized Petersen graphs. Math. Scand. 48 (1981), 184–188. | DOI | MR

[2] Fiorini S.: On the crossing number of generalized Petersen graphs. Ann. Discrete Math. 30 (1986), 225–242. | MR | Zbl

[3] Guy R. K., Harary F.: On the Möbius ladders. Canad. Math. Bull. 10 (1967), 493–496. | DOI | MR

[4] Jendrol’ S., Ščerbová M.: On the crossing numbers of ${S_m}\times {C_n}$. Čas. Pěst. Mat. 107 (1982), 225–230. | MR

[5] Kuratowski K.: Sur le problème des courbes gauches en topologie. Fund. Math. 15 (1930), 271–283. | DOI

[6] Richter R. B., Salazar G.: The crossing number of $P(n,3)$. Graphs Combin. 18 (2002), 381–394. | DOI | MR

Cité par Sources :