The Crossing Number of c, x c n Marian Klesc DEPARTMENT OF MATHEMATICS FACULTY OF ELECTRICAL ENGINEERINGAND INFORMATICS TECHNICAL UNIVERSITY 042 00 KOSICE, SLOVAKIA R. Bruce Richter Ian Stobert DEPARTMENT OF MATHEMATICSAND STATISTICS CARLETON UNIVERSITY OTAWA, CANADA KIS 5B6 ABSTRACT We prove that the crossing number of C5x C, is 372, which is consistent with the general conjecture that the crossing number of C,, x C, is ( m- 2)n,for 3 5 m 5 n. 0 1996 John Wiley & Sons, Inc. The drawing in Figure 1 shows that the crossing number of the Cartesian product C5x Cg of the 5-cycle C5 with the 8-cycle Cs is at most 24. It obviously generalizes to show that the crossing number of C, x C,, is at most ( m - 2)n. Harary et al. [3] have conjectured that, for 3 I m 5 n, this is the actual crossing number. FIGURE 1 Journal of Graph Theory Vol. 22, No. 3, 239-243 (1 996) 0 1996 John Wiley & Sons, Inc. CCC 0364-9024/96/030239-05 240 JOURNAL OF GRAPH THEORY Beineke and Ringeisen verified this conjecture for m 5 4, using induction on n [ l , 51. This required knowing cr(C3x C 3 )= 3 and cr(C4 x C4) = 8. (For a graph G, the crossing number of G is denoted cr(G).)The former is fairly easy and is in [3], while the latter was announced in 1971, but never published. A proof is given in [2]. The point of this paper is to prove the following. Main Theorem. For n 2 5,cr(C5 x C,) = 3n. We interrupt the flow here to give a little background about the preparation of this article. The first author has, independently of [4] and this article, proved that cr(C5 x Cn)= 3n. That paper was submitted to this journal independently of and at roughly the same time as this article. The arguments in that paper overlap substantially with both [4]and this work. Thus it seems most satisfactory to have a single joint paper. The idea of the proof of the Main Theorem is the same as in [l, 51. We proceed by induction on n. The base case is n = 5; this is proved in [4]. The basic idea of the inductive step is either to find a 5-cycle whose edges are crossed a total of at least three times and apply the inductive assumption after deleting the edges of this 5-cycle, or to show directly that if no such 5-cycle exists, then there are at least 3n crossings. In order to help comprehension, color the edges of C5 x C,, red and blue, so that the edges of the n 5-cycles are red and the edges of the 5 n-cycles are blue. A drawing of a graph G is good if no two edges incident with a common vertex have any intersections, no two edges have more than one intersection, any intersection of two edges is a crossing rather than tangential, and no three edges have a common crossing. It is a routine exercise to show there is a good drawing of G having fewest pairwise intersections of edges (i.e., the drawing attains the crossing number). We begin with the following observation. Lemma 1. Let be a good drawing of CS x C, in the plane, with n 2 3. If two red 5-cycles intersect in a, then one of them has its edges crossed at least three times. Proof. Call the intersecting 5-cycles R1 and R2. By the Jordan Curve Theorem, there are at least two crossings of R1 and R2. If either they have more than two points in common or one of them has a self-intersection, then we are done. Therefore, we can assume that they are both simple closed curves in the plane with exactly two points z, y in common. The two curves correspond to four arcs A l , A2,A S ,A4, in this cyclic order around z, from z to y. Then R1 = Al UA3 and Ra = A2 UA4. It is not possible that two of these arcs contain no vertices at all, since that means two edges intersect in at least the two points 2 and y. For sake of definiteness, assume A l , A2, A3 all contain a vertex of G. Let R3 be any other of the red 5-cycles. If it intersects either of R1 and R2, then we are done, so we can assume it is contained in one of the four regions complementary to R1 U Ra. If R3 and A2 are in different regions complementary to R1, then there is a blue n-cycle that contains exactly one vertex in each of A2,R1, and RY.This cycle must cross R1 at some point that is not a vertex, yielding the desired third intersection. We can assume, then, that R3 lies in the region bounded by A1 U Aa. There is a blue n-cycle that contains exactly one vertex in each of A3 and Rd and at most one vertex in THE CROSSING NUMBER OF C5 x CN 241 Al u A2, Therefore, it must cross A1 u A:! at some point other than a vertex, yielding the desired third intersection of either R1 or Rz. I Lemma 2. Let @ be a good drawing of C, x C, in the plane, with n 2 3. If in @ the red 5-cycles are pairwise disjoint and there are red 5-cycles R1,R2,R3 such that R2 and R3 are in different regions of the plane complementary to R1, then R1 is crossed at least five times. ProoJ There are five disjoint blue n-cycles, each of which has exactly one vertex in each of the cycles R1,Rz, R3.Thus, there are at least 10 points of these blue n-cycles in R1,and at most 5 of these points are vertices. Therefore, there are at least five crossings of R1,as claimed. I The following is the heart of the proof of the Main Theorem. Lemma 3. Suppose CP is a good drawing of Cs x C, such that none of the red 5-cycles is crossed three or more times. Then @ has at least 3n crossings. We postpone the proof of this momentarily, to show that it completes the proof of the Main Theorem. Proof of Main Theorem. We proceed by induction on n , with the base case n = 5 being the main result in [4].So assume n > 5 and let CP be an optimal drawing of Cs x C,. If there is a red 5-cycle C that has its edges in at least 3 crossings in @, then delete the edges of C to create a drawing (of a subdivision) of C5 x Cn,-l. Inductively, this drawing has at least 3(n - 1) crossings, so that CP has at least 3(n - 1) + 3 = 3n crossings, as required. On the other hand, if no red 5-cycle has at least 3 crossings, then Lemma 3 implies that CP has at least 3n crossings, as required. I Thus, the proof of the Main Theorem will be complete with the proof of Lemma 3. Proof o f k m m a 3. By Lemmas 1 and 2, the red 5-cycles are pairwise disjoint and no one separates any of the other two. These 5-cycles are naturally cyclically ordered as Q1,Q2,. . . , Q,, so that each of the blue n-cycles has an edge that joins a vertex of Qz-l with a vertex of Q,, for i = 2, . . . ,n, where the indices are read modulo n. For i = 1 , 2 , . . . ,n, let H, denote the subgraph of Cs x C, induced by the vertices in QZp1U Q,, again the indices being read modulo n. Thus, H, has 10 red edges and 5 blue edges, every red edge is in two of the H, and every blue edge is in exactly one of the H,. Theforce f ( H , ) of H, is the total number of crossings of the following types: (1) a crossing of a blue edge in H , with an edge in Q, U Q,+l; with an edge in H,; (2) a crossing of a blue edge in (3) a crossing of a blue edge in H, with a blue edge in H,; and (4) a self-intersection of Q,. 242 JOURNAL OF GRAPH THEORY A moment’s thought shows that no crossing counted in f ( H i ) is counted in f ( H j )if i # is at least Cl<iilL f ( H , ) . Therefore, in order to complete the proof of Lemma 3, it suffices to show that, foreach i = 1 , 2 , . . . , n. f ( H , ) 2 3. By the symmetry, it clearly suffices to show that f ( H 1 ) 2 3. Since the red 5-cycles are disjoint and no red 5-cycle separates two other red 5-cycles, we can assume that, for each red 5-cycle Q, all the other red 5-cycles are in the infinite region determined by @(Q).(We remark that @ ( Q )might have several finite regions.) Assume first that there is a blue edge of H1 that crosses Q2. Because no two of Qn,& I , and Q2 intersect and no one separates the other two, the blue edge of H1 that crosses Q2 does so twice. Both of these are counted in f(H1),so there can be no other crossings counted in f ( H l ) or we are done. In particular, Qz crosses no other blue edge of H1 and if in H I we contract Qn to a point, the result is a crossing-free drawing of a graph, which we shall call H i . Clearly, H: is isomorphic to a wheel with five rim vertices. Let v be the vertex of Hi corresponding to QT1.In cyclic order, let wl,. . . , v5 be the ~,i = vertices of Q1. The faces of H { are bounded by Q1 and the triangles w ~ ~ w , +for 1 , 2 , . . . , 5 , where the indices are read modulo 5. Now Q2 crosses exactly one blue edge of H i , which we may assume is wvl. It follows that Q2 is contained in the faces of Hi bounded by the triangles vvl w2 and vv5v1. In any case, the vertices w 3 and w4 of Q2 joined by blue edges to v3 and v4, respectively, are separated from v3 and v4 by the cycle wv2v1v5. Therefore, both these edges must cross this cycle. Thus, there are at least two crossings of blue edges of H 2 with edges of H I , so that f ( H 1 )is at least four, which is more than enough. It follows that we can assume that no blue edge of H1 crosses Q2. Consider any blue edge e = uv of H I , with u E V(Q,) and w E V(Q1).As we proceed from w to u along e , let a be that first point in e that is in Qn (uis such a point) and let b be the last point in e before a that is in Q1 (v is such a point). Let Te be the segment of e from a to b. Note that if b # v, then e crosses Q1 at b. Let 7H1 denote the subset of the plane consisting of Qn,Q1, and all the r e , for e a blue edge of H I . Since Q 2 is disjoint from 7H1 and is not separated by either Qn or Q1 from the other, that contains Q2 and whose boundary contains some of the there is a region R of T H ~ blue part of 7H1. Suppose there are k vertices of Q1 incident with R. Then there must be at least 5 - k crossings of blue edges of H2 with the boundary of this region. Thus, the force of H1 is at least 5 - k . Consequently, if k 5 2, then f(H1)2 3. We now consider the possibility that k 2 3. We must find an additional 3 - (5- k ) = k -2 crossings that contribute to the force of H I . We note that the boundary of R is a simple closed curve whose intersection with Q1 is a connected segment. As we trace the portion of the boundary of R in Q1, we begin at a point (say pl) and, . . , wl traversing edges and possibly self-intersections of Q1, we go through vertices wl, w2,. of Q1, in this order, and finally finish at a point p 2 . We remark that p l and p 2 need not be vertices of Q1, but in any case 1 2 k - 2. The vertices w1,. . . ,wl are in the interior of the segment of Q1 that is in the boundary of R. Consider the blue edge ei from Qn to w i , i = 1,. . . ,1. We claim that if bi is the end For if bi = wi, then the segment rei goes from wi to Q,. point of Tei on Ql, then b, # wi. But then it must go through the region R and we have incorrectly identified the region R. Thus, b, # wi and ei crosses Q1 at bi. Therefore, there are an additional 1 2 k - 2 crossings that contribute to the force of H I , so f(H1)2 3, as required. I j. Therefore, the number of crossings in THE CROSSING NUMBER OF Cs x C N 243 References [ 11 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. [2] A. M. Dean and R. B. Richter, The crossing number of C4 x C4. J. Graph Theory, 19 (1995) 125-129. [3] F. Harary, P. C. Kainen, and A. J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers. Nanta Math. 6 (1973) 5 8 4 7 . [4] R. B. Richter and C. Thomassen, Intersection of curve systems and the crossing number of Cs x Cg. Discrete Comp. Geom. 13 (1995) 149-159. [5] R. D. Ringeisen and L. W. Beineke, The crossing number of C3 x C,. J. Combinat. Theory 24 (1978) 1 3 4 136. Received December 19, 1994

1/--страниц