close

Вход

Забыли?

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

?

468

код для вставкиСкачать
Closure, 2-Factors, and
Cycle Coverings in
Claw-Free Graphs
Zdeněk Ryjáček,1 Akira Saito,2 and R. H. Schelp3
1 DEPARTMENT OF MATHEMATICS
UNIVERSITY OF WEST BOHEMIA
UNIVERZITN´
I 22, 306 14 PLZEŇ
CZECH REPUBLIC
E-mail: ryjacek@kma.zcu.cz
2 DEPARTMENT OF MATHEMATICS
NIHON UNIVERSITY
SAKURAJOSUI 3-25-40
SETAGAYA-KU, TOKYO 156-8550
JAPAN
E-mail: asaito@math.chs.nihon-u.ac.jp
3 DEPARTMENT OF MATHEMATICAL SCIENCES
THE UNIVERSITY OF MEMPHIS
MEMPHIS, TN 38152
E-mail: schelpr@mathsci.msci.memphis.edu
Received January 16, 1997; revised January 31, 1999
Abstract: In this article, we study cycle coverings and 2-factors of a claw-free
graph and those of its closure, which has been defined by the first author (On a
closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217–224).
For a claw-free graph G and its closure cl(G), we prove: (1) V (G) is covered by
k cycles in G if and only if V (cl(G)) is covered by k cycles of cl(G); and (2) G
has a 2-factor with at most k components if and only if cl(G) has a 2-factor with
c 1999 John Wiley & Sons, Inc. J Graph Theory 32: 109–117, 1999
at most k components. Keywords: closure; claw-free graph; 2-factor; cycle covering
Contract grant sponsor: NSF
Contract grant number: DMS-9400530
Correspondence to: Akira Saito
c
1999 John Wiley & Sons, Inc.
CCC 0364-9024/99/020109-09
110 JOURNAL OF GRAPH THEORY
1. INTRODUCTION
For graph theoretic notation not defined in this article, we refer the reader to [2]. A
vertex x of a graph G is said to be locally connected, if the neighborhood NG (x)
of x in G induces a connected graph. A locally connected vertex x is said to be
eligible, if NG (x) induces a noncomplete graph. Let x be an eligible vertex of a
graph G. Consider the operation of joining every pair of nonadjacent vertices in
NG (x) by an edge, so that NG (x) induces a complete graph in the resulting graph.
This operation is called local completion of G at x. For a graph G, let G0 = G. For
i ≥ 0, if Gi is defined and it has an eligible vertex xi , then apply local completion
of Gi at xi to obtain a new graph Gi+1 . If Gi has no eligible vertex, let cl(G) = Gi
and call it the closure of G. The above operation was introduced, and the following
theorems were proved in [3].
Theorem A ([3]).
If G is a claw-free graph, then
(1) a graph obtained from G by local completion is also claw-free, and
(2) cl(G) is uniquely determined.
Theorem B ([3]). Let G be a claw-free graph. Then G, is Hamiltonian if and
only if cl(G) is Hamiltonian.
Recently, several other properties on paths and cycles of a claw-free graph and
those of its closure were studied in [1]. In particular, the following theorem was
proved.
Theorem C ([1]).
(1) A claw-free graph G is traceable if and only if cl(G) is traceable.
(2) There exist infinitely many claw-free graphs G such that cl(G) is Hamiltonianconnected, while G is not Hamiltonian-connected.
(3) For any positive integer k, there exists a k -connected claw-free graph G such
that cl(G) is pancyclic, while G is not pancyclic.
Let H1 , . . . , Hk be subgraphs of G. Then G is said to be covered by H1 , . . . , Hk
if V (G) = V (H1 ) ∪ · · · ∪ V (Hk ).
We consider two interpretations of a Hamiltonian cycle. First, a Hamiltonian
cycle of a graph G is a cycle that covers G. Second, it is considered as a 2-factor
with one component. These interpretations may lead us to possible extensions of
Theorem B to cycle coverings and 2-factors. This is the motivation of this article.
2. MAIN RESULTS
We prove the following theorems as generalizations of Theorem B.
Theorem 1. Let G be a claw-free graph. Then G is covered by k cycles if and
only if cl(G) is covered by k cycles.
CLOSURE, 2-FACTORS, AND CYCLE COVERINGS 111
Theorem 2. Let G be a claw-free graph. If cl(G) has a 2-factor with k components, then G has a 2-factor with at most k components.
Note that the conclusion of Theorem 2 says G has a 2-factor with ‘‘at most’’ k
components. Under the assumption of Theorem 2, G does not always have a 2-factor
with exactly k components, if k ≥ 2. Let G be a graph with k − 1 components
H1 , . . . , Hk−1 , where H1 is the graph shown in Fig. 1, and H2 , . . . , Hk−1 are
cycles of arbitrary lengths. Then G is claw-free and cl(G) = cl(H1 ) ∪ H2 ∪
· · · ∪ Hk−1 , where cl(H1 ) is isomorphic to K9 . Since K9 has a 2-factor with two
components, cl(G) has a 2-factor with k components. However, G has no 2-factor
with k components, since H1 does not have a 2-factor with two components.
Before proving the above theorems, we introduce some notation that is used in
/ S ⊂ V (G), the subgraph induced
the subsequent arguments. For a graph G and ∅ =
by S is denoted by G[S]. When we consider a path or a cycle, we always assign an
orientation. Let P = x0 x1 · · · xm . We call x0 and xm the starting vertex and the
terminal vertex of P , respectively. The set of internal vertices of P is denoted by
int(P ): int(P ) = {x1 , x2 , . . . , xm−1 }. The length of P is the number of edges in P ,
+(P )
−(P )
= xi+1 and xi
= xi−1 . Furthermore,
and is denoted by l(P ). We define xi
++(P )
= xi+2 . When it is obvious which path is considered in the
we define xi
+(P )
−(P )
−
context, we sometimes write x+
and xi
, respectively.
i and xi instead of xi
→
For xi , xj ∈ V (P ) with i ≤ j , we denote the subpath xi xi+1 · · · xj by xi P xj . The
←
same path traversed in the opposite direction is denoted by xj P xi . We use similar
notations with respect to cycles with a given orientation.
We present several lemmas before proving the main theorems.
Lemma 1. Let G be a claw-free graph, and let x be a locally connected vertex.
Let T1 , T2 ⊂ V (G) with T1 ∩ T2 = {x}. Suppose that both G[T1 ] and G[T2 ]
are Hamiltonian, but G[T1 ∪ T2 ] is not Hamiltonian. Choose cycles C1 and C2
with V (C1 ) ∪ V (C2 ) = T1 ∪ T2 and V (C1 ) ∩ V (C2 ) = {x} and a path P in
G[NG (x)] with starting vertex in {x+(C1 ) , x−(C1 ) } and terminal vertex in {x+(C2 ) ,
x−(C2 ) }, so that P is as short as possible. Then 2 ≤ l(P ) ≤ 3 and int(P ) ∩
(T1 ∪ T2 ) = ∅.
FIGURE 1.
112 JOURNAL OF GRAPH THEORY
Proof. First, note that each Hamiltonian cycle Di in G[Ti ] (i = 1, 2) satisfies
V (D1 ) ∪ V (D2 ) = T1 ∪ T2 and V (D1 ) ∩ V (D2 ) = {x}. Furthermore, since x is a
locally connected vertex of G, there exists a path in G[NG (x)] with starting vertex
in {x+(D1 ) , x−(D1 ) } and terminal vertex in {x+(D2 ) , x−(D2 ) }. Therefore, we can
make a choice for (C1 , C2 , P ). Let u1 = x+(C1 ) , v1 = x−(C1 ) , u2 = x+(C2 ) , and
v2 = x−(C2 ) . We may assume that the starting and terminal vertices of P are u1
and u2 , respectively.
←
→
If u1 u2 ∈ E(G), then C 0 = xv1 C 1 u1 u2 C 2 v2 x is a cycle in G with V (C 0 ) =
V (C1 ) ∪ V (C2 ) = T1 ∪ T2 . This contradicts the assumption. Hence, we have
u1 u2 ∈
/ E(G). Similarly, we have u1 v2 , v1 u2 , v1 v2 ∈
/ E(G). Since {u1 , v1 , u2 } ⊂
NG (x) and G is claw-free, we have u1 v1 ∈ E(G). Similarly, u2 v2 ∈ E(G).
+(P )
/ V (C1 ) ∪ V (C2 ). Assume that w ∈ V (C1 ) ∪
Let w = u1 . We claim w ∈
→
→
V (C2 ). Since w ∈ V (P ) ⊂ NG→
(x), w =
/ x. Thus, w ∈ u1 C 1 v1 ∪ u2 C 2 v2 . →
−
First, suppose that w ∈ u1 C 1 v1 . Then by the choice of P, w ∈ u+
1 C 1 v1 .
+ , xw − , w + w − } ∩
Since {x, w+ , w− } ⊂ NG (w) and G is claw-free,→we have {xw
→
+
−
0
−
+
E(G) =
/→∅. If w w ∈ E(G), let C1 = xwu1 C→1 w w →C 1 v1 x, C20 = C2 , and
0
P = w→
P u2 . If w− x ∈ E(G), then let C10 = xw←
C 1 v1 u1 ←
C 1 w− x, C20 = C2 , and
0
+
0
P = w→P u2 . If w x ∈ E(G), then let C1 = xw C 1 u1 v1 C 1 w+ x, C20 = C2 , and
P 0 = w P u2 . Then in each case, since V (C10 ) = V (C1 ), we have V (C10 )∪V (C20 ) =
0
V (C1 ) ∪ V (C2 ) = T1 ∪ T2 , and V (C10 ) ∩ V (C20 ) = {x}. Furthermore, w = x+(C1 )
and l(P 0 ) < l(P ). This contradicts
the choice of (C1 , C2 , P ).
→
Now,
suppose
that
w
∈
u
C
v
.
Since {u2 , v2 } ∩ NG (u1 ) = ∅, we have w ∈
2
2
2
→
−
− , w + } ⊂ N (w) and G is claw-free, {xw − , xw + , w − w + }
C
v
.
Since
{x,
w
u+
G
2 2 2
←
→
→
∩ E(G) =
/ ∅. If xw−→ ∈ E(G)
,
let
C = xv1 C 1 u1 w C 2 v2 u2 C 2 w− x. If xw+ ∈
→
→
E(G), let C = xw+ C 2 v2 u2 C 2 wu1 C 1 v1 x. Then, in either case, C is a cycle in
G with V (C) = V (C1 ) ∪ V (C2 ) = T1 →∪ T2 . This contradicts
the assumption.
+ ∈ E(G), then let C 0 = xwu C v x, C 0 = xu →
− w+ →
If w− w→
C
w
C 2 v2 x, and
1 1 1
2 2
1
2
0
0
0
0
P = w P u2 . Then V (C1 )∪V (C2 ) = V (C1 )∪V (C2 ) = T1 ∪T2 , V (C1 )∩V (C20 ) =
0
{x}, w = x+(C1 ) and l(P 0 ) < l(P ). This contradicts the choice of (C1 , C2 , P ).
Therefore, w ∈
/ V (C1 ) ∪ V (C2 ).
−(P )
Let w0 = u2 . (Possibly w0 = w.) Then, by the same arguments, we have
w0 ∈
/ V (C1 ) ∪ V (C2 ).
By the choice of (C1 , C2 , P ), P is an induced path. Hence, if l(P ) ≥ 4, then
++(P )
{u1 , u1
, u2 } is an independent set. Since V (P ) ⊂ NG (x) and G is claw-free,
this is a contradiction. Thus, l(P ) ≤ 3. Since u1 u2 ∈
/ E(G), l(P ) ≥ 2. These
imply int(P ) ∩ (T1 ∪ T2 ) = ∅.
By similar arguments, we have the following lemma.
Lemma 2. Let G be a claw-free graph, and let x be a locally connected vertex
of G. Let T ⊂ V (G) with x ∈ T, and let u ∈ NG (x) − T. Suppose that G[T ]
is Hamiltonian, but G[T ∪ {u}] is not Hamiltonian. Choose a Hamiltonian cycle
C in G[T ], and a path P in G[NG (x)] with starting vertex in {x+(C) , x−(C) } and
terminal vertex u, so that P is as short as possible. Then 2 ≤ l(P ) ≤ 3 and
int(P ) ∩ (T ∪ {u}) = ∅.
CLOSURE, 2-FACTORS, AND CYCLE COVERINGS 113
We prove one more lemma.
Lemma 3. Let G be a claw-free graph, and let x be an eligible vertex of G. Let
G0 be the graph obtained from G by local completion at x. Let C 0 be a cycle in G0
with x ∈ V (C 0 ). Then either (1) or (2) follows:
(1)
(2)
(2.1)
(2.2)
There exists a cycle C in G with V (C) = V (C 0 ).
There exist T1 , T2 ⊂ V (G) such that
T1 ∪ T2 = V (C 0 ) and T1 ∩ T2 = {x}, and
G[Ti ] is Hamiltonian or isomorphic to K2 (i = 1, 2).
Proof. Let B = E(G0 ) − E(G). Note that, for each uv ∈ B, {u, v} ⊂ NG (x).
Choose a cycle C in G0 with V (C) = V (C 0 ), so that |E(C) ∩ B| is as small as
possible. If E(C) ∩ B = ∅, then C is a cycle satisfying (1). Therefore, we may
assume E(C) ∩ B =
/ ∅.
We claim |E(C) ∩ B| = 1. Assume, to the contrary, that |E(C) ∩ B| ≥ 2, say
e1 , e2 ∈ E(C) ∩ B, e1 =
/ e2 . Let ei = xi yi (i = 1, 2). We may assume x1 , y1 ,
x2 , y2 and x appear in this order along C . (Possibly, y1 = x2 .) Then x1 , x2 ,
is claw-free,
{x1 x2 , x1 x− , x2 x− } ∩
and x− are distinct vertices in NG (x). Since G
→
←
E(G) =
/ ∅. If x1 x2 ∈ E(G), let C0 = y2 C x1 x2 C y1 y2 . Then V (C0 ) = V (C)
and E(C0 ) = (E(C) − {x1 y1 , x2 y2 }) ∪ {x1 x2 , y1 y2 }. This implies |E(C0 ) ∩
B| < |E(C) ∩ B|,→which←contradicts the minimality of |E(C) ∩ B|. If x1 x− ∈
E(G), let C0 = x C x1 x− C y1 x. Then V (C0 ) = V (C) and E(C0 ) = (E(C) −
{x1 y1 , xx− }) ∪ {xy1 , x1 x− }. Since xy1 ∈ E(G), we have |E(C0 ) ∩ B| <
|E(C) ∩ B|, again a contradiction. We have a similar contradiction, if x− x2 ∈
E(G). Therefore, the claim is proved.
Let E(C) ∩ B = {x1 y1 }→. We may assume→that x, x1 , and y1 appear in this
and
order along C . Let T1 = x C x1 and T2 = y1 C x. Then T1 ∪ T2 = V (C)
→
T1 ∩ T2 = {x}. Since x1 y1 ∈ B, xx1 , xy1 ∈ E(G). If x1 =
/ x+ , then x C x1 x is
a Hamiltonian cycle in G[T1 ]. If x1 = x+ , then G[T1 ] ' K2 . Similarly, G[T2 ] is
either Hamiltonian or isomorphic to K2 .
Let G0 be a graph obtained from a claw-free graph by local completion at a
vertex. Using Lemmas 1, 2, 3 we prove that for each cycle in G0 there exists a cycle
in G that contains it. We can also impose some restriction on its length.
Theorem 3. Let G be a claw-free graph, and let x be a locally connected vertex
of G. Let G0 be the graph obtained from G by local completion at x. Then for each
cycle C 0 in G0 there exists a cycle C in G with V (C 0 ) ⊂ V (C) and l(C 0 ) ≤ l(C) ≤
l(C 0 ) + 3.
Proof. If E(C 0 ) ∩ (E(G0 ) − E(G)) = ∅, then C 0 is a required cycle. Hence,
we may assume E(C 0 ) ∩ (E(G0 ) − E(G)) =
/ ∅.
/ V (C 0 ). Let e = u+(C1 ) ∈
If x ∈ V (C 0 ), let C10 = C 0 . Suppose that x ∈
0)
0
0
0
+(C
E(C ) ∩ (E(G ) − E(G)). Then {u, u
} ⊂ NG (x). Let C10 = u+(C )
→
0
C 0 uxu+(C ) . In either case, we have a cycle C10 with V (C 0 ) ∪ {x} ⊂ V (C10 )
and l(C 0 ) ≤ l(C10 ) ≤ l(C 0 ) + 1.
114 JOURNAL OF GRAPH THEORY
If there exists a cycle C in G with V (C10 ) = V (C), then C is a required cycle.
Therefore, we may assume that G has no such cycle. Then, by Lemma 3, there
exist T1 , T2 ⊂ V (G) with T1 ∩ T2 = {x}, and T1 ∪ T2 = V (C10 ) such that G[T] is
Hamiltonian or G[Ti ] ' K2 .
Suppose that both G[T1 ] and G[T2 ] are Hamiltonian. Then by Lemma 1 there
exist cycles C1 and C2 in G and a path P in G[NG (x)] such that
(1) V (C1 ) ∪ V (C2 ) = T1 ∪ T2 = V (C10 ), V (C1 ) ∩ V (C2 ) = {x}, and
(2) P joins {x+(C1 ) , x−(C1 ) } and {x+(C2 ) , x−(C2 ) }, 2 ≤ l(P ) ≤ 3 and int(P ) ∩
(T1 ∪ T2 ) = ∅.
1 ) and v = x+(C2 ) . We may assume that P joins u and v . Let
u =→x+(C
Let ←
→
C = x C 1 u P v C 2 x. Then C is a cycle in G, V (C10 ) ⊂ V (C), and l(C10 ) ≤ l(C) ≤
l(C10 ) + 2. Therefore, V (C 0 ) ⊂ V (C10 ) ⊂ V (C), and l(C 0 ) ≤ l(C10 ) ≤ l(C) ≤
l(C10 ) + 2 ≤ l(C 0 ) + 3.
Using Lemma 2 instead of Lemma 1, we can, by similar arguments, deal with
the case in which G[T1 ] or G[T2 ] is isomorphic to K2 .
Now Theorem 1 is a consequence of the following corollary of Theorem 3.
Corollary 1. Let G be a claw-free graph, and let x be an eligible vertex of G.
Let G0 be the graph obtained from G by local completion at x. Then G is covered
by k cycles if and only if G0 is covered by k cycles.
Proof. Since the ‘‘only if’’ part is trivial, we have only to prove the ‘‘if’’ part
of the corollary. Suppose G0 is covered by k cycles, say V (G0 ) = V (C10 ) ∪ · · · ∪
V (Ck0 ) for cycles C10 , . . . , Ck0 in G0 . By Theorem 3 for each Ci0 there exists
a cycle Ci in G with V (Ci0 ) ⊂ V (Ci ) (1 ≤ i ≤ k). Then V (G) = V (C1 ) ∪
· · · ∪ V (Ck ).
Now we prove Theorem 2. Actually, we prove a stronger statement.
Theorem 4. Let G be a claw-free graph, and let x be an eligible vertex of G.
Let G0 be the graph obtained from G by local completion at x. Then for each set of
k disjoint cycles {D1 , . . . , Dk } in G0 there exists a set of at most k disjoint cycles
{C1 , . . . , Cl } (l ≤ k) in G with ∪ki=1 V (Di ) ⊂ ∪li=1 V (Ci ).
Proof. Let S0 = ∪ki=1 V (Di ). Assume, to the contrary, that G[S] has no 2factor with at most k components for any S ⊂ V (G) with S0 ⊂ S . Let B =
E(G0 ) − E(G). Note {a, b} ⊂ NG (x) for each ab ∈ B . Let
F = {(S, F ): S0 ⊂ S ⊂ V (G) and F is a 2-factor of G0 [S]}.
Since (S0 , ∪ki=1 E(Di )) ∈ F, F =
/ ∅. Let F0 be the set of pairs (S, F ) ∈ F , chosen
so that
CLOSURE, 2-FACTORS, AND CYCLE COVERINGS 115
(a) the number of components of F is as small as possible, and
(b) |F ∩ B| is as small as possible, subject to (a).
Let (S, F ) ∈ F0 . Suppose that F consists of l components (cycles) C1 , . . . , Cl :
F = E(C1 ) ∪ · · · ∪ E(Cl ) (disjoint). Since (S0 , ∪ki=1 E(Di )) ∈ F, l ≤ k . By the
/ ∅.
assumption F ∩ B =
If x ∈
/ S , choose i with
E(Ci ) ∩ B =
/ ∅, say e = uv ∈ E(Ci ) ∩ B and
→
v = u+(Ci ) . Let Ci0 = xv C i ux and F 0 = (F − E(Ci )) ∪ E(Ci0 ). Then F 0 is a
2-factor of G0 [S ∪ {x}] with l components and |F 0 ∩ B| = |F ∩ B| − 1. This
contradicts the choice of (S, F ) given in (b). Therefore, we have x ∈ S . We may
assume x ∈ V (C1 ).
We claim B ∩ (∪li=2 E(Ci )) = ∅. Assume that B ∩ (∪li=2 E(Ci )) =
/ ∅, say
f = u0 v 0 ∈ B ∩ E(Cj ) (j ≥ 2). Then {u0 , v 0 , x+(C1 ) } ⊂ NG (x) and, hence,
+(C1 ) ∈ E(G0 ). We may assume that j = 2 and v 0 = u0+(C2 ) . Let C 0 =
u0 x→
→
0
xv C 2 u0 x+(C1 ) C 1 x and F 0 = (F − (E(C1 ) ∪ E(C2 ))) ∪ E(C 0 ). Then F 0 is a
2-factor of G0 [S] with l − 1 components. This contradicts the choice of (S, F ).
Since F ∩ B =
/ ∅, B ∩ E(C1 ) =
/ ∅. If there exists a cycle C10 in G with
V (C10 ) = V (C1 ), then (F − E(C1 )) ∪ E(C10 ) is a 2-factor of G[S] with l components. This contradicts the assumption. Since x ∈ V (C1 ), by Lemma 3, there
exist T0 , T1 ⊂ V (G) such that T0 ∪ T1 = V (C1 ), T0 ∩ T1 = {x}, and G[T] is
Hamiltonian or isomorphic to K2 (i = 0, 1).
First, consider the case in which both G[T0 ] and G[T1 ] are Hamiltonian. Let
C00 and C10 be cycles in G[T0 ∪ T1 ] with V (C00 ) ∪ V (C10 ) = T0 ∪ T1 = V (C1 )
0
0
and V (C00 ) ∩ V (C10 ) = {x}. Let ui = x+(Ci ) and vi = x−(Ci ) (i = 0, 1). Since
x is a locally connected vertex of G, G[NG (x)] has a path P with starting vertex
in {u0 , v0 } and terminal vertex in {u1 , v1 }. Since G[S] has no 2-factors with l
components, u0 u1 , u0 v1 , v0 u1 , v0 v1 ∈ B . By the choice of (S, F ) given in (b),
|E(C1 ) ∩ B| = 1.
Now choose (S, F ) ∈ F0 , C00 , C10 , and P so that
(c) P is as short as possible.
Then by Lemma 1, 2 ≤ l(P ) ≤ 3 and int(P ) ∩ V (C1 ) = ∅. We may assume that
the starting vertex and the terminal vertex of P are v0 and u1 , respectively.
+(P )
/ V (C1 ). Assume that a ∈
/ S . Since V (P ) ⊂ NG (x),
Let a = v0 . Then a ∈
→
→
ax ∈ E(G) and, hence, au1 ∈ E(G0 ). Let C 0 = xu0 C 00 v0 au1 C 01 v1 x and F 0 =
(F − E(C1 )) ∪ E(C 0 ). Then F 0 is a 2-factor of G0 [S ∪ {a}] with l components,
and F 0 ∩B→⊂ {au1 }. Since |B∩E(C1 )| = 1, |F 0 ∩B| = |F ∩B| = 1. Furthermore,
C000 = xu0 C 00 v0 ax and C100 = C10 are two→cycles in G with V (C000 )∪V (C100 ) = V (C 0 )
and V (C000 ) ∩ V (C100 ) = {x}. Since a P u1 is shorter than P , this contradicts the
choice of (S, F ) given in (c). Therefore, we have a ∈ S . We may assume that
a ∈ V (C2 ). Let a0 = a+(C2 ) and a00 = a−(C2 ) .
If a0 x ∈ E(G), then {a0 , u1 } ⊂ NG (x) and, hence, a0 u1 ∈ E(G0 ). Let
→
←
→
C 0 = xu0 C 00 v0 a C 2 a0 u1 C 01 v1 x
116 JOURNAL OF GRAPH THEORY
and F 0 = (F − (E(C1 ) ∪ E(C2 ))) ∪ E(C 0 ). Then F 0 is a 2-factor of G0 [S] with
l − 1 components. This contradicts the choice of (S, F ). Hence, we have a0 x ∈
/
/ E(G). Since a and→ {x, a0 , a→00 } do
E(G). By the same argument, we have a00 x ∈
not form a claw in G, a0 a00 ∈ E(G)
. If l(C2 ) ≥ 4, let C 0 = xu0 C 00 v0 au1 C 01 v1 x
→
0
00
0
(note au1 ∈ E(G )), C = a C 2 a00 a0 and F 0 = (F − (E(C1 ) ∪ E(C2 ))) ∪
E(C 0 ) ∪ E(C 00 ). Then F 0 is a 2-factor of G0 [S] with l components and F 0 ∩
B ⊂→ {au1 }. Since |B ∩ E(C1 )| = 1, |F 0 ∩ B| = |F ∩ B|. Furthermore, C000 =
xu0 C 00 v0 ax and C100 = C10 are two cycles
in G with V (C000 ) ∪ V (C100 ) = V (C 0 )
→
00
00
and V (C0 ) ∩ V (C1 ) = {x}. Since a P u1 is shorter than P , this contradicts the
choice of (S, F ) given in (c). Therefore, we have l(C2 ) = 3, which implies
C2 = aa0 a00 a.
→
→
If a0 ∈ NG (v0 ), let C 0 = xu0 C 00 v0 a0 a00 au1 C 01 v1 x and F 0 = (F − (E(C1 ) ∪
E(C2 ))) ∪ E(C 0 ). Then F 0 is a 2-factor of G0 [S] with l − →
1 components.
This
→
0
0
0
0
00
0
contradicts the choice of (S, F ). If a ∈ NG (u1 ), let C = xu0 C 0 v0 aa a u1 C 1 v1 x
and F 0 = F − ((E(C1 ) ∪ E(C2 ))) ∪ E(C 0 ). Then F 0 is a 2-factor of G0 [S] with
l − 1 components, which contradicts the assumption. Therefore, a0 ∈
/ NG (v0 ) ∩
NG (u1 ). Similarly, a00 ∈
/ NG (v0 ) ∪ NG (u1 ).
−(P )
Let b = u1 . Let b ∈ V (Ci ), 2 ≤ i ≤ l, b0 = b+(Ci ) , and b00 = b−(Ci ) . By
symmetry, we have {b0 , b00 } ∩ (NG (x) ∪ NG (u1 ) ∪ NG (v0 )) = ∅ and l(Ci ) = 3.
Suppose that l(P ) = 2. Then b = a and, hence, Ci = C2 . Since a0 ∈
/ NG (v0 ) ∪
/ E(G), a and {a0 , v0 , u1 } form a claw in G, a contradiction.
NG (u1 ) and v0 u1 ∈
/ E(G), Ci =
/ C2 . We may assume
Therefore, we have l(P ) = 3. Since u1 a0 , u1 a00 ∈
that b ∈ V (C3 ).
/ E(G). Since v0 a0 ∈
/ E(G) and a
By the choice of P given in (c), bv0 , au1 ∈
0
0
and {a , b, v0 } do not form a claw, a b ∈ E(G). Similarly, we have a00 b, ab0 , ab00 ∈
E(G). Now let C 0 = aa00 a0 bb0 b00 a and F 0 = (F − (E(C2 ) ∪ E(C3 )) ∪ E(C 0 ).
Then F 0 is a 2-factor of G0 [S] with l − 1 components. This contradicts the choice
of (S, F ) given in (a), and the theorem follows in this case.
By replacing Lemma 1 with Lemma 2, we can follow the same arguments to
obtain a contradiction if G[T1 ] or G[T2 ] is isomorphic to K2 . Therefore, the theorem
is proved.
3. CONCLUDING REMARKS
Let S be a set of vertices in a claw-free graph G. Then by Theorem 3, the minimum number of cycles covering S in G is the same as the minimum number of cycles covering S in cl(G). Furthermore, by Theorem 4, the minimum
number of disjoint cycles covering S in G is the same as the minimum number of disjoint cycles covering S in cl(G), if there exist such cycles. Therefore,
these invariants (and, hence, the minimum number of cycles covering V (G)) are
stable in the sense of [1]. Furthermore, the existence of a 2-factor is a stable
property.
CLOSURE, 2-FACTORS, AND CYCLE COVERINGS 117
ACKNOWLEDGMENTS
This research was carried out while Z.R. and A.S. visited the Department of Mathematical Sciences, The University of Memphis. These authors are grateful for the
hospitality extended during their stay.
References
[1] S. Brandt, O. Favaron, and Z. Ryjáček, Closure and stable hamiltonian properties in claw-free graphs, preprint.
[2] G. Chartrand and L. Lesniak, Graphs & digraphs, 2nd Ed., Wadsworth &
Brooks/Cole, Monterey, CA, 1986.
[3] Z. Ryjáček, On a closure concept in claw-free graphs, J Combin Theory Ser
B 70 (1997), 217–224.
Документ
Категория
Без категории
Просмотров
2
Размер файла
239 Кб
Теги
468
1/--страниц
Пожаловаться на содержимое документа