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.

1/--страниц