 Забыли?

?

# 229

код для вставкиСкачать
```Partitioning a Graph into
Two Square-Cycles
Genghua Fan
H. A. Kierstead"
DEPARTMENT 0F MATHEMATICS
ARIZONA STATE UNIVERSITY
TEMPE, AZ 85287
e-mai1:fanQmath./a.asu.edu
e-mail:kierstead@math.la.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 ) conjectured that if
S(G) 2 \$n,then G contains a hamiltonian square-cycle. In 1973 Seymour  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
 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  proved that if S(G) 2 :n, then G contains a
hamiltonian square-cycle. Fan and Kierstead  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  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 , 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
contradiction proves (a).
+
+
+ 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)
a contradiction.
+ 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 , 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 , 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.

P. Erdos, Problem 9, Theory of Graphs and its Applications (M. Fieldler ed.), Czech. Acad. Sci.
Publ., Prague (1 964), 159.

G. Fan and R. Haggkvist, The square of a hamiltonian cycle, SIAM J. Discrete Math., 203-212.

G. Fan and H. A. Kierstead, The square of paths and cycles, J. Combinat. Theory Ser: B 63
(199% 5 5 4 4 .

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.

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/--страниц
Пожаловаться на содержимое документа