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.

Send comments to *dan.archdeacon@uvm.edu
*

August, 1995. Last modified September 2000