The Crossing Numbers of Products of Path with Graphs of Order Six

Marián Klešč; Jana Petrillová

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 3, page 571-582
  • ISSN: 2083-5892

Abstract

top
The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartesian products G⃞Pn for graphs G of order six are studied. Let H denote the unique tree of order six with two vertices of degree three. The main contribution is that the crossing number of the Cartesian product H⃞Pn is 2(n − 1). In addition, the crossing numbers of G⃞Pn for fourty graphs G on six vertices are collected

How to cite

top

Marián Klešč, and Jana Petrillová. "The Crossing Numbers of Products of Path with Graphs of Order Six." Discussiones Mathematicae Graph Theory 33.3 (2013): 571-582. <http://eudml.org/doc/267699>.

@article{MariánKlešč2013,
abstract = {The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartesian products G⃞Pn for graphs G of order six are studied. Let H denote the unique tree of order six with two vertices of degree three. The main contribution is that the crossing number of the Cartesian product H⃞Pn is 2(n − 1). In addition, the crossing numbers of G⃞Pn for fourty graphs G on six vertices are collected},
author = {Marián Klešč, Jana Petrillová},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; drawing; crossing number; Cartesian product; path; tree},
language = {eng},
number = {3},
pages = {571-582},
title = {The Crossing Numbers of Products of Path with Graphs of Order Six},
url = {http://eudml.org/doc/267699},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Marián Klešč
AU - Jana Petrillová
TI - The Crossing Numbers of Products of Path with Graphs of Order Six
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 3
SP - 571
EP - 582
AB - The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartesian products G⃞Pn for graphs G of order six are studied. Let H denote the unique tree of order six with two vertices of degree three. The main contribution is that the crossing number of the Cartesian product H⃞Pn is 2(n − 1). In addition, the crossing numbers of G⃞Pn for fourty graphs G on six vertices are collected
LA - eng
KW - graph; drawing; crossing number; Cartesian product; path; tree
UR - http://eudml.org/doc/267699
ER -

References

top
  1. [1] L.W. Beineke and 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[Crossref] Zbl0403.05037
  2. [2] D. Bokal, On the crossing number of Cartesian products with paths, J. Combin. Theory (B) 97 (2007) 381-384. doi:10.1016/j.jctb.2006.06.003[Crossref] Zbl1113.05027
  3. [3] S. Jendrol’ and M. Ščerbová, On the crossing numbers of Sm × Pn and Sm × Cn, ˇ Casopis Pro P ˇ estov´ an´ı Matematiky 107 ( 1982) 225-230. Zbl0509.05035
  4. [4] M. Klešč, The crossing numbers of Cartesian products of stars and paths or cycles, Math. Slovaca 41 (1991) 113-120. Zbl0755.05067
  5. [5] M. Klešč, The crossing numbers of products of paths and stars with 4-vertex graphs, J. Graph Theory 18 (1994) 605-614. Zbl0808.05038
  6. [6] M. Klešč, The crossing number of K2,3 ×Pn and K2,3 ×Sn, Tatra Mt. Math. Publ. 9 (1996) 51-56. 
  7. [7] M. Klešč, The crossing numbers of products of 4-vertex graphs with paths and cycles, Discuss. Math. Graph Theory 19 (1999) 59-69. doi:10.7151/dmgt.1085[Crossref] 
  8. [8] M. Klešč, The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Math. 233 (2001) 353-359. doi:10.1016/S0012-365X(00)00251-X[Crossref][WoS] Zbl0983.05027
  9. [9] D. Kravecová, The crossing number of P2 5 × Pn, Creat. Math. Inform. 28 (2012) 49-56. 
  10. [10] Y.H. Peng and Y.C. Yiew, The crossing number of P(3, 1)×Pn, Discrete Math. 306 (2006) 1941-1946. doi:10.1016/j.disc.2006.03.058[Crossref] 
  11. [11] J. Wang and Y. Huang, The crossing number of K2,4 ×Pn, Acta Math. Sci.,Ser. A, Chin. Ed. 28 (2008) 251-255. 
  12. [12] L. Zhao, W. He, Y. Liu and X. Ren, The crossing number of two Cartesian products, Int. J. Math. Comb. 1 (2007) 120-127. Zbl1140.05025
  13. [13] W. Zheng, X. Lin, Y. Yang and Ch. Cui, On the crossing number of Km⃞Pn, Graphs Combin. 23 (2007) 327-336. doi:10.1007/s00373-007-0726-z [Crossref] 

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.