PDF

Discussiones Mathematicae Graph Theory 31(2) (2011) 239-252
DOI: https://doi.org/10.7151/dmgt.1542

ON THE CROSSING NUMBERS OF G^[¯] C_n FOR GRAPHS G ON SIX VERTICES

Emília Drazenská and  Marián Klešč Department of Mathematics Faculty of Electrical Engineering and Informatics Technical University, 042 00 Košice, Slovak Republic e-mail: Emilia.Drazenska@tuke.sk Marian.Klesc@tuke.sk

Abstract

The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. The crossing numbers of G^[¯] C_n for some graphs G on five and six vertices and the cycle C_n are also given. In this paper, we extend these results by determining crossing numbers of Cartesian products G^[¯] C_n for some connected graphs G of order six with six and seven edges. In addition, we collect known results concerning crossing numbers of G ^[¯] C_n for graphs G on six vertices.

Keywords: graph, cycle, drawing, crossing number, Cartesian product.

2010 Mathematics Subject Classification: 05C10.

References

[1]	M. Anderson, R.B. Richter and P. Rodney, The crossing number of C6 ×C6, Congr. Numer. 118 (1996) 97-107.
[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]	A.M. Dean and R.B. Richter, The crossing number of C4 ×C4, J. Graph Theory 19 (1995) 125-129, doi: 10.1002/jgt.3190190113.
[4]	E. Drazenská and M. Klešč, The crossing numbers of products of cycles with 6-vertex trees, Tatra Mt. Math. Publ. 36 (2007) 109-119.
[5]	E. Drazenská, The crossing numbers of G [¯] Cn for the graph G on six vertices, Mathematica Slovaca (to appear).
[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.
[7]	F. Harary, P.C. Kainen and A.J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers, Nanta Math. 6 (1973) 58-67.
[8]	S. Jendrol'   and M. Scerbová, On the crossing numbers of Sm ×Pn and Sm ×Cn, Casopis pro pestování  matematiky 107 (1982) 225-230.
[9]	M. Klešč, On the crossing numbers of Cartesian products of stars and paths or cycles, Mathematica Slovaca 41 (1991) 113-120.
[10]	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.
[11]	M. Klešč, The crossing number of K2,3×C3, Discrete Math. 251 (2002) 109-117, doi: 10.1016/S0012-365X(01)00332-6.
[12]	M. Klešč, Some crossing numbers of products of cycles, Discuss. Math. Graph Theory 25 (2005) 197-210, doi: 10.7151/dmgt.1272.
[13]	M. Klešč, R.B. Richter and I. Stobert, The crossing number of C5 ×Cn, J. Graph Theory 22 (1996) 239-243.
[14]	M. Klešč and A. Kocúrová, The crossing numbers of products of 5-vertex graphs with cycles, Discrete Math. 307 (2007) 1395-1403, doi: 10.1016/j.disc.2005.11.077.
[15]	R.B. Richter and C. Thomassen, Intersection of curve systems and the crossing number of C5 ×C5, Discrete Comp. Geom. 13 (1995) 149-159, doi: 10.1007/BF02574034.
[16]	R.B. Richter and G. Salazar, The crossing number of C6 ×Cn, Australasian J. Combin. 23 (2001) 135-144.
[17]	R D. Ringeisen and L.W. Beineke, The crossing number of C3 ×Cn, J. Combin. Theory (B) 24 (1978) 134-136, doi: 10.1016/0095-8956(78)90014-X.
[18]	W. Zheng, X. Lin, Y. Yang and C. Deng, On the crossing number of Km [¯] Cn and Km,l [¯] Pn, Discrete Appl. Math. 156 (2008) 1892-1907.

Received 30 November 2009
Revised 29 April 2010
Accepted 30 April 2010