On the Crossing Numbers of Cartesian Products of Stars and Graphs of Order Six

Marián Klešč; Štefan Schrötter

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 3, page 583-597
  • ISSN: 2083-5892

Abstract

top
The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. According to their special structure, the class of Cartesian products of two graphs is one of few graph classes for which some exact values of crossing numbers were obtained. The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. Moreover, except of six graphs, the crossing numbers of Cartesian products G⃞K1,n for all other connected graphs G on five vertices are known. In this paper we are dealing with the Cartesian products of stars with graphs on six vertices. We give the exact values of crossing numbers for some of these graphs and we summarise all known results concerning crossing numbers of these graphs. Moreover, we give the crossing number of G1⃞T for the special graph G1 on six vertices and for any tree T with no vertex of degree two as well as the crossing number of K1,n⃞T for any tree T with maximum degree five.

How to cite

top

Marián Klešč, and Štefan Schrötter. "On the Crossing Numbers of Cartesian Products of Stars and Graphs of Order Six." Discussiones Mathematicae Graph Theory 33.3 (2013): 583-597. <http://eudml.org/doc/267804>.

@article{MariánKlešč2013,
abstract = {The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. According to their special structure, the class of Cartesian products of two graphs is one of few graph classes for which some exact values of crossing numbers were obtained. The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. Moreover, except of six graphs, the crossing numbers of Cartesian products G⃞K1,n for all other connected graphs G on five vertices are known. In this paper we are dealing with the Cartesian products of stars with graphs on six vertices. We give the exact values of crossing numbers for some of these graphs and we summarise all known results concerning crossing numbers of these graphs. Moreover, we give the crossing number of G1⃞T for the special graph G1 on six vertices and for any tree T with no vertex of degree two as well as the crossing number of K1,n⃞T for any tree T with maximum degree five.},
author = {Marián Klešč, Štefan Schrötter},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; drawing; crossing number; Cartesian product; join product; star},
language = {eng},
number = {3},
pages = {583-597},
title = {On the Crossing Numbers of Cartesian Products of Stars and Graphs of Order Six},
url = {http://eudml.org/doc/267804},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Marián Klešč
AU - Štefan Schrötter
TI - On the Crossing Numbers of Cartesian Products of Stars and Graphs of Order Six
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 3
SP - 583
EP - 597
AB - The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. According to their special structure, the class of Cartesian products of two graphs is one of few graph classes for which some exact values of crossing numbers were obtained. The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. Moreover, except of six graphs, the crossing numbers of Cartesian products G⃞K1,n for all other connected graphs G on five vertices are known. In this paper we are dealing with the Cartesian products of stars with graphs on six vertices. We give the exact values of crossing numbers for some of these graphs and we summarise all known results concerning crossing numbers of these graphs. Moreover, we give the crossing number of G1⃞T for the special graph G1 on six vertices and for any tree T with no vertex of degree two as well as the crossing number of K1,n⃞T for any tree T with maximum degree five.
LA - eng
KW - graph; drawing; crossing number; Cartesian product; join product; star
UR - http://eudml.org/doc/267804
ER -

References

top
  1. 1] K. Asano, The crossing number of K1,3,n and K2,3,n, J. Graph Theory 10 (1986) 1-8. doi:10.1002/jgt.3190100102[Crossref] 
  2. [2] 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
  3. [3] 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
  4. [4] D. Bokal, On the crossing numbers of Cartesian products with trees, J. Graph Theory 56 (2007) 287-300. doi:10.1002/jgt.20258[Crossref] Zbl1128.05017
  5. [5] M. Draženská and M. Klešč, The crossing numbers of products of the graph K2,2,2 with stars, Carpathian J. Math. 24 (2008) 327-331. Zbl1249.05331
  6. [6] L.Y. Glebsky and G. Salazar, The crossing number of Cm ×Cn is as conjectured for n ≥ m(m + 1), J. Graph Theory 47 (2004) 53-72. doi:10.1002/jgt.20016[Crossref] Zbl1053.05032
  7. [7] F. Harary, P.C. Kainen and A.J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers, Nanta Math 6 (1973) 58-67. Zbl0285.05104
  8. [8] X. He, The crossing number of Cartesian products of stars with 5-vertex graphs, in: 2010 International Conference on Computational Intelligence and Software Engineering, CiSE 2010, Wuhan, December 2010. 
  9. [9] P.T. Ho, The crossing number of K2,2,2,n, Far East J. Appl. Math. 30 (2008) 43-69. Zbl1148.05028
  10. [10] Y. Huang and T. Zhao, The crossing number of K1,4,n, Discrete Math. 308 (2008) 1634-1638. doi:10.1016/j.disc.2006.12.002[Crossref] 
  11. [11] 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. 
  12. [12] D.J. Kleitman, The crossing number of K5,n, J. Combin. Theory (B) 9 (1971) 315-323. Zbl0205.54401
  13. [13] M. Klešč, The crossing numbers of Cartesian products of stars and paths or cycles, Math. Slovaca 41 (1991) 113-120. Zbl0755.05067
  14. [14] M. Klešč, The crossing numbers of products of paths and stars with 4-vertex graphs, J. Graph Theory 18 (1994) 605-614. Zbl0808.05038
  15. [15] M. Klešč, The crossing number of K2,3 ×Pn and K2,3 ×Sn, Tatra Mt. Math. Publ. 9 (1996) 51-56. 
  16. [16] M. Klešč, On the crossing numbers of products of stars and graphs of order five, Graphs Combin. 17 (2001) 289-294. doi:10.1007/s003730170042[Crossref] Zbl0977.05038
  17. [17] M. Klešč, The join of graphs and crossing numbers, Electron. Notes Discrete Math. 28 (2007) 349-355. doi:10.1016/j.endm.2007.01.049[Crossref] Zbl1291.05108
  18. [18] M. Klešč, On the crossing numbers of Cartesian products of stars and graphs on five vertices, Combinatorial Algorithms, Springer, LNCS 5874 (2009) 324-333. doi:10.1007/978-3-642-10217-2 32[Crossref] Zbl1267.05225
  19. [19] V.R. Kulli and M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97. Zbl0982.05084
  20. [20] S. Lü and Y. Huang, On the crossing numner of K5 × Sn, J. Math. Res. Expo. 28 (2008) 445-459. 
  21. [21] H. Mei and Y. Huang, The crossing number of K1,5,n, Internat. J. Math. Combin. 1 (2007) 33-44. Zbl1140.05023
  22. [22] K. Zarankiewicz, On a problem of P. Turán concerning graphs, Fund. Math 41 (1954) 137-145 Zbl0055.41605

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.