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

Stanley Fiorini; John Baptist Gauci

Mathematica Bohemica (2003)

  • Volume: 128, Issue: 4, page 337-347
  • ISSN: 0862-7959

Abstract

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

How to cite

top

Fiorini, Stanley, and Gauci, John Baptist. "The crossing number of the generalized Petersen graph $P[3k,k]$." Mathematica Bohemica 128.4 (2003): 337-347. <http://eudml.org/doc/249227>.

@article{Fiorini2003,
abstract = {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$.},
author = {Fiorini, Stanley, Gauci, John Baptist},
journal = {Mathematica Bohemica},
keywords = {graph; drawing; crossing number; generalized Petersen graph; Cartesian product; graph; drawing; crossing number; generalized Petersen graph; Cartesian product},
language = {eng},
number = {4},
pages = {337-347},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The crossing number of the generalized Petersen graph $P[3k,k]$},
url = {http://eudml.org/doc/249227},
volume = {128},
year = {2003},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 128
IS - 4
SP - 337
EP - 347
AB - 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$.
LA - eng
KW - graph; drawing; crossing number; generalized Petersen graph; Cartesian product; graph; drawing; crossing number; generalized Petersen graph; Cartesian product
UR - http://eudml.org/doc/249227
ER -

References

top
  1. The crossing numbers of some generalized Petersen graphs, Math. Scand. 48 (1981), 184–188. (1981) MR0631334
  2. On the crossing number of generalized Petersen graphs, Ann. Discrete Math. 30 (1986), 225–242. (1986) Zbl0595.05030MR0861299
  3. 10.4153/CMB-1967-046-4, Canad. Math. Bull. 10 (1967), 493–496. (1967) MR0224499DOI10.4153/CMB-1967-046-4
  4. On the crossing numbers of S m × C n , Čas. Pěst. Mat. 107 (1982), 225–230. (1982) MR0673046
  5. Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930), 271–283. (1930) 
  6. 10.1007/s003730200028, Graphs Combin. 18 (2002), 381–394. (2002) MR1913677DOI10.1007/s003730200028

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.