The Crossing Number of a Product of Cycles

The crossing number cr(G) of a graph G is the minimal number of pairwise edge crossings over all drawings of G in the plane. (In a drawing edges may cross one another, but only transversally and only if they are nonadjacent.) Let C_n denote the simple cycle of length n. The following conjecture is due to Harary, Kainen and Schwenk.

Conjecture: cr(C_n x C_m) = n(m-2) where m is at most n.

There exists a drawing with this many crossings. Namely, let the m copies of C_n be nested regular n-gons with the same center. For each of the n copies of C_m the vertices lie along a common radii. Complete the C_m using straight line segments except for a slight curve joining the inside n-gon to the outside one.

The difficulty is in showing that every drawing must have at least this many crossings. Generally the hardest case is n = m, with an induction argument covering n > m.

The conjecture is known to be true for some small values. In particular, it is true for n = 3 [RB], n = 4 [BR], and n = 5 [S].

A generalization exploited by Richter and Thomassen [RT] is to consider graphs G whose edges partition into n+m 2-regular subgraphs (not necessarily connected) A_1,...,A_n,B_1,...,B_m such that each A_i intersects each B_j. It is conjectured that the crossing number of any such graph is at least as large as that of C_n x C_m.

References:

[BW] L. Beineke and R. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980) 145-155.

[RB] R. Ringeisen and L. Beineke, The crossing number of C_3 x C_n, J. Combin. Theory B 24 (1978) 134-136.

[RT] R.B. Richter and C. Thomassen, Intersections of curve systems and the crossing number of C_5 x C_5, preprint (1993).

[S] I. Stobert, The crossing number of C_5 x C_n, Honour's Thesis, Carleton University (1993).

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.