The crossing numbers of join products of paths with graphs of order four

Marián Klešč; Stefan Schrötter

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 2, page 321-331
  • ISSN: 2083-5892

Abstract

top
Kulli and Muddebihal [V.R. Kulli, M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97] gave the characterization of all pairs of graphs which join product is planar graph. The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. There are only few results concerning crossing numbers of graphs obtained as join product of two graphs. In the paper, the exact values of crossing numbers for join of paths with all graphs of order four, as well as for join of all graphs of order four with n isolated vertices are given.

How to cite

top

Marián Klešč, and Stefan Schrötter. "The crossing numbers of join products of paths with graphs of order four." Discussiones Mathematicae Graph Theory 31.2 (2011): 321-331. <http://eudml.org/doc/271023>.

@article{MariánKlešč2011,
abstract = {Kulli and Muddebihal [V.R. Kulli, M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97] gave the characterization of all pairs of graphs which join product is planar graph. The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. There are only few results concerning crossing numbers of graphs obtained as join product of two graphs. In the paper, the exact values of crossing numbers for join of paths with all graphs of order four, as well as for join of all graphs of order four with n isolated vertices are given.},
author = {Marián Klešč, Stefan Schrötter},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; drawing; path; crossing number; join product; joint product},
language = {eng},
number = {2},
pages = {321-331},
title = {The crossing numbers of join products of paths with graphs of order four},
url = {http://eudml.org/doc/271023},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Marián Klešč
AU - Stefan Schrötter
TI - The crossing numbers of join products of paths with graphs of order four
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 2
SP - 321
EP - 331
AB - Kulli and Muddebihal [V.R. Kulli, M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97] gave the characterization of all pairs of graphs which join product is planar graph. The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. There are only few results concerning crossing numbers of graphs obtained as join product of two graphs. In the paper, the exact values of crossing numbers for join of paths with all graphs of order four, as well as for join of all graphs of order four with n isolated vertices are given.
LA - eng
KW - graph; drawing; path; crossing number; join product; joint product
UR - http://eudml.org/doc/271023
ER -

References

top
  1. [1] K. Asano, The crossing number of K 1 , 3 , n and K 2 , 3 , n , J. Graph Theory 10 (1986) 1-8, doi: 10.1002/jgt.3190100102. 
  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. Zbl0403.05037
  3. [3] D. Bokal, On the crossing numbers of Cartesian products with paths, J. Combin. Theory (B) 97 (2007) 381-384, doi: 10.1016/j.jctb.2006.06.003. Zbl1113.05027
  4. [4] M.R. Garey and D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic. Discrete Methods 4 (1983) 312-316, doi: 10.1137/0604033. Zbl0536.05016
  5. [5] L.Y. Glebsky and G. Salazar, The crossing number of Cₘ ×Cₙ is as conjectured for n ≥; m(m+1), J. Graph Treory 47 (2004) 53-72, doi: 10.1002/jgt.20016. Zbl1053.05032
  6. [6] F. Harary, P.C. Kainen and A.J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers, Nanta Math. 6 (1973) 58-67. Zbl0285.05104
  7. [7] S. Jendrol' and M. Scerbová, On the crossing numbers of Sₘ ×Pₙ and Sₘ ×Cₙ, Casopis pro pestování matematiky 107 (1982) 225-230. 
  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. Zbl0983.05027
  9. [9] M. Klešč, The join of graphs and crossing numbers, Electronic Notes in Discrete Math. 28 (2007) 349-355, doi: 10.1016/j.endm.2007.01.049. Zbl1291.05108
  10. [10] D.J. Kleitman, The crossing number of K 5 , n , J. Combin. Theory (B) 9 (1971) 315-323. Zbl0205.54401
  11. [11] 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
  12. [12] 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.