close

Вход

Забыли?

вход по аккаунту

?

192

код для вставкиСкачать
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
Документ
Категория
Без категории
Просмотров
2
Размер файла
276 Кб
Теги
192
1/--страниц
Пожаловаться на содержимое документа