Забыли?

?

# 229

код для вставкиСкачать
```Partitioning a Graph into
Two Square-Cycles
Genghua Fan
DEPARTMENT 0F MATHEMATICS
ARIZONA STATE UNIVERSITY
TEMPE, AZ 85287
e-mai1:fanQmath./a.asu.edu
ABSTRACT
A square-cycle is the graph obtained from a cycle by joining every pair of vertices of
distance two in the cycle. The length of a square-cycle is the number of vertices in
it. Let G be a graph on n vertices with minimum degree a t least \$n and let c be the
maximum length of a square-cycle in G. Posa and Seymour conjectured that c = n.
In this paper, it is proved that either c = n or
5 c 5 \$n. As an application of this
result, it is shown that G has two vertex-disjoint square-cycles C1 and Cz such that
V ( G )= V ( c 1 )U V ( c 2 ) .0 1996 John Wiley & Sons, Inc.
in
1. INTRODUCTION
All graphs considered are simple and undirected. S(G) denotes the minimum degree of a
graph G. Let P be a path (cycle). The kth power of P is the graph obtained from P by
joining every pair of vertices with distance at most k in P. An edge is called a k-chord of
P if it joins two vertices of distance k in P. We call the 2nd power of P a square-path
(-cycle). (For technical reasons, the empty set is regarded as a square-cycle.) A hamilronian
square-path (-cycle) is a square-path (-cycle) that contains all the vertices of the graph.
A classical theorem of Dirac [l] states that if G is a graph on n vertices with 6(G) 2 :,
then G contains a hamiltonian cycle. In 1963 Posa (see Erdos [2]) conjectured that if
S(G) 2 \$n,then G contains a hamiltonian square-cycle. In 1973 Seymour [6] introduced
* Research partially supported by Office of Naval Research Grant N00014-90-J-1206.
Journal of Graph Theory Vol. 23, No. 3, 241-256 (1996)
0 1996 John Wiley & Sons, Inc.
CCC 0364-9024/96/030241-16
242 JOURNAL OF GRAPH THEORY
the more general conjecture that if S(G) 2 [ k / ( k +l ) ] n then
,
G contains the kth power of a
hamiltonian cycle. As Seymour pointed out, if his conjecture is true, the proof is likely to
be very hard, because it implies the remarkably difficult theorem of Hajnal and Szemeredi
[6] that any graph G with maximum degree A can be properly colored with A + 1 colors
so that no two color classes differ in size by more than one. There has been progress on
Posa’s conjecture. Fan and Haggkvist [3] proved that if S(G) 2 :n, then G contains a
hamiltonian square-cycle. Fan and Kierstead [4] showed that for every E > 0, there exists
m such that if n > m and S(G) > [(2 ~ ) / 3 ] nthen
, G contains a hamiltonian squarecycle. They [5] also proved that if 6(G) 2 [(2n- 1)/3], then G contains a hamiltonian
square-path.
If H is a subgraph of G , G - H denotes the subgraph obtained by deleting all the
, H(z)
vertices of H together with all the edges with at least one end in H . For z E V ( G ) N
is the set, and d ( z , H ) the number, of vertices in H that are joined to z. We denote
) N H ( z )n N H ( ~ )(In
. the case
by zy the edge with ends z and y and define N ~ ( z y =
that H = G, we simply use N(x),d(z),and N(zy).) If F is another subgraph of G,
we define d ( F , H ) = C v E I / ( F ) d ( ~ , H
By) . the definition, d ( F , H ) = d ( H , F ) , and if
V ( F )n V ( H ) = 0, then d ( F ,H ) is simply the number of edges with one end in F and the
other end in H . The complete graph on m vertices is denoted by K,,,.
The third power of a path is also called a cube-path. If P = z1z2. . . z pis a square-path
(cube-path), we say that P starts at 21x2. By definition, the existence of a square-path
starting at z1z2does not imply the existence of a square-path starting at z2z1.Here the
order of the endpoints of edges is significant. This is the only case where we distinguish
xy from yx for the same edge. In such a case, for clarity, we shall use the term ordered
edge instead of edge. If P = zyQzw is a square-path (so Q is a square-path itself), we
say that xy is connected to zw through Q, or by P.
A square-cycle is optimal if (i) it is a longest square-cycle; (ii) subject to (i), it has the
maximum number of 3-chords; (iii) subject to (i) and (ii), it has the maximum number of
4-chords. A square-cycle C is chord-maximum if it is optimal and, subject to this, the
subgraph induced by V ( C ) has maximum number of edges among all optimal square+~,
cycles. Let C = u1u2 . . . uCul be a square-cycle, where c = IV(C)I and u , ~ ,u,u,+2
are 1- and 2-chords of C respectively, 1 5 i 5 c. (Addition of indices is taken modulo c.)
By i < 1, we mean that u,,
u,+1,.
. . , IL] are around C in the order consistent with a fixed
orientation of C.
Let G be a graph on n vertices with S(G) 2
Section 2 is devoted to general lemmas
that are needed in other sections. In Section 3, we prove that if G has no hamiltonian
square-cycle, then any square-cycle in G has length at most
In Section 4, it is showed
that the longest square-cycle in G has length at least n/2. Finally, by using the two results,
we establish in Section 5 that the vertices of G can be partitioned into at most two squarecycles.
+
in.
in.
2. LEMMAS
Lemma 2.1 (4, Lemma 3.21. Let C = u1u2. . . utl,.ulbe an optimal square-cycle in a graph
G. Let x be a vertex in G - C.
(a) d ( z , Q) 5 \$ q
+ 1 for any segment Q = u1u2. . . uq--luqof C, with equality only if
d ( z , U I U 2 ) = d ( z ,uq--luq)= 2.
PARTITIONING INTO TWO SQUARE CYCLES 243
(b) d(x,C ) 5 (2c
+ 1)/3, with equality only if, by relabeling,
Nc(x)= v(c)\ { u g k : 1 5 k 5 ( c - 1)/3}.
d ( x , u C u 1 u 2=) 3 and
Remark. The second part of Lemma 2.l(a) is not contained in [4], but it follows
immediately by applying the first part to the segments Q - a1a2 and Q - a q - l a q .
in,
Lemma 2.2. Let G be a graph on n vertices with 6(G) 2
where n 2 7. Suppose that
S is an independent set of G with ( S / 2 f and xy E E(G) with x E S. Then G has a
hamiltonian square-cycle C such that xy is neither a 1-chord nor a 2-chord of C.
Proof. Since S is an independent set, we have that S(G) 5 n - I
S1 and so I
S
15
n - S(G) 5 2 , which implies that (SI= n/3, S(G) = \$n, and each vertex of S is joined
to every vertex of G - S. Let S = { 2 1 , 5 2 , . . . , x k } , where x1 = x and Ic = IS\. Since
S(G - S ) 2 S(G)- I
S1 = n / 3 = i ( V ( G- S)l,it follows from a classical theorem of Dirac
[ l ] that G - S has a hamiltonian cycle, say a1u2 . . . uv,ul, where m = IV(G - S ) ( = 2k
and a,, = y. Noting that m 2 5 (since n 2 7) and each 2, is joined to every vertex of
G - S, we see that ala2x1a3a4x2a5a6x3... a23-1a2,xJa23+1a23+2...anL-1a,,xkalu2 is a
hamiltonian square-cycle in G with the required property.
I
Lemma 2.3. Let C = u1u2. . . ucul be a chord-maximum square-cycle in a graph G. Let
W 2 V ( G - C ) with d(v,C) = (2c + 1)/3 for all v E W.
(a) If c = 4, then W is an independent set in G;
(b) If c # 5 and W # 0, then there is a set S C V ( C )with / S /= ( c - 1)/3 such that
W U S is an independent set in G and N c ( a ) = Nc(6) for every a , 6 E W U S.
Proof. (a) If the statement is not true, let 2,y E W with xy E E(G).Since d ( v ,C) = 3
for all v E W, we have that 2 5 INc(xy)( 5 3. If i N ~ ( x y ) =
( 3, we have a K5; if
INc(xy)l = 2, we have a square-cycle C' with V ( C ' )= V ( C )U {x,y}. In either case, we
have a contradiction to the maximality of c. This proves (a).
(b) Since W # 0, c = 1 (mod 3), and since c 2 5, we have that c 2 7. Let x E W. By
Lemma 2.l(b), with a proper labeling we have that Nc(x)= V ( C )\ S, where S = { u 3 k :
1 5 k 5 ( c - 1)/3}. Let C, be the square-cycle obtained from C by replacing u3, with x,
that is, C, = u1u2 ..'u3t-2u3t-1xu3t+iu3t+2...u,.ul, where 1 5 t 5 ( c - l)/3. First, we
have that U3?& \$! E ( G ) since, otherwise, &u1xu2u4u3u5ug . . . u, would be a square-cycle
of length c + 1. And analogously ~ , - 1 ~ , - 4 \$! E ( G ) . Now, since u,x is a 3-chord in C1
and by the optimality of C, we have that
ucu3E E ( G ) ,and analogously, u,-1u2 E E ( G ) .
(2.1)
Next, we have that uc-lu3 q! E ( G ) since, otherwise, uc-1ucu3ulu22u4u5.~. u , - ~ would
be a square-cycle of length c I. Moreover, since xu7 is a 4-chord in C1,it follows from
E 4E ( G ) follows from the optimality
the optimality of C that ~ 3 1 1 7E E ( G ) .Then u 3 t ~ 3 t +
~ 4-chords in C,, 2 5 t 5 ( c - 4)/3.
of C and from the fact that xugt--q and Z U ~ , +are
We have seen that u 3 U 6 q! E(G). If ~
3 E E (~G ) for ~some t ,32 5 t ~5 ( c -~4)/3,
then u , 2 ~ ~ 2 u ~ ( u ~ u g u g (u3t+lu3tu3t+2)uL3t+3U3tf4
) ( ~ ~ u ~ u ~ ) ~ ~ ~ . . . U , - ~ U , is a square-cycle
of length c + 1. Therefore we have that
+
\$! E ( G )
u3tu3t+3
c-4
3
for all t , 1 5 t 5 -.
~
244 JOURNAL OF GRAPH THEORY
We note that C,, 1 5 t 5 (c - 1)/3, has the same length as C, and by (2.2), has as many
3-chords as C does. Since C is chord-maximum, d(u3,, C) 2 d ( z , C), and since Ct is also
optimal, we have that d ( u S t ,C) = d ( z , C) = (2c + 1)/3. We claim that Nc(wgt,)= Nc.(z).
If this is not true, then u g t is joined to some u 3 k E S. We may suppose that k > t and
choose k - t to be as small as possible. By (2.2), k 2 t + 2, and by the minimality
~ ~ the
) property
of k - tlu3tusk-:3 \$! E ( G ) . Since d(u3t,Ct)= (2c + 1 ) / 3 , N ~ , ( uhas
described in Lemma 2.l(b). Noting that u3tu3/c E E ( G ) and u S t u 3 k u 3 @ E ( G ) ,we see
that d ( u S t ,u 3 k - - 2 u ~ k - - 1 ~ 3 k=) 3. It follows from (2.1) (with Ct, uSt in the position of C, z)
that u:jk--3u:\$k- E E ( G ) ,contradicting (2.2). Therefore, NC(uSt)= Nc(x)
for all ulgtE S,
which implies that S U { z } is an independent set.
Next we show that Nc(y) = N c ( z ) for all y E W \ {z}. By Lemma 2.l(b),
d ( y , ~ , u , + ~ , u , + ~=
) 3 for some u., E V ( C )and N(y) = V ( C )\ S’, where S’ = {u,+:\$~
:
i 2 l} and /S‘I
= (c - 1)/3. If j = c, then Nc(y) = N c ( z ) . Suppose that this is not the
case. For 1 5 t 5 (c - 4)/3, if j = 3t or 3t + 1, then, as seen in (2.1), uju3+3E E ( G ) ,
contradicting (2.2). Thus, j E {c - 2, c - 1,1,2}u {3t + 2 : 1 5 t 5 ( c - 4)/3}. It is easily
verified that for any such value of j, S’ n S = 0. So S U {x} and S’ u {y} are two independent sets, and moreover, S C Nc(y) and S’ C Nc(x).Let D be the graph induced by
V(C)U{z,y),p lu s th eed g ex y if itis n o tin E (G ). S o d ( w , D ) = (2c+1)/3+1 = \$lV(D)l
for all v E S u S ’ u { z , y } . Note that ( S U { Z } / = IS’u{y}/ = ( c + 2 ) / 3 = i l V ( D ) l .We see
that d ( v , D ) 2 (SU{z}(+(S’U{y}(= \$lV(D)I for all v E V ( D ) \ ( S U S ’ u { z , y } ) . Therefore, 6 ( D ) > { l V ( D ) ( .Note that IV(D)l 2 c + 2 > 9. It follows from Lemma 2.2 that D
has a hamiltonian square-cycle that does not contain the edge zy,and so it is a hamiltonian
square-cycle of length c + 2 in G. This contradiction shows that Nc(y) = N<:(x)
for all
YE W\{xI.
Finally we need to show that W is an independent set. If this is not true, let x , y E W
and zy E E ( G ) . Since N c ( z ) = Nc(y) and c 2 7, we may replace a vertex of S by the
edge zy and obtain a square-cycle of length c + 1. Thus W is an independent set and the
proof is completed.
I
Lemma 2.4. Let G be a graph on n vertices with S(G) 2 \$ n and let C = u1u2 ”.u,:u1
be an optimal square-cycle in G. Then either c = n or c 2 5.
Prooj For n 5 9, the result can be easily verified. We assume that n 2 10. If c = 3,
then G contains no K4. This means that N ( u v ) is an independent set for any edge uv E
E ( G ) . Since S(G) 2 \$ n , we have that ( N ( u v ) l2 n/3, and the by Lemma 2.2, c = n. If
c = 4, then d(v,C) 6 3 for all v E V ( G - C), and by Lemma 2.3(a), S = {z E V ( G- C )
: d(x,C) = 3) is an independent set. Moreover,
8
-n 5 d ( C , G) 6 2(n - c )
3
+ IS1 + 12 = 2n + 4 + IS/,
which implies, since n 2 10, that /St> - 1. Let z E S. Since S is an independent set
and d ( z , C )5 c - 1, we see that d(x) 5 n - 1 - IS/,
and thus I
S1 5 n - 1 - d(x) 1. - 1,
a contradiction. This proves the lemma.
I
Lemma 2.5. Let C = u1u2. . . u,ul be a chord-maximum square-cycle in a graph G. Let
xy be an edge in G - C.
PARTITIONING INTO TWO SQUARE CYCLES 245
(b) If d(xy,C) = i c and c # 3, then d ( ~ y , u ~ u , +I~3) for all consecutive U ~ , U , + E~
V ( C )and there are s , t such that x E N ( U , ~ U , ~E+N~()U, ~~ U ~ and
+ ~ s) , 2 5 t 5
s + 4.
+
Proof. (a) If c = 1 (mod 3), by Lemma 2.l(b) and Lemma 2.3, d(zy, C) 5 (4c - 1)/3;
if c 1 (mod 31, by Lemma 2.l(b), d(zy, C) 5 4c/3.
(b) By the given conditions, c = 0 (mod 3) and c 2 6, and it follows from Lemma
2.l(b) that d ( x , C ) = d ( y , C ) = \$c. Let Q be any segment of C with IV(Q)I = 3k + 2.
Then, for any a E (5, y}, by Lemma 2.l(a) d ( a ,C - Q) 5 \$(c - IV(Q)\)+ 1. Noting that
c - IV(Q)I = 1 (mod 3), we have d ( a , C - Q) 5 \$ ( c - IV(Q)I)+ \$, and therefore
+
2
3
d(a, Q) = -C
-
2
1
d(a,C - Q ) 2 -IV(Q)I - - = 2k
3
3
+ 1.
(2.3)
Suppose, to the contrary, that d(xy, U , U , + ~ ) = 4 for some i. By relabeling, we may assume
that d(xy, u1u2)= 4. By the maximality of c, either d(u,, xy) = 0 or d ( u 3 ,xy) = 0. Without
loss of generality, we assume that d(u3,zy) = 0. By (2.3) with Q = u 3 u 4 , d ( u 4 , z y =
) 2.
Then d ( u 5 , x y ) = 0 for otherwise a longer square-cycle results by replacing
by xy.
Again by (2.3) with Q = u5u6,d(u6,xy) = 2. We claim that c 2 9. If this is not true, then
c = 6 and {a1,u2,
u4,u6,x,y} induces either K6 or K6 minus the edge ~ 4 ~ which
1 ,
gives
a square-cycle with at most one 3-chord missing. Thus, since it is optimal, C contains
all the 3-chords, except for at most one. Then the graph induced by V ( C )U {z,y} has
a square-cycle of length at least 7, a contradiction. Therefore c 2 9, as claimed. If
d(u,,xy) = 0, by (2.3) with k = 2 and Q = u,-2uc-1u[~u1u2u3u4u5,we obtain that
d(u,-2u,-l, xy) = 4 and ~,-2u,-~zyu~u2
. . . tLc-3uc-2 is a square-cycle of length c + 1.
Thus we assume that d(u,, zy) 2 1. By symmetry, we may assume that ucxE E ( G ) . Note
that d(u3, zy) = d ( u 5 ,zy) = 0. By (2.3) with Q = u3u4u5u6u7,we have that d(u6u7,zy) =
4. Thus C' = u,ulu2zu4yu62L7"'uc-1u[: is a square-cycle of length c. We note that
zu,.,xu6,yu2 are 3-chords in C'. By the choice of C, there must be at least three 3chords incident with u3 and u5. So either u,u3 or u5u8 is a 3-chord in C. In the former
case, u,u1u3th2u4xy'zL6u7.. . u,-~u,, and in the latter case ulu22yuqu6ugu7ug... u,ul, is
) 3 for all
a square-cycle of length c 1. This contradiction shows that d(zy, U , U ~ + ~ 5
u , + ~E V ( G ) .
consecutive ui,
Since d ( z , C ) = i c , we may assume that 17: E N(u1u2).By the above result, y q!
N ( u l u Z ) Without
.
loss of generality, we suppose that yu2 # E ( G ) . By (2.3) with Q =
u2u3u4ugu6, we have that y E N ( ~ ~ u j + ~5) j, 3 5 5. This completes the proof of
Lemma 2.5.
I
+
Lemma 2.6. Let C = u 1 u ~. . . u,ul be a chord-maximum square-cycle in a graph G. Let
T be a triangle in G - C. Then d ( T , C) 5 2c - 1.
Pruuj
If c = 3, then d(v,C) I
2 for all 'u E V ( T ) ,which gives that d ( T , C) I
6.
But, if d ( T ,C) = 6, then, since G has no K4, the subgraph induced by V ( T )u V ( C )is a
square-cycle of length 6, contradicting the maximality of c . Thus d(T,C) 5 5 = 2c - 1.
We assume therefore that c 2 4. Let x,y, z be the three vertices of T . If the assertion is
not true, then by Lemma 2.5,
2
3
d(x,C ) = d ( y , C ) = d ( z ,C ) = -c.
(2.4)
246 JOURNAL OF GRAPH THEORY
and d(T,uiu,+l) 5 4 for all consecutive u i ,ui+l E V ( C ) .By (2.41, d(T,C) = 2c, and it
follows that d(T,U , U , + ~ ) = 4 for all consecutive ui, u , + ~E V ( C ) .We note that c E 0
(mod 3 ) by (2.4), and hence c 2 6.
Case 1. There is some s such that d(u,, T ) = 1, say d(ul,
T ) = 1. Then d ( u 2 ,T ) = 3,
which implies that d(u3,T ) = 1, and then d(u4,T ) = 3 , . . . , d ( u ~ k + lC, ) = 1,d ( ~G)~= ~ ,
3 , . . . . We may suppose that u1x E E ( G ) .If c = 6, then u6U1tL2xyzu4u6 is a square-cycle
of length 7, a contradiction, thus c 2 9. If u1 and us are joined to distinct vertices of T ,
then replacing u3 by T gives a square-cycle of length c 2 . Thus ul and u5 are joined to
the same vertex x. By the same reason, u3 and u7 are joined to the same vertex in T . Since
x cannot be joined to the four consecutive vertices, the vertex in T joined to u7 must be
distinct from x, say it is y. Then u1U.m4zyu6u7 . . . u,.u1 is a square-cycle of length c + 1,
thus case 1 leads to a contradiction.
Case 2. d ( u i , T )= 2 for all u, E V ( C ) .By (2.4) and Lemma 2.5(b), we may assume
that d ( u l ,zy) = 2 and d ( u 2 ,yz) = 2 .
Case 2a. u,y E E ( G ) .Noting that y, by the maximality of c, cannot be joined to four
consecutive vertices, we have that u 3 y @ E ( G ) and so d ( u g ,xz) = 2 . If u,x E E ( G ) ,then
uu,:u1xyzu2u~~
is~a" usquare-cycle
c
of length c 3. Thus we assume that ucz E E ( G ) .
If ulz E E ( G ) , then u,u1yu2zu3u4. "u, is a square-cycle of length c + 2; otherwise
d(u~q,
xy) = 2 , then ulu2yzZu3u4 . . . ucul is a square-cycle of length c + 3.
Case 2b. u,y @ E ( G ) and so d ( u , , x z ) = 2 . Clearly, u3z @ E ( G ) for otherwise, as
before, u,ulzyzuzu:3. . . u c is a square-cycle of length c + 3 . So d ( u g , x y ) = 2 . Since
y cannot be joined to four consecutive vertices, u4y @ E ( G ) and SO d ( u 4 , x z ) = 2 . If
U , . - ~ X E E ( G ) ,then ~ ~ - ~ u , x z y u .~
u,.-1
u ~is
u a4square-cycle
~~
of length c + 2 ; otherwise
d(u,-l,yz) = 2 , then u,-1u,zxyu1u2.
. . u , - ~is a square-cycle of length c + 3. In either
case we have a contradiction. This completes the proof of Lemma 2.6.
I
+
+
Lemma 2.7. Let G be a graph on n vertices and let C be a chord-maximum square-cycle
of length c in G. Set H = G - C. If H f 0 and d(v,G) 2 \$ n for all w E V ( H ) ,then
E ( H ) f 0 and any edge of H is contained in a K4 in H .
. Lemma 2.l(b), S ( H ) 2 (2h - 1)/3 > 0 and so E ( H ) # 8.
Proof. Let h = / V ( H ) / By
For any e E E ( H ) ,by Lemma 2.5(a), d ( e , H ) 2 t h , which implies that e is contained in
a triangle, say T , in H . By Lemma 2.6, d ( T , H ) 2 2h 1 and so T is contained in a K4
in H .
I
+
Lemma 2.8. Let G be a graph on n vertices with b(G) 2 \$71 and let C be a chordmaximum square-cycle of length c in G, where c < n. Set H = G - C and h = / V ( H ) I .
Let Q be a chord-maximum square-cycle of length q in H . If q < h, then q I h - 4.
Proof. By Lemma 2.4, c 2 5. If d (v,H ) 2 \$ h for all E V ( H - Q ) , then by Lemma
2.7, H - Q contains a K 4 , and we are done. Assume that there is y E V ( H - Q) such
that d ( y , H ) < gh, which together with Lemma 2.l(b) implies that d(y, C) = (2c + 1)/3
(so c = 1 (mod 3)). Let H' = H - y. For any w E V ( H ' ) , if d(w,C) = (2c + 1)/3, then by
Lemma 2.3, vy @ E ( G ) .This means that b ( H ' ) > i ( h - 1).If q < ( h - l ) , then the result
follows by the arguments we just used. Otherwise, q = h - 1 and d ( y , Q) = (2q + 1)/3 (so
q = 1 (mod 3)). If q 2 5, by applying Lemma 2.3(b) to y and Q, we have an independent set
S1 C V ( Q )suchthat ISl]= (q-1)/3,S1u{y}isanindependentset,andNQ(a) = N Q ( ~ ) ,
implying d ( a , C) = (2c + 1)/3, for all a E S1. If q = 4, let S1 = { z } , where z is the
only vertex in Q not joined to y. (Note that d ( z , C) 2 \$ n - 3 = (2c + 1)/3 and hence
d ( z , C) = ( 2 c + 1)/3 by Lemma 2.1(b).) In either case, S1U {y} is an independent set with
PARTITIONING INTO TWO SQUARE CYCLES 247
IS11 = ( q - l ) / 3 a n d d ( w , C ) = ( 2 c + 1 ) / 3 f o r a l l v ~S 1 u { y j . ItfollowsfromLemma2.3
that there is an independent set S2 C V ( C )such that IS2J = ( c - 1)/3 and S2 U S1U { y j is
an independent set, which has cardinality n/3, and by Lemma 2.2, c = n, a contradiction.
I
This completes the proof.
Lemma 2.9. Let G be a graph on n vertices and let P = ~ 1 ~ . .2. uP-1uP
~ 3 be a squarepath starting at u1u2 and ending at uP-luP.Set H = G - P and h = IV(H)I. Let A =
{u E V ( H ): d(v,G ) 2 (5n 1)/6}. If p > 2h - 5, then G has a square-path P’ starting
at u1u2 and ending at uP-luPwith V(P’) = V ( P )u A.
+
Proof: We use induction on / A / .If A = 0, there is nothing to prove, and thus we
assume that A # 0 and let a E A . We note that d ( a , P ) 2 (5n + 1)/6 - (h - 1) =
z3 ( p 1) ( p 5 - 2h)/12 > i ( p + 1), which implies that there are four consecutive
vertices u2,uz+l,u,+2,ut+3on P that are all joined to a, so that Q =
u1u2 . . . u,uz+lau~,+Zu2+3~,-I~~
is a square-path. Let H’ = H - Q and A’ = A \ { u } .
Obviously IV(Q)I > 21V(H’)J - 5, and the result follows by induction.
I
+ + +
Lemma 2.10. Let G be a graph on n vertices with a square-path P = u1u2 . . .~ , - 3 ~ , - 2
such that G - P is a single edge, denoted by xy. Suppose that u1 \$ N(zy). If d(u1,G) +
d(y,G) 2 \$n - 1 and d(u1u2,G)
+ d(xy,G) 2 (10n - 8)/3, then G has a hamiltonian
square-path starting at sy and ending at ~ , - 3 ~ , , - 2 .
Proof: Let B = {u,u,+~: u,E N(zy) and u,+1 E N ( u I z L1~5) ,i I
n - 3). For each
E B and i
n - 3 (note that u1 @ N(zy)),if both u,-1 E N(y) and u,+2 E N ( u l ) ,
then zyu,u,-1 . . . u2u1u,+1u2+2‘ . . ~ , - 3 ~ , - 2 is a square-path with the required property.
((V(P)I- 1)
Thus we assume that this is not the case. Then d ( u l , P ) d(y, P ) I
( V ( P )/ (If?/- 1) = 2n - 4 - IB(.
Since ul !\$ N ( x y ) , we have d(u1,xy) I 1, and
obviously d ( y , x) = 1. It follows that
+
U,U,+~
+
5
-n
3
-
1I
d ( u l , G)
+ d ( y , G) Id(u1, P ) + d ( y ,P ) + 2 I2n
+
-
2 - JBJ,
which gives that ( B (5 n/3 - 1. We shall prove that this is impossible. Let D = { u 2 :
u , + ~E N(ulu2),1 5 i 5 n - 3). Clearly, ID1 = J N p ( u 1 u 2=
) JIN(uIu2)\ { z , y j I . Since
u1 @ N(xy), we have I{x,y}nN(u1u2)1
5 1. Noting that IN(u1u2)I2 d(u1u2,G)- n , we
obtain that (Dl 2 d(ulu2,G ) - n - 1. By definition, B = {ZL,U,+~ : u,E D n N(zy)} and
hence
which gives that JBJ2 (472 - 11)/3 - ID U N(zy)J.Since u1 4 D U N(zy), ID U N(xy)I 5
IV(P)I - 1 = n - 3, and it follows that IBI 2 (n - 2)/3. This contradiction completes the
I
proof of Lemma 2.10.
3. AN UPPER BOUND FOR LONGEST SQUARE-CYCLES
Theorem 3.1. Let C = u1u2 - - . u c u l be a chord-maximum square-cycle of a graph G
with n vertices. Suppose that G - C f 0 and d ( v , G ) 2 \$n for all ‘u E V ( G - C ) . Then
c 5 \$n,with equality only if there is a triangle T in G - C such that d ( T , G) = 2n.
248 JOURNAL OF GRAPH THEORY
We first prove two additional lemmas and then go to the proof of Theorem 3.1. Recall
that a cube-path contains all the 2- and 3-chords. Define an almost-cube-path to be a
square-path that has at most one 3-chord absent.
Lemma 3.2. Let P = x 1 x 2~ ~ ~ x p - - 2 x p -be
l xap cube-path, where p 2 5. Then x1z2 is
xpzp-l,
xp-2xp,xpxp--2} by a squareconnected to each of the ordered edges {xp--lxp,
path P’ with V(P’) = V ( P ) , and to each of the ordered edges {xp--2xp--1,xp-1xp-~}
by a square-path P” with V(P”) C V ( P )and IV(P”)I = p - 1. Moreover, all of these
square-paths are almost-cube-paths, possibly except for the one connecting x 1x 2 to X ~ X ~ Proof. Trivially P itself is an almost-cube-path connecting x122 to xp-lxp.Since P is
a cube-path, each of the following is an almost-cube-path: 21x2 . . . Xp-3zp-22pXp-l,21~2
. . . x p ~ 3 x p - 1 x p - 2 xxp1rx 2 . . . xp-3xP--2xp-~,and x152 .. ~xp-3xp-lxp-2.Clearly, X ~ Z Z
. . . ~ ~ - 3 %1zpxp-2
~ is a square-path. This proves the lemma.
I
Lemma 3.3. Let C = u 1 u 2 .. . u,ul be an optimal square-cycle of G and let xy and zw
be two independent edges in G - C. Suppose that d ( ~ y , u ~=u 4~ and
)
xy is connected
to Z7U and wz by square-paths of at least p vertices in G - C, at least one of which is an
almost-cube-path.
+
(a) If c > 2p 3, then ~ ( z wC), 5 \$c - \$ p
(b) If c 5 2 p + 3, then d ( z w , C ) 5 c + 2.
+ !.
Proof. Let Q = u3u4. . . up and Q’ = ucu,_ . . . u9t be two segments of C starting at
u3u4 and U , U , _ ~ , respectively, such that (i) V(Q) n V(Q’) = 0 and both IV(Q)l 5 p 1
and IV(Q’)I 5 p 1; (ii) d(u,, zw) 5 1 and d(u,t,zw) 5 1; (iii) subject to (i) and (ii),
+
+
IV(Q)I + IV(Q‘)I is as large as possible.
Letu, ~ V ( Q ) , 3 < i < q - l . S i n c e ( V ( Q ) (~ p + l , i f d ( u , , z w )=2,thend(u,+l,zw) =
0, for otherwise zw or wz is connected to ~ , u , +by~a square-path and we may replace the
segment u3u4. . . u,- by a square-path in G - C to obtain a longer square-cycle. Taking
into account that d ( u g ,zw)5 1, we have that
d(zw,Q) F IV(Q)I1
~,
with equality only if d ( ~ , - zw)
=2
(3.1)
whenever d(u,, zw)= 0 with u,E V(Q). Similarly,
d(z.u~,
Q’)
F IV(Q’)I,
~ , = 2 whenever d(u,, zw)
with equality only if d ( ~ , +zw)
that
(3.2)
=0
with u,E V(Q’). We claim
= 2(d(u,+l,zw) = 2) whenever d ( u , , z w ) = 0 with
with equality only if d(u,-,,zw)
ut E V(Q)(uz E V(Q‘1).
If d ( u 1 u 2 , z w )5 3, then (3.3) follows directly from (3.1) and (3.2). Suppose that
d(ulu-2,zw) = 4. Then d(u.3, zw)= 0 or d(u,, zw)= 0, for otherwise z or w is joined to
four consecutive vertices or one of u, u1zwu2u3,u,u1wzu2uy is a square-path. Without loss
of generality, suppose that d ( u 3 , zw)= 0. Then, d ( z w ,Q) = d ( z w , Q - us) 5 IV(Q)I - 1,
with equality only if d ( ~ , - ~ , ~= w2 )whenever d ( u , , z w ) = 0, where u, E V(Q - u 3 ) .
~ .
PARTITIONING INTO TWO SQUARE CYCLES 249
This together with (3.2) gives (3.3). Let R = C - (Q u Q’ u { u l u 2 } )By
. Lemma 2.l(a),
2
d ( z , R ) 5 -(RI
3
+1
2
and d(w, R ) 5 -IRI
3
+ 1.
(3.4)
Combining with (3.3),
J
Substituting IRI = c - IV(Q)I - IV(Q’)I - 2 ,
(a) Since c > 2p + 3, the proofs of (3.1) and (3.2) also implies, by the maximality of
IV(Q)I IV(Q’)I, that IV(Q)I 2 p and IV(Q‘)I L p . If both have strict inequalities, then
IV(Q)l+lV(Q’)I L 2p+2 and the result follows from (3.6). Thus, without loss of generality,
we assume that IV(Q)I = p , noting that IV(Q)I IV(Q’)I 2 2p. If equality does not hold
in (3.31, then the result follows easily from (3.5) and (3.6). Thus we may also assume that
equality holds in (3.3). If IRI f 0 (mod 31, then d ( z , R ) 5 \$IRI +\$ and d ( w ,R ) 5 \$ IRI + \$;
if IRI = 0 (mod 3) and there is one strict inequality in (3.4), then d ( z w , R ) 5 \$ IRI + 1. In
either case, d ( z w ,R ) IIRI
which implies, as seen in (3.5) and (3.61, that d ( z w ,C ) 5
\$c - \$ p
as required. Thus we may further assume that both equalities hold in (3.4)
(so \RI = 0 (mod 3)). By definition, R = uq+luq+2
. . . ugr-l. Since both equalities hold in
(3.4) and by Lemma 2.l(a), we have d ( z w ,uq+luq+2)
= 4. Let P be an almost-cube-path
‘ . u,ul is a squareconnecting xy to zw or wz,say to zw. Now, C‘ = u1u2Puq+luq+2.
cycle. By the maximality of c, IV(P)I = p = IV(Q)1 and C’ has the same length as C. We
shall arrive at a contradiction by showing that C’ has more 3-chords then C does.
( 1) + 1 > \$(IRI +
If d(zw,u,) # 0, say d(z,u,) = 1, then d ( z , R U {u,})= ( \$ ( R+
1) 1, contradicting Lemma 2.l(a). Thus, d ( z w ,u,,)
= 0, and since equality holds in (3.3),
d(zw, uq-l) = 2 . If d ( z w ,uq-2) # 0, then replacing uq by zw or wz yields a longer square,
= 0, and again since equality holds in (3.3), d ( z w ,uq-3) = 2.
cycle. Thus ~ ( z wuq-2)
(We note that IV(Q)I = p 2 4.) We show now that there is no 3-chord incident with
any vertex of { U ~ - ~ , U ~ - ~ in
, UC.
~ }If
E E ( G ) ,then u1u2Puq-luq+luquq+2uq+3
. . . u,ul is a square-cycle of length c + 2. If uquq-3E E ( G ) ,then u1u2Puq--3uq-luquq+1
...u,u1is a square-cycle of length c + 3. If uq--2uq+lE E ( G ) , then u1u2Puq--3uQ-l
uq-2uquq+1
. . ’ u c u l is a square-cycle of length c + 4. If uq-2uq-5E E ( G ) , then uq--5
uq-4uq-2uq-3uq-122vuq+l~q+2 . . . uq--(iuq-5 is a square-cycle of length c + 1. If u,,-1u,+2
E E ( G ) , then u ~ u ~ P u q ~ ~ u q + ~ uisqa+square-cycle
2 ~ ~ ~ u cofu length
1
c + 1. Finally, if
uq-] uq-4 E E ( G ) ,then D = u q - 4 u q - 3 u q - 1 z ~ u q + l uq--5uq-4
q + ~ ~ ~is~ u
a square-cycle
of length c in which zuq+2 and wuqP3are 3-chords. Since we have just showed that C
has no 3-chord incident with uqP2or uq and also uq-1uq+2\$ E ( G ) ,the only 3-chord lost
is uq-Iuq-4. However, we gain two 3-chords in D: wuq-3 and z u q f 2 . So D has more
3-chords than C, contradicting the optimality of C. This proves that there is no 3-chord
incident with any vertex of { u q - 2 , u q - - 1 , u qin} C. Since P is an almost-cube-path and
since u l y and z u q f 2 are 3-chords in C’, it follows that C’ has more 3-chords than C. This
+
+
+ g,
+
4 + 4,
250 JOURNAL OF GRAPH THEORY
(b) Since c 5 2 p + 3 , by the maximality of IV(Q)I + IV(Q’)I we have JRI 5 1, and it
follows from (3.3) that d ( z w ,C) 1. IV(Q)I + IV(Q’)I+ 3 + 21RI = c + 1 + IRI 5 c 2, as
required.
I
+
Proof of Theorem 3.2. Let H = G - C and h = 1 V ( H )1. Let K be a maximum complete
subgraph in H with IV(K)I = k . By Lemma 2.7, we have k 2 4. By the maximality of
K,d(K,u)
< k - l f o r a l l u ~ V ( H - K ) a n d h e n c e d ( K , H ) 5 h(k-l).Ifd(K,uiui+l) 5
k + 1 for every edge U , U ~ + E~ E ( C ) ,then summing these inequalities over all i , 1 5 i L c,
yields that d ( K ,G) 5 (k + 1)/2c, and consequently,
(3.7)
in.
in
which gives c 5
If equality holds, then d ( v , G) =
for all v E V ( K ) So
. d ( T , G ) = 2n
for any triangle T in K . Therefore we assume that there is some edge U , U , + ~ E E ( C ) such
that d ( K , u , ~ , +2~ )k + 2, which implies that d ( ~ , u , + ~ , e=) 4 for some edge e E E ( K ) .
Let P = ~ ~ 5 .~ I 5G : ~ ~be
- . a~ longest
~
~
cube-path in H starting at some edge zlx2 with
d ( x l z 2 ,u2u,+1)= 4 for some i, where p 2 k 2 4. By relabeling, we may assume i = 1.
That is, d(zlz2,u1u2)= 4.
Case 1. p = 4. So V ( P )induces a K4. Clearly, c 2 Ic 2 4. By Lemma 2.5(b), noting
that d ( z 1 x 2 , u 1 u 2=) 4, we have that d(xlz2,G) < i c . Without loss of generality we
assume that d(z2, C) < \$c. If c > 2 p + 3 , then, by Lemma 3.3(a), d(53x4,C)2 \$ c - 1 and
hence d(x2z3z4,C) < 2c-1. By the maximality of P, d(z2x3xq,H - P ) 5 2(h-p) = 2h-8,
and since V ( P )induces a K4, we have that d(z3z4,P ) = 9, and consequently,
+ (2h 8) + 9 = 2n,
(3.8)
Therefore we suppose that c 5 2p + 3 . By Lemma 3.3(b), d(x3z4,C) 5
2n 1. d ( z 2 ~ 3 ~G)
4 , < (2c - 1)
+ 2. Using 4 ~
c
~ xH4) 5
,
-
2(h - l ) ,
4
-n 5 ~ ( Z Q ZG)
~ ,5 c + 2 + 2(h - 1) = 2n - c,
3
in.
(3.9)
in,
If equality, c =
holds, then d(x3,G) = d(xq,G) = i n , and
which gives that c 5
moreover, d(a3z4,H ) = 2(h - l ) , which implies, by the maximality of P, that d ( x 2 ,H P ) = 0. Using d ( z 2 , P )= 3 , we obtain that 4 x 2 , G) < \$ c 3 I \$ n \$, and hence
d ( z 2 ,G) = \$n. Let T be the triangle on ( 5 2 , z 3 , xq}. Then d ( T , G) = 2n, as required.
Case 2. p 2 5. Let T be the triangle on ( ~ ~ - z2p, - l ,z p } .If c > 2p 3 , by Lemmas
3.2 and 3.3(a),
+
4
2
3
5 -c
3
-
5 -c
4
- -2p
3
Tp
3
+ -,53
+ -,53
+
+
d(xp-25p,C )
and
~ ( Z ~ - - ~ Z + IC)
,
L -c
4
3
-
-2( P
3
-
1) + -.
5
3
Adding these inequalities yields that 2d(T, C) 5 4c-2p+5+\$, which gives, since d ( T , C)
is an integer, that d(T,C) 5 2c - p 2. By the maximality of P, d ( T , H - P ) 5 2(h - p ) ,
and using d ( T , P ) 1. 3 ( p - l ) ,
+
2n 5 d ( T , G) 5 2c - p
+ 2 + 2(h
-
p)
+ 3(p
-
1) = 2n - 1.
(3.10)
PARTITIONING INTO TWO SQUARE CYCLES 251
This contradiction shows that c i 2 p + 3 . By Lemmas 3.2 and 3.3(b),
and as seen in (3.91, we have that
4
-n 5 d(~:,-lzp,G ) 5 c
3
+ 2 + 2(h - 1) = 2n,
C) 5 c t 2 ,
(3.1 1)
- C,
which gives that c 5 \$n with equality only if ~ ( Z , - ~ , G
= )d(z,,G) = \$n. If equality holds, then, by applying Lemmas 3.2 and 3.3(b) to the edge xp-2xp, we have that
d ( ~ ~ ,G- )~=, d(x,, G ) = jn, and hence d ( T ,G) = 2n. This proves Theorem 3.1.
We may modify the proof of Theorem 3.1 to obtain the following generalization.
Theorem 3.2. Let C = ulu2 . . . u,u1 be a chord-maximum square-cycle in a graph G with
n vertices. Suppose that G - C # 8 and d(v,G) 2
+ r for all v E V ( G - C ) ,where r
is a nonnegative real number. Then c L: \$n - 2r.
in
Proof. Let H = G - C and h = IV(H)I. As in the proof of Theorem 3.1, let K be a
maximum complete subgraph in H with IV(K)\ = lc. If d(K,u,ui+l) 5 k + 1 for every
edge uiu,L+lE E ( C ) ,then, instead of (3.7), we have that
J
which gives c I
\$ n- 2 r k / ( k - 3 ) 5 f n - 2r, as required. Thus, as in the proof of Theorem
3.1, we may let P = ~ 1 ~ 2 .x. .3xp-lxp be a longest cube-path in H starting at some edge
51x2 E E ( H ) with d(zlz2,ulu2)= 4. Clearly, we still have contradictions in (3.8) and
(3.10). Note that (3.9) can be included in (3.11) by allowing p = 4. Instead of (3.11), we
5 )2n - c, which gives that c 5
- 2r. This
now have that \$ n + 2r 5 ~ ( J : , - ~ J : , , G
completes the proof of Theorem 3.2.
I
in
4. A LOWER BOUND FOR LONGEST SQUARE-CYCLES
Theorem 4.1. If G is a graph on n vertices with S(G) 2 \$n,then G has a square-cycle
of length at least n/2.
We need the following three lemmas in the proof of Theorem 4.1.
Lemma 4.2 [4, Theorem 2.11. Let G be a graph on n vertices. If 6(G) > \$n, then any
two independent ordered edges are connected by a square-path in G.
Lemma 4.3. Let G be a graph on n vertices with S(G) 2 \$n. Let C = ~ 1 ~ 2. u. ,u
. 1 be
a chord-maximum square-cycle in G. Set H = G - C and h = IV(H)I. If c < h, then the
following hold.
(a) d ( z , C ) I \$ c for all J: E v ( H ) .
(b) d ( e , C ) L: (4c - 1)/3 for all e E E ( H ) .
Proof. By Lemma 2.4, c 2 5. Let U Z I E E ( G ) with u E V ( C )and ZI E V ( H ) .Clearly,
d ( u , N ) 2 \$n-(c-l) = (2h-c)/3+1. By Lemma2.l(b), d(w,H ) 2 (2h-1)/3. Therefore,
d(u, H )
+ d ( v , H ) 2 h + 1+ h - c - 1
and so l N ~ ( u v )2
1 1,
(4.1)
252 JOURNAL OF GRAPH THEORY
with equality only if d ( u ,C) = c - 1 and d(v,C) = (2c + 1)/3.
(a) If the statement is not true, let z E V ( H ) with d ( z ,C) 2 (2c + 1)/3. By Lemma
2.l(b), d ( z , C ) = (2c 1)/3 (so c 2 7). Let H’ = H - z. We first claim that there
is y f V ( H ’ ) such that d ( y , ~ ~ u , +=~2) for some j , 1 5 j I c. If this is false, then
d ( y , C) 5 c / 2 for all y E V ( H ’ ) and so
+
(4.2)
Furthermore, since d ( y , ~ p , + 5
~ )1 for ally E V ( H ’ ) ,we have that 3n 5 d(u,u,+l,G)
5 h + 1 + 2(c - l ) , which yields, using n = h + c, that c 2 ( h + 3)/2. Applying this to
(4.2) yields that S(H’) 2 \$ ( h- 1) 2 \$ ( h- 1). By the result in [3], H’ has a hamiltonian
square-cycle. This implies that H has a square-cycle of length at least h - 1, and it follows
from Lemma 2.8 that H has a hamiltonian square-cycle, contradicting c < h. This shows
that there is y E V ( H ’ ) such that d ( y , u j u j + l )= 2 for some j, 1 I j 5 c , as claimed. Since
d ( z , C) = (2c+1)/3 and c 2 7, there is uiulLi+l
E E(C-U~U,~
such
+ ~that
) d ( z , ~ , & u i=
+ 2.
~)
Choose i and j such that the two edges ~ ~ u and
, +u,7uj+l
~
are as close as possible. By
relabeling, we may assume that i = 1, that is, d(z,u1u2)= 2. By Lemma 2.l(b) and by
the choice of i and j, 3 5 j L 5. By (4.11, we may let a E N ~ ( z u 2and
) b E N~(yu,,).
Case la. a # y and b \$ { a , z } . By Lemma 2.5, d ( a z , H ) _> \$n. - \$ c = i h . Since
h 2 c + 1 2 8, we see that I N ~ f ( a z )2
l 3. Let f E N ~ ( u z\ ){b,y). Now consider the
subgraph H’ = H - z. For any v E V ( H ’ ) , by Lemma 2.3, if d(v,C) = (2c + 1)/3, then
v z 4 E ( G ) .This implies that S(H’) > \$lV(H’)l,and it follows from Lemma 4.2 that a f is
connected to by by a square-path P in H‘. Then u1u2xPufufII. . . ucuI is a square cycle
of length longer than C.
Case lb. a f y and b = 2. By Lemma 2.3, d ( y , C ) # (2c + 1)/3, and by (4.1),
I N H ( y u 3 )2
( 2. Let z E NH(yuj)\{z). If z # a , we havecase la; if z = a,ulu2sayuju,+l
. . . u,ul is a longer square-cycle.
Case Ic. a # y and b = a. If I N ~ ( y u j ) 2
l 2 or I N ~ ( z u ~2) 2,
l then we have either
Case l a or Case l b above. Suppose that this is not the case. By (4.1), d ( z ,C) = d ( y , C) =
(2c 1)/3, and by Lemma 2.4, N c ( z ) = Nc(y) and so z is joined to both u j and uj+l.
Since we have equality in (4.11, d(u2,C) = c- 1 and so uLL,-1ucu2u1
is a square-path, which
means that we may use xu1 as xu2 in the above arguments and derive that N H ( z u l )= { a > .
Now ulu2azuju,,+1 ..’ucul is a square-cycle. Thus j = 5, and by the choice of i and j ,
no vertex in H is joined to both ug and u4. So d ( u g u 4 , H ) I h. Let w E { u 3 , u 4 }with
d ( w , H ) 5 i h . Then d ( w , C ) 2
- i h = (3c + n ) / 6 . Using n 2 2 c + 1, we derive that
d(w, C) 2 (5c 1)/6. Let P = u 4 u g u g . . . ucu1u2.It follows from Lemma 2.9 that there
is a square-path P’ starting at u4u5and ending at ulu2 with V(P’)= V ( P )u {w}. Then
P‘u2azu4 is a square-cycle of length c + 1.
Case 2. a = y. If (N~(zu~)l
2 2, then it is one of the above cases. We thus assume
that N ~ ( z u 2=) {y}. So d(u2,C) = c - 1. As in Case lc, we have that Nli(zul) = {v}.
Since y cannot be joined to four consecutive vertices of C, we have j 2 4. No matter
whether j = 4 or j = 5, by the choice of i , j and by Lemma 2.l(b), we always have
xu3 E E ( G ) .So ulu~zyujuj+l.. .u,:u1 is a square-cycle, which implies that j = 5. As in
Case lc, using d(u3u4,H ) 5 h, we obtain a longer square-cycle containing w E { u s ,u 4 } .
In any case, we have a contradiction to the maximality of c. This proves (a).
(b) By statement (a), d ( e , C ) 5 \$c for all e E E ( H ) . If (b) is false, let zy E E ( H )
with d(zy,C) = :c (so c = 0 (mod 3) and c 2 6). By Lemma 2.5, with a proper
) y E N H ( u ~ u ~ +where
I ) , 3 I t 5 5. By (4.11,
labeling we have that z E N ~ ( u l u 2and
+
+
in
PARTITIONING INTO TWO SQUARE CYCLES 253
/NIJ(ZU2
~ )2( and I N ~ ( y u t )2( 2. If there is z E V ( H ) such that N ~ ( z u=~ {z,y},
)
then u I u 2 z ~ y u t u t +.l. . uCulis a square-cycle of length at least c + 1. Otherwise, there are
distinct a , b E V ( H )\ {z, y} such that a E Nfi(zu2) and b E N H ( y u t ) . By (a), d ( a z ,H ) 2
3h,
3
and since h 2 c 2 7,(N~(az)l
2 3. Similarly, l N ~ ( b y ) 2
I 3. If d ( a z , b y ) = 4, then
ulu2zabyutut+l . . . uculis a longer square-cycle. Thus d(az, by) 5 3 and it follows that
) b’ E N ~ ( b y ) Let
.
there are distinct u’,b’ E V ( H )\ { a , b,z,y} such that u’ E N ~ ( a zand
H’ = H - z - y. For any v E V ( H ) ,by Lemma 2.6, if d ( v ,C) = gc, then d(v,z y ) 5 1.
This means, since c = 0 (mod 31, that S ( H ’ ) 2
- 1 > :(h - 2). By Lemma 4.2,
aa‘ is connected to b’b by a square-path Q in H I . Then u1 u2xQyutut+l. . . u,ul is a longer
square-cycle. This contradiction proves (b) and so the lemma.
I
in i c
Lemma 4.4. Let G be a graph on n vertices with S(G) 2 \$ 7 ~and let C = u1u2 . . . u,u1
be a chord-maximum cycle in G. Set H = G - C and h = IV(H)I. Let z E V ( H ) with
d ( z , C) = max{d(v, C ) : u E V ( H ) } If
. c < h, then the following hold.
(a) For distinct u,v E V ( C )and y E V ( H )\{x}, if uz,yv E E ( G ) ,then uz is connected
to yv through a square-path Q in H with IV(Q)I2 1.
(b) z E NH(uL,_lu,)
for some i, 1 I i 5 c, and if N ~ ( u ~ u ~ + ~ #
) \0,
{ where3
z}
2 i+2,
then j - i 2 6 with equality only if d(u,+l,H ) > h/2.
Proof. By applying Lemma 4.3(a) to (4.1), we have that INH(uz))
2 2 and INH(vy)I 2
2. If N H ( U Z =
) {y, z } and N ~ ( y v =
) ( 5 ,z } for some z E V ( H ) ,then uzzyv is a squarepath and the result holds with V ( Q )= {.}. Otherwise, there are distinct w l , w2 E V ( H )\
{z, y} such that w1 c N ~ ( u zand
) wzE N ~ ( v y )If. d ( z ,C) < Zc, then, by the choice of
z , S ( W ) > \$h, and by Lemma 4.2, xwl is connected to way by a square-path in H and
so uz is connected to yw through a square-path Q in H with {w1,w2} C V ( Q ) Thus
.
we
assume that d ( z ,C) 2 \$c, and by Lemma 4.3(a), d ( z , C) = \$ c (hence c 2 6 by Lemma
2.4). Using Lemma 4.3(b), we derive that d(zwl, H ) 2 (4h + 1)/3. Since h 2 c + 1 2 7 ,
it follows that \ N ~ ( z w ~2 )3\ and there is z E NH(zwl) \ {w2,y}. Let H’ = H - z. For
any w E V ( H ’ ) , by Lemma 4.3(b), if d ( v , C ) = gc, then vuz \$! E ( G ) . This implies that
S(H’) > \$ ( h - l), and by Lemma 4.2, w l z is connected to w2y by a square-path in HI,
which gives a square-path from uz to yu with the required property. This proves (a).
If x y! NH(u,-~u,) for all i, 1 5 i 5 c, then d ( z ,C) 5 i c . By the choice of z,
2
1
2
S ( H ) 2 3n - -c
=
3h+n
6 ’
~
(4.3)
and moreover, d ( H , C ) 5 ach, which implies that gnc 5 d(C,G) 5 +ch+ c(c - l ) , and
hence, n 2 ;(h+2). Applying this to (4.3) gives that 6 ( H ) 2 (3h+2)/4 > qh. By the result
in [3], H has a hamiltonian square-cycle, contradicting c < h. Therefore, z E NH(u,-lu2)
for some i. Now let y E N ~ ( u ~ u\ ~{z}
+ and
~ ) choose j such that j - i is as small as
possible. By statement (a), there is a square-path Q in H , where IV(Q)l 2 1, such that
u,-1u2zQyu,uj+1. . . uLL,_zu,-l
is a square-cycle of length at least c - ( j - i - 1)+ 3. Thus
j - i 2 4. For convenience, let L = a1a2. . . at be the segment of C from u,+]to u J - l ,
where a1 = U , + ~ , U ~= u,+2,. . . , and t = j - i - 1. If t 2 6, the proof of part (b) is
completed, and thus we assume that t 5 5. By the minimality of j - i, NH(ulul+l) = 0 for
all 1 , 1 I 1 I
t - 1, and then,
d(alal+l,H)lh
fordll,l<l5t-l.
(4.4)
254 JOURNAL OF GRAPH THEORY
Let A = { u E V ( L ) : d ( a , H ) 5 h/2}. By (4.4), ]A1 2 ( t - l ) / 2 with equality only if
al \$! A . We note that, for each a E A , d(u, C ) >_ \$ n - f h = (3c + n)/6 2 (5c + 1)/6. By
applying Lemma 2.9 to the graph induced by V ( C )with P = uJu,+1u3+2... u , - ~ u ,(by
the minimality of j - 2, IV(P)I 2 t + 4 > 2t - 5), we obtain a square-path P’ starting at
u7uJ+1and ending at u,-1uL2with V ( P ’ )= V ( P )u A. Then P’u,xQyuZLJ
is a square-cycle
of length at least c - t + IA( + 3, which implies that t > 5 with equality only if a1 \$ A.
This completes the proof of part (b), and so the lemma.
a
Proof of Theorem 4.1. Let C = u1u2. . . u,ul be a chord-maximum square-cycle in G.
Assume, contrary to assertion, that c < n/2. By Lemma 2.4, c > 5. Set H = G - C and
h = IV(H)I. So c < h. Let x E V ( H ) with d ( x , C ) = max{d(v,C) : ’u E V ( H ) } .By
Lemma 4.4(b), x E N ( U , ~ , +for~ )some 2. By relabeling, we assume that z E N ( u c u l ) ,
and again by Lemma 4.4(b), both N ~ ( u ~\ {x}
u ~=) 0 and N H ( U ~ U\ ?{x}
) = 0. If we also
have N ~ ( u 2 u\ ~{z}
) = 0, then d(u2u3u4,H ) 5 h + 2 and so
2n 5
G) 5
d ( ~ 2 ~ 3 ~ 4 ,h
+2 +3
( -~ I )
=
+ 2~
-
1,
+
which gives that c 2 ( n 1)/2, a contradiction. Therefore N , Z I ( U ~\U(z}
~ ) # 0. Let
y E N H ( u z u ~ ) \ { ~By
} . Lemma 4.4(a), u1x is connected to yu2 and to yu4 through squarepaths Q and &‘ in H , respectively, where lV(Q)l 1 and lV(Q’)I 1. If u2u5E E ( G ) ,then
u,ulxQyu2u4u5.. . u,ul is a square-cycle of length at least c+2. Thus u2u5@ E ( G ) .Since
>
>
x cannot be joined to four consecutive vertices on C, x \$ N ( u 2 u 3 )and so d(u2u3,H ) 5 h.
Consequently,
+
which gives that c 2 n / 3 3. Using c 5 ( n - 1)/2, we obtain that n > 21, and therefore,
c > 10. Now, if u3u6 E E ( G ) , then u , u l ~ Q y u 2 u 4 u ~ ~ u ~ uis~ a~ square-cycle
~ ~ u , u 1 of
length at least c + 3, which is impossible. So u3u6 \$ E ( G ) .Then, instead of (4.3, we
have that
4
-n 5 d ( ~ 2 ~G)
3 ,5 h + 2 ( ~ 1) - 2 = 72 + c - 4,
3
and as above, c 2 13. Using Lemma 4.4(b), we derive that
d ( u , ~ , + ~H, ) 5 h
+1
for all j, 2 5 j 5 7,
(4.6)
with equality j = 7 only if d ( u 2 ,H ) > h/2.
Case la. d ( u 3 , H ) 5 ( h 1)/2 and d ( u 5 , H ) 5 ( h + 1)/2. Let P = u5u6. . . u,ul
(= C - u2u3uq) and let D = C - u 4 (so u2u3is the single edge of D - P). By (4.6),
+
D)+d
d ( ~ 2 ~ 3 ,
( ~ g ~D
g ),
> 83
-TX
-
2(h
2
+ 1) - 4 = 2~ + -n
- 6.
3
Using n 2 2c + 1 and IV(D)I = c - 1,
and furthermore, since d(u3,H ) 5 ( h + 1)/2 and d(u5,H ) 5 ( h + 1)/2,
PARTITIONING INTO TWO SQUARE CYCLES 255
We have showed that u2u5 \$ E ( G ) and so u5 \$ N(u2u3),it follows from Lemma 2.10
that the subgraph induced by V ( D )has a hamiltonian square-path P’ starting at u2u3and
ending at u,u1. Then uCu1~Q’yu4u2u3P’
is a square-cycle of length at least c + 3.
Case lb. d ( u 3 , H ) 5 ( h 1 ) / 2 and d ( u 5 ,H ) > ( h 1 ) / 2 . Then by (4.61,d ( u 6 ,H ) 5
h/2. Let L = U g u 7 . . . U,UI and F = C - ~ 4 ~ We
5 . have that
+
d ( ~ 2 ~F3 ),
+
+
d ( ~ g ~F7 ),
8
- 2(h
3
2 -n
+ 1 ) - 8 2 10lV(F)I
3
-
8
and
d ( ~ yF, )
+
d ( ~ gF
, )
5
2
In the proof of c 2 13, we showed that u3u6 \$ E ( G ) , and so u6 f N(u2u3). It follows
from Lemma 2.10 that the subgraph induced by V ( F )has a hamiltonian square-path L’
starting at ~ 2 and
~ ending
3
at u,ul. Then u,u12Q’yu4u2u3P’ is a square-cycle of length
at least c + 2.
Case 2. d(u3,H)> ( h + 1 ) / 2 . By (4.6), d ( u 2 , H ) 5 h/2 and d ( u q , H ) 5 h/2. Since
d ( u 2 , H ) 5 h/2, we do not have equality j = 7 in (4.6) and so d ( u 7 u 8 , H ) 5 h + 1. As
and u1z is connected to zu3 and to zug by square-paths
before, we have z E N H(u3u5)\{~}
in H . Using d(u2, H ) 5 h/2 and n 2 2c 1 ,
+
2
h
3c+n
d(u2,C ) 2 -n - - = _ _
3
2
6
5c+1
6
2 -.
Let W = u7ulg.. . u,u1 and S = ~ 2 . . .~u6.3Since c 2 13, we have that IV(W)l = c - 5 2
8 > 2(V(S)I- 5. It follows from Lemma 2.9 that there is a square-path W’ starting at
u7u8and ending at u,ulwith V ( W ’ )= V ( W )U { u 2 } , and the proof is completed by the
same arguments as those used in Cases l a and lb.
5. PARTITION INTO TWO SQUARE-CYCLES
Theorem 5.1. Let G be a graph on n vertices with S(G) 2 \$n. Then G has two vertexdisjoint square-cycles C1 and C2 such that V ( C l )u V ( C 2 )= V ( G ) and C1 is chordmaximum.
Proof. If n 5 5 , G is complete and the theorem holds with C1 = G and C2 = 0. Assume
that n 2 6 and let C1 be a chord-maximum square-cycle of length c1 in G. By Lemma
2.4, c1 2 5. If c1 = n, the theorem holds with C2 = 0. We thus assume that c1 < n.
Let H = G - C and h = IV(H)I. By Theorem 4.1, c1 2 h. Let C2 be a chord-maximum
square-cycle of length c2 in H . If c2 = h, we are done, and thus we assume that c2 < h.
Set R = H - C2 and T = IR1. By Lemma 2.8, T 2 4.
If 27- 5 cl, let D = G - C2. Clearly C1 is also a chord-maximum square-cycle in D. If
d(v,C2) 5 \$c2 for all v E V ( R ) ,then d(v,D ) 2 \$ ( n- c 2 )for all v E V ( R ) ,and it follows
from Theorem 3.1 that 27- 2 cl, and so 27- = c1 and there is a triangle T in R such that
d(T,D ) = 2(n - c2).By Lemma 2.6, d ( T , C2) 5 2c2 - 1. It follows that
256 JOURNAL OF GRAPH THEORY
This contradiction shows that there is z E V ( R )such that d ( z , C 2 )2 (2c2 + 1)/3, which
means, by Lemma 2.l(b), that d ( z , C 2 )= (2c2 + 1)/3. Let D’ = G - C2 - z. By Lemma
2.3(a), for each w E V ( R- z), if d(v,C2)= (2c2 1)/3, then wz \$! E ( G ) ,which implies
> \$lV(D‘l for each w E V ( R- z). As before, 2 ( -~ 1) 2 el, a contradiction.
that d(w,0’)
If 2r 2 c1 + 1, then T 2 ( h + 1)/2 and c2 5 ( h - 1)/2. Since C2 is chord-maximum
in H and by Theorem 4.1, we have that S ( H ) < \$h. Thus there is x E V ( H ) such that
d(z,C1)= (2c1+1)/3 (so c1 = 1 (mod 3)). Let H’ = H - x . As before, S(H’) > \$lV(H’)I,
and it follows from Theorem 4.1 that H’ has a square-cycle of length at least ( h - 1)/2.
Therefore, c2 = ( h - 1)/2,r = ( h 1)/2, and c1 = h. Then n = 2 (mod 3) and so S(G) 2
(an 1)/3, which implies that S ( H ) 2 (2n 1)/3 - (2cl + 1)/3 = \$h, a contradiction.
This completes the proof of the theorem.
I
+
+
+
+
Note added in proofi Komlos, Siirkozy, and SzemerCdi have just used the Regularity Lemma and
a new lemma they call the Blow-up Lemma to prove that P6sa’s conjecture is true for sufficiently
large n, where “sufficiently large” means much more than Z1Oo.
References
[ 11
G. A. Dirac, Some theorems on abstract graphs. Proc. London Math Soc. 2 (1952), 68-81.
[2]
P. Erdos, Problem 9, Theory of Graphs and its Applications (M. Fieldler ed.), Czech. Acad. Sci.
Publ., Prague (1 964), 159.
[3]
G. Fan and R. Haggkvist, The square of a hamiltonian cycle, SIAM J. Discrete Math., 203-212.
[4]
G. Fan and H. A. Kierstead, The square of paths and cycles, J. Combinat. Theory Ser: B 63
(199% 5 5 4 4 .
[5]
G. Fan and H. A. Kierstead, Hamiltonian square-paths, preprint, .
I
.
Combinat. Theory Sex B,
in press.
(61
A. Hajnal and E. Szemeredi, Proof of a conjecture of P. Erdos, Combinatorid Theory and its
Application (P. Erdos, A. Renyi, and Vera T. Sos eds), North-Holland, London (1970), 601423.
[7]
P. Seymour, Problem section, Combinatorics: Proceedings of the British Combinatorid Conference 1973 (T. P. McDonough and V. C. Mavron eds), Cambridge University Press, Cambridge
(1974), 201-202.
Received April 18, I995
```
###### Документ
Категория
Без категории
Просмотров
3
Размер файла
1 027 Кб
Теги
229
1/--страниц
Пожаловаться на содержимое документа