The crossing numbers of join products of paths with graphs of order four
Marián Klešč ; Stefan Schrötter
Discussiones Mathematicae Graph Theory, Tome 31 (2011), p. 321-331 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2011-01-01
EUDML-ID : urn:eudml:doc:271023 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1548,
     author = {Mari\'an Kle\v s\v c and Stefan Schr\"otter},
     title = {The crossing numbers of join products of paths with graphs of order four},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {31},
     year = {2011},
     pages = {321-331},
     zbl = {1227.05131},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1548}
}

Marián Klešč; Stefan Schrötter. The crossing numbers of join products of paths with graphs of order four. Discussiones Mathematicae Graph Theory, Tome 31 (2011) pp. 321-331. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1548/

[000] [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.

[001] [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. | Zbl 0403.05037

[002] [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. | Zbl 1113.05027

[003] [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. | Zbl 0536.05016

[004] [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. | Zbl 1053.05032

[005] [6] F. Harary, P.C. Kainen and A.J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers, Nanta Math. 6 (1973) 58-67. | Zbl 0285.05104

[006] [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.

[007] [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. | Zbl 0983.05027

[008] [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. | Zbl 1291.05108

[009] [10] D.J. Kleitman, The crossing number of K5,n, J. Combin. Theory (B) 9 (1971) 315-323. | Zbl 0205.54401

[010] [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. | Zbl 0982.05084

[011] [12] K. Zarankiewicz, On a problem of P. Turán concerning graphs, Fund. Math. 41 (1954) 137-145. | Zbl 0055.41605