Discussiones Mathematicae Graph Theory 31(2) (2011)
321-331
doi: 10.7151/dmgt.1548
Marián Klešč and Stefan Schrötter
Department of Mathematics |
Keywords: graph, drawing, path, crossing number, join product.
2010 Mathematics Subject Classification: 05C10, 05C38.
[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] | 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. |
[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. |
[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. |
[5] | L.Y. Glebsky and G. Salazar, The crossing number of C_{m} ×C_{n} is as conjectured for n ≥ m(m+1), J. Graph Treory 47 (2004) 53-72, doi: 10.1002/jgt.20016. |
[6] | F. Harary, P.C. Kainen and A.J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers, Nanta Math. 6 (1973) 58-67. |
[7] | S. Jendrol' and M. Scerbová, On the crossing numbers of S_{m} ×P_{n} and S_{m} ×C_{n}, Casopis pro pestování matematiky 107 (1982) 225-230. |
[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. |
[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. |
[10] | D.J. Kleitman, The crossing number of K_{5,n}, J. Combin. Theory (B) 9 (1971) 315-323. |
[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. |
[12] | K. Zarankiewicz, On a problem of P. Turán concerning graphs, Fund. Math. 41 (1954) 137-145. |
Received 30 November 2009
Revised 22 June 2010
Accepted 28 June 2010