The crossing numbers of products of a 5-vertex graph with paths and cycles

Marián Klešč

Discussiones Mathematicae Graph Theory (1999)

  • Volume: 19, Issue: 1, page 59-69
  • ISSN: 2083-5892

Abstract

top
There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with "small" graphs. Let H be the 5-vertex graph defined from K₅ by removing three edges incident with a common vertex. In this paper, we extend the earlier results to the Cartesian products of H × Pₙ and H × Cₙ, showing that in the general case the corresponding crossing numbers are 3n-1, and 3n for even n or 3n+1 if n is odd.

How to cite

top

Marián Klešč. "The crossing numbers of products of a 5-vertex graph with paths and cycles." Discussiones Mathematicae Graph Theory 19.1 (1999): 59-69. <http://eudml.org/doc/270306>.

@article{MariánKlešč1999,
abstract = {There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with "small" graphs. Let H be the 5-vertex graph defined from K₅ by removing three edges incident with a common vertex. In this paper, we extend the earlier results to the Cartesian products of H × Pₙ and H × Cₙ, showing that in the general case the corresponding crossing numbers are 3n-1, and 3n for even n or 3n+1 if n is odd.},
author = {Marián Klešč},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; drawing; crossing number; path; cycle; Cartesian product; planar drawing},
language = {eng},
number = {1},
pages = {59-69},
title = {The crossing numbers of products of a 5-vertex graph with paths and cycles},
url = {http://eudml.org/doc/270306},
volume = {19},
year = {1999},
}

TY - JOUR
AU - Marián Klešč
TI - The crossing numbers of products of a 5-vertex graph with paths and cycles
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 1
SP - 59
EP - 69
AB - There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with "small" graphs. Let H be the 5-vertex graph defined from K₅ by removing three edges incident with a common vertex. In this paper, we extend the earlier results to the Cartesian products of H × Pₙ and H × Cₙ, showing that in the general case the corresponding crossing numbers are 3n-1, and 3n for even n or 3n+1 if n is odd.
LA - eng
KW - graph; drawing; crossing number; path; cycle; Cartesian product; planar drawing
UR - http://eudml.org/doc/270306
ER -

References

top
  1. [1] D. Archdeacon, R.B. Richter, On the parity of crossing numbers, J. Graph Theory 12 (1988) 307-310, doi: 10.1002/jgt.3190120302. Zbl0659.05043
  2. [2] L.W. Beineke, R.D. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980) 145-155, doi: 10.1002/jgt.3190040203. Zbl0403.05037
  3. [3] F. Harary, Graph Theory (Addison - Wesley, Reading, MA, 1969). 
  4. [4] S. Jendrol', M. S cerbová, On the crossing numbers of Sₘ × Pₙ and Sₘ × Cₙ, Casopis pro pestování matematiky 107 (1982) 225-230. 
  5. [5] M. Klešč, On the crossing numbers of Cartesian products of stars and paths or cycles, Mathematica Slovaca 41 (1991) 113-120. Zbl0755.05067
  6. [6] M. Klešč, The crossing numbers of products of paths and stars with 4-vertex graphs, J. Graph Theory 18 (1994) 605-614. Zbl0808.05038
  7. [7] M. Klešč, The crossing numbers of certain Cartesian products, Discuss. Math. Graph Theory 15 (1995) 5-10, doi: 10.7151/dmgt.1001. Zbl0828.05028
  8. [8] M. Klešč, The crossing number of K 2 , 3 × P ₙ and K 2 , 3 × S ₙ , Tatra Mountains Math. Publ. 9 (1996) 51-56. 
  9. [9] M. Klešč, R.B. Richter, I. Stobert, The crossing number of C₅ × Cₙ, J. Graph Theory 22 (1996) 239-243. Zbl0854.05036
  10. [10] A.T. White, L.W. Beineke, Topological graph theory, in: Selected Topics in Graph Theory (Academic Press, London, 1978) 15-49. 

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.