PDF

Discussiones Mathematicae Graph Theory 25(1-2) (2005) 197-210
DOI: https://doi.org/10.7151/dmgt.1272

SOME CROSSING NUMBERS OF PRODUCTS OF CYCLES

Marián Klešč

Department of Mathematics
Faculty of Electrical Engineering and Informatics
Technical University, 042 00 Košice, Slovak Republic
e-mail: Marian.Klesc@tuke.sk

Abstract

The exact values of crossing numbers of the Cartesian products of four special graphs of order five with cycles are given and, in addition, all known crossing numbers of Cartesian products of cycles with connected graphs on five vertices are summarized.

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

2000 Mathematics Subject Classification: 05C10, 05C38.

References

[1]	M. Anderson, R.B. Richter and P. Rodney, The crossing number of C6×C6, Congr. Numer. 118 (1996) 97-107.
[2]	M. Anderson, R.B. Richter and P. Rodney, The crossing number of C7×C7, Congr. Numer. 125 (1997) 97-117.
[3]	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.
[4]	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.
[5]	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.
[6]	F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).
[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 products of 5-vertex graphs with paths and cycles, Discuss. Math. Graph Theory 19 (1999) 59-69, doi: 10.7151/dmgt.1085.
[11]	M. Klešč, The crossing number of (K4 −e)×C3, in: Proc. International Scientific Conference on Mathematics (Herl'any, 1999), 106-109, Univ. Technol. Košice, Košice, 2000.
[12]	M. Klešč, The crossing number of K2,3×C3, Discrete Math. 251 (2002) 109-117.
[13]	M. Klešč and A. Kocúrová, The crossing numbers of products of  5-vertex graphs with cycles, Discrete Math. (to appear).
[14]	M. Klešč, R.B. Richter and I. Stobert, The crossing number of C5×Cn, J. Graph Theory 22 (1996) 239-243.
[15]	R.B. Richter and G. Salazar, The crossing number of C6×Cn, Australasian J. Combin. 23 (2001) 135-144.
[16]	R.B. Richter and C. Thomassen, Intersections of curve systems and the crossing number of C5×C5, Discrete Comput. Geom. 13 (1995) 149-159, doi: 10.1007/BF02574034.
[17]	R.D. Ringeisen and L.W. Beineke, The crossing number of C3×Cn, J. Combin. Theory 24 (B) (1978) 134-136.

Received 3 December 2003
Revised 2 February 2005