Hamiltonian k-Factors in Graphs* Bing Wei† and Yongjin Zhu INSTITUTE OF SYSTEMS SCIENCE ACADEMIA SINICA BEIJING 100080, CHINA E-mail: wei@bamboo.iss.ac.cn Received August 24, 1994 Abstract: Let k ≥ 2 be an integer. A k-factor F of a graph G is called a hamiltonian k-factor if F contains a hamiltonian cycle. In this paper, we shall prove that if G is a graph of order n with k ≥ 2, n ≥ 8k − 4, kn even and δ(G) ≥ n/2, then G has a hamiltonian c 1997 John Wiley & Sons, Inc. J Graph Theory 25: 217–227, 1997 k-factor. Keywords: hamiltonian cycles, k-factors, hamiltonian k-factors 1. INTRODUCTION We consider only finite undirected graphs without loops and multiple edges. The set of vertices of a graph G is denoted by V (G) or just by V ; the set of edges by E(G) or just by E. We use |G| as a symbol for the cardinality of V (G). If H and S are subsets of V (G) or subgraph of G, we denote by NH (S) the set of vertices in H which are adjacent to some vertex in S and set |NH (S)| = dH (S). In particular, when H = G and S = {u}, then let NG (u) = N (u) and set dG (u) = d(u). As usual, we use δ(G) for the minimum degree of G. For basic graph-theoretic terminology, we refer the reader to [2]. A k-regular spanning subgraph of G is called a k-factor. If a k-factor F contains a hamiltonian cycle we call it a hamiltonian k-factor (Hk-factor, for short). The following result is due to Dirac [3]. Theorem 1. Let G be a graph of order n ≥ 3 with δ(G) ≥ n/2. Then G is hamiltonian. * Supported by National Natural Science Foundation of China. † Supported also by a foundation of the National Education Committee of China. c 1997 John Wiley & Sons, Inc. CCC 0364-9024/97/030217-11 218 JOURNAL OF GRAPH THEORY Obviously, if a graph G is hamiltonian, then G has a H2-factor, because a hamiltonian cycle itself is a H2-factor. But for k ≥ 3, the situation is quite different, because the existence of a hamiltonian cycle or a k-factor or even both can not guarantee the existence of a Hk-factor. In this paper, we shall prove the following sufficient condition for the existence of a Hk-factor in G. Theorem 2. Let G be a graph of order n with k ≥ 2, n ≥ 8k − 4, kn even and δ(G) ≥ n/2. Then G has a Hk-factor. In order to prove Theorem 2, we need the following results. Theorem 3 [5]. Let G be a graph of order n ≥ 20 with δ(G) ≥ 5 and d(x) + d(y) ≥ n for any nonadjacent vertices x, y of G. Then G contains at least two edge disjoint hamiltonian cycles. From Theorem 3, we can easily get that under the conditions of Theorem 2, G has a Hk-factor for k = 3, 4. Theorem 4 [1]. Let u, v be two nonadjacent vertices of a graph G satisfying d(u) + d(v) ≥ n. Then G is hamiltonian if and only if G + uv is hamiltonian. Theorem 5 [1]. Let u, v be two nonadjacent vertices of a graph G satisfying d(u) + d(v) ≥ n + 2k − 4, where k ≥ 2 is an integer. Then G has a k-factor if and only if G + uv has a k-factor. Theorem 6 [2]. Let G = (X, Y, E) be a complete bipartite graph with X = {x1 , x2 , . . . , xs } and Y = {y1 , y2 , . . . , ym }. For two integer sequences P = {p1 , . . . , ps } and Q = {q1 , . . . , qm } with pi ≥ 0, qj ≥ qj+1 ≥ 0, there exists a subgraph F of G with dF (xi ) = pi (1 ≤ i ≤ s) and dF (yj ) = qj (1 ≤ j ≤ m) if and only if for any 1 ≤ r ≤ m, s X min{pi , r} ≥ i=1 r X qj . j=1 2. PROOFS In this section, we assume that G satisfies the conditions of Theorem 2. By Theorem 1 and Theorem 3, we only need to consider the case that k ≥ 5. Let t = k − 2. Then t ≥ 3. If there exists a hamiltonian cycle C in G such that G \ C has a t-factor, then Theorem 2 holds. Hence, in the rest of this section, assume that there is no hamiltonian cycle C in G such that there is a t-factor in G \ C. Since δ(G) ≥ n/2, by Theorem 3, we may choose a hamiltonian cycle C such that G \ C is connected. Set G1 = G \ C. Then by a theorem of Tutte [6], there exist disjoint subsets A and B of V (G1 ) = V (G) satisfying X (dG1 \A (x) − t) − w(A, B), (1) −2 ≥ t|A| + x∈B where w(A, B) denotes the number of components in G1 \ (A ∪ B). Let a := |A| and b := |B|. Now, we choose two disjoint subsets A and B which satisfy (1) and have the properties (a) a + b is as large as possible and (b) under (a), b is as large as possible. Clearly, we have w(A, B) ≤ n − a − b. (2) If w(A, B) ≥ 1, let γ be the least order of components in G1 \ (A ∪ B). Then by a result of Katerinis and Woodall [4, Lemma 1], we have γ ≥ 3. Hence, in this case, we have 3w(A, B) ≤ γw(A, B) ≤ n − a − b (3) HAMILTONIAN k-FACTORS IN GRAPHS 219 and δ(G1 ) ≤ γ − 1 + a + b. If B = / ∅, let h = min{dG1 \A (x) : x ∈ V (B)} and θh = P x∈B (4) dG1 \A (x) − hb. Then −2 ≥ ta + (h − t)b − w(A, B) + θh . (5) If B = / ∅, by δ(G) ≥ n/2, we have a ≥ n/2 − 2 − h. (6) Proposition 1. w(A, B) = 0. Proof. Assume that w(A, B) ≥ 1. Then γ ≥ 3. If B = ∅, then by (1)–(4), we can get A = / ∅ since G1 is connected. Thus we have w(A, B) ≥ 5 and (n − a)/3 ≥ (n − a)/γ ≥ w(A, B) ≥ ta + 2 ≥ 5. (7) a ≤ (n − 6)/(3t + 1) ≤ (n − 6)/10. (8) By t ≥ 3, we have Since a ≥ 1, by (4), (7) and (8), we can get δ(G1 ) ≤ γ − 1 + a < (n − a)/w(A, B) + (n − 6)/10 ≤ (n − 1)/5 + (n − 6)/10 ≤ (3n − 8)/10, contrary to the fact that δ(G1 ) ≥ n/2 − 2 and k ≥ 5. Hence B = / ∅. We distinguish the following three cases. Case 1. h ≥ t + 1. By (5), we have w(A, B) ≥ ta + (h − t)b + 2 ≥ 3a + b + 2 ≥ a + b + 2. This implies that γ ≤ (n − a − b)/w(A, B) ≤ (n − a − b)/(a + b + 2). Thus (γ + 1)(a + b + 2) ≤ n + 2. (9) If a + b + 2 ≥ 4, then by γ + 1 ≥ 4 and (4), (9), we can get δ(G1 ) ≤ γ − 1 + a + b ≤ γ + 1 + a + b + 2 − 4 ≤ 2(n + 2)/4 − 4 = n/2 − 3, contrary to the fact that δ(G1 ) ≥ n/2 − 2. If a + b + 2 = 3, then b = 1 and a = 0. By (4) and (9) we have n/2 − 2 ≤ δ(G1 ) ≤ γ − 1 + b ≤ (n − 1)/3. Thus n ≤ 10, a contradiction. Case 2. t = h. By (3) and (5), we have w(A, B) ≥ ta + 2 and γ ≤ (n − a − b)/w(A, B) ≤ (n − a − b)/(ta + 2). If a = 0, then by (6) we have n/2 − 2 ≤ h + a = t. Thus, n ≤ 2t + 4 = 2(t + 2) = 2k. Hence 6k ≤ 4 by n ≥ 8k − 4, contrary to k ≥ 5. (10) 220 JOURNAL OF GRAPH THEORY If a ≥ 1, then by (t − 1)(a − 1) ≥ 0 and (6), we have ta + 2 ≥ h + a + 1 ≥ n/2 − 1. Thus by (10), γ ≤ 2(n − a − b)/(n − 2) ≤ 2, a contradiction. Case 3. 0 ≤ h ≤ t − 1. By (3), w(A, B) ≤ n − a − b − 2w(A, B). Now by (5), we have −2 ≥ ta + (h − t)b + (t − h + h − t − 1)w(A, B) + θh ≥ ta + (h − t)b − (t − h)(n − a − b − 2w(A, B)) + t − h − 1 + θh . This implies (t − h)n ≥ (2t − h)a + (2w(A, B) + 1)(t − h) + 1 + θh . If w(A, B) ≥ 2, then by (6), we can easily get 0 ≥ (n/2 − 2t − 5)h + h(h + 2) + t + 1 + θh which is impossible by n ≥ 8k − 4 = 8t + 12. If w(A, B) = 1, (t − h)n ≥ (2t − h)a + 3(t − h) + 1 + θh . Thus t ≥ (n/2 − 2t − 3)h + h(h + 2) + 1 + θh by (6). By n ≥ 8k − 4 = 8t + 12, we can get h = 0 and θ0 ≤ t − 1. Now, by h = 0 and (5), we have b > a. Since γ ≥ 3, we have a = n/2 − 2 by (6) and b = n/2 − 1 by (3). Let U := G1 \ (A ∪ B). Then |U | = 3 and X X dB (z) ≤ dG1 \A (y). (11) z∈U P y∈B By (1), y∈B dG1\A (y) ≤ t − 1. If there exists a vertex z ∈ U such that dG1 \A (z) ≤ t, set B 0 = B ∪ {z}. Then X X (dG1 \A − t) − 1 ≥ t|A| + (dG1 \A − t) − 1, −2 ≥ t|A| + x∈B x∈B 0 which is contrary to the choice of A and B. Thus, we can get dB (z) ≥ t − 1 for any z ∈ U , since dU (z) ≤ 2. Hence by (11), we have 3t − 3 ≤ t − 1, that is, t = 1, a contradiction. By Proposition 1 and (5), we have b > a and h ≤ t − 1. Thus |A| ≥ 14 by n ≥ 8t + 12 and (6). Let A = {x1 , x2 , . . . xa } and B = {y1 , y2 , . . . , yb }. Then n = a + b. Proposition 2. h ≤ 1. Proof. By (5) and (6), we have −2 ≥ at + (h − t)b = ta + (h − t)(n − a) = (2t − h)a + (h − t)n ≥ (2t − h)(n/2 − 2 − h) + (h − t)n. This implies 4t ≥ (n/2 − 2t)h + h(h + 2) + 2. By n ≥ 8t + 12, we can get h ≤ 1. Proposition 3. (i) If (b − a) ≥ 3, then a = n/2 − 2 − h when n is even and a = (n + 1)/2 − 2 − h when n is odd. (ii) If (b − a) ≤ 2, then a = n/2 − 1 when n is even and a = (n + 1)/2 − 1 when n is odd. Proof. (i) Assume that n is even. Then a and b are either both even or both odd and (b−a) ≥ 4. If a ≥ n/2 − 1 − h, by a + b = n, we can get (b − a) ≤ 2 + 2h. Thus h = 1. By Proposition 1 and (5), we can get −2 ≥ −4t + b contrary to the fact that b > 4t. Thus a = n/2 − 2 − h. For the case in which n is odd, we can similarly get a = (n + 1)/2 − 2 − h. (ii) Since b ≤ a + 2 and a + b = n, from (5) and Proposition 1, we can verify that (ii) is true. From (5) and Propositions 2 and 3, we have 1 ≤ (b − a) ≤ 6 and (b − a) ≤ 4 if and only if h = 0. HAMILTONIAN k-FACTORS IN GRAPHS 221 Proposition 4. θh ≤ (b − a)t − hb − 2. Proof. By Proposition 1 and (5) we have θh ≤ (b − a)t − hb − 2. By Proposition 4, (b − a) ≤ 6 and b ≥ 4t + 7, we can get θ1 ≤ 2t − 9. P Proposition P 5. (i) x∈A dG1 \A (x) ≥ (δ(G) − 2 − h)b − θh + 2. (ii) y∈B dC\A (y) ≥ (b − a)(t + 3) + 3. P Proof. Since G 1 is obtained by deleting P a hamiltonian cycle P from G, we have y∈B dC (y) ≤ P 2|b| − 2. Thus by x∈A dG1 \A (x) = y∈B dG1 \B (y) and y∈B (dG1 \B (y) + dC (y)) + hb + we can easily prove (i). θh ≥ δ(G)b,P P (ii) SinceP y∈B (dG1 (y) + dC (y)) ≥ δ(G)b and y∈B (dG1 (y) + dC\B (y)) ≤ ab + hb + θh , we can get y∈B dC\AP (y) ≥ (δ(G) − a − h)b − θh . Since n = a + b and δ(G) ≥ n/2, by Proposition 4, we have y∈B dC\A (y) ≥ (b − a)b/2 − (b − a)t + 2 ≥ (b − a)(b/2 − t) + 2. Hence by b ≥ 4t + 7, (ii) holds. Proposition 6. (i) dG1 \A (y) + dG1 \A (y 0 ) ≤ 2t − 2h for any distinct y, y 0 ∈ B(h = 0, 1). (ii) dG1 \A (y) ≤ 2t − 2h − 1 for any y ∈ B(h = 0, 1). (iii) There exist at least b − 1 vertices in B such that dG1 \B (y) ≥ δ(G1 ) − t. Proof. (i) Assume that there exist some distinct y, y 0 ∈ B such that dG1 \A (y) + dG1 \A (y 0 ) ≥ 2t + 1 − 2h. Let S = (N (y) ∪ N (y 0 ) \ {y, y 0 }) ∩ B. Then X X dG1 \A (z) ≥ 2t + 1 − 2h + dG1 \A (z) ≥ 4t − 4h. z∈B z∈S By (6) and n = b + a, we have (b − a) ≤ 2(2 + h). If h = 0, then by (5) we can get −2 ≥ t(a − b) + 4t ≥ −4t + 4t = 0, a contradiction. If h = 1, then X X dG1 \A (z) ≥ 2t + 1 − 2h + dG1 \A (z) z∈B + z∈S X dG1 \A (z) ≥ 4t + 1 − 4h − 2 + b − (2t + 1 − 2h + 2) = 2t + b − 6. z∈B\(S∪{y,y 0 }) Also by (5), b ≥ 4t + 7 and (b − a) ≤ 6, we can get a contradiction. (ii) If dG1 \A (y) = 0 for any y ∈ V (B), then (ii) holds. Thus there exist at least two vertices in B each of which has a neighbor in G1 \ A. Hence by (i), we can prove (ii). (iii) If for any y ∈ B, dG1 \A (y) ≤ t, then (iii) holds. If there exists some y ∈ B such that dG1 \A (y) ≥ t + 1, then by (i), dG1 \A (y 0 ) ≤ t − 1 for any y 0 (= / y) ∈ B. Thus dG1 \B (y 0 ) ≥ δ(G1 ) − t + 1. Proposition 7. (i) dG1 \A (x) ≥ t + 1 for any x ∈ A. (ii) dG1 \A (x) + dG1 \A (x0 ) ≥ (2 + h)b − (b − a)t + 2 for any distinct x, x0 ∈ A if (b − a) ≥ 3. (iii) dG1 \A (x) + dG1 \A (x0 ) ≥ b − 2t + 2 for any distinct x, x0 ∈ A if (b − a) ≤ 2. (iv) There exist at least a − 2 + 2h vertices x's in A such that dG1 \A (x) ≥ 2t + 9 + 2h if (b − a) ≥ 3 and there exist at least a − 2 vertices x's in A such that dG1 \A (x) ≥ 2t + 7 if (b − a) ≤ 2, unless n = 8k − 4, b = 4t + 7, θ0 = 2t − 2, dG1 \A (x) ≥ 2t + 6 for any x ∈ A and dG1 \B (y) ≥ a − 3 for any y ∈ B. (v) There exist at least a − 6 vertices x's in A such that when (b − a) ≥ 3 or b ≤ 5t + 8, dG1 \A (x) ≥ b − t; when (b − a) ≤ 2 and b ≥ 5t + 9, dG1 \A (x) ≥ 4t + 7. 222 JOURNAL OF GRAPH THEORY Proof. (i) If there exists some x ∈ A such that dG1 \A (x) ≤ t, then it is easy to check that A0 = A \ {x} and B 0 = B ∪ {x} satisfy (1), contrary to the choice of B. (ii) If there exist distinct x, x0 ∈ A such that dG1 \A (x) + dG1 \A (x0 ) ≤ (2 + h)b − (b − a)t + 1, then we have X dG1 \A (x) ≤ (a − 2)b + (2 + h)b − (b − a)t + 1. (12) x∈A Since (b − a) ≥ 3, by Proposition 3(i), a = n/2 − 2 − h when n is even and a = (n + 1)/2 − 2 − h when n is odd. By Proposition 5, we can get X dG1 \A (x) ≥ ab − θh + 2. (13) x∈A Thus by (12) and (13), we can get θh ≥ (b − a)t − hb + 1, contrary to Proposition 4. (iii) If (b − a) ≤ 2, then a ≥ n/2 − 1 and h = 0 by Proposition 3. When there exist two distinct x, x0 ∈ A such that dG1 \A (x) + dG1 \A (x0 ) ≤ b − 2t + 1, similar to the proof of (ii), we can get θ0 ≥ 2t − 1 = (b − a)t − 1, contrary to Proposition 4. P (iv) Put S = {x : dG1 \A (x) ≤ 2t + 8 + 2h, x ∈ A}. If h = 1 and |S| ≥ 1, then we have + 10). x∈A dG1 \A (x) ≤ (a − 1)b + (2tP As in the proof of (ii), we have x∈A dG1 \A (x) ≥ ab − θ1 + 2. Thus θ1 ≥ b − 2t − 8 ≥ 2t − 1 by b ≥ 4t + 7, contrary to Proposition 4. If h = 0 and |S| ≥ 3, then by 4 ≥ (b − a) ≥ 3 and Propositions 3 and 5, we have X dG1 \A (x) ≥ ab − θ0 + 2. x∈A P On the other hand, we have x∈A dG1 \A (x) ≤ (a − 3)b + 3(2t + 8). Thus θ0 ≥ 3b − 6t − 22 ≥ (b − a)t by b ≥ 4t + 7, contrary to Proposition 4. If (b − a) ≤ 2, set S = {x : dG1 \A (x) ≤ 2t + 6, x ∈ A} and assume that |S| ≥ 3. Then by Proposition 5, we have X dG1 \A (x) ≥ ab − b − θ0 + 2. x∈A P On the other hand, we have x∈A dG1 \A (x) ≤ (a − 3)b + 3(2t + 6). Thus θ0 ≥ 2b − 6t − 16 ≥ 2t − 2 by b ≥ 4t + 7. Thus by Proposition 4, all equalities must hold. Hence, the proof of (iv) is complete. (v) Let S = {x : dG1 \A (x) ≤ b − t − 1, x ∈ A}. When (b − a) ≥ 3 and |S| ≥ 7, then by (13), X dG1 \A (x) ≤ (a − 7)b + 7(b − t − 1), ab − θh + 2 ≤ x∈A which implies θh ≥ 7t + 9 > (b − a)t + 9 by (b − a) ≤ 6, contrary to Proposition 4. When (b − a) ≤ 2 and b ≤ 5t P+ 8, then h = 0. If |S| ≥ 7, by Propositions 3(ii) and 5(i), we obtain ab − b − θ0 + 2 ≤ x∈A dG1 \A (x) ≤ (a − 7)b + 7(b − t − 1), which implies b ≥ 7(t + 1) − (2t − 2) + 2 = 5t + 11 by θ0 ≤ 2t − 2, a contradiction. When (b − a) ≤ 2 and b ≥ 5t + 9, let S = {x : dG1 \A (x) ≤ 4t + 6, x ∈ A}. Using similar arguments to the proof of (iv), we can verify (v). Proposition 8. If there exists a vertex x0 ∈ A such that dG1 \A (x0 ) = t + 1, then (i) h = 0; (ii) when (b − a) ≥ 3, for any x(= / x0 ) ∈ A we have dG1 \A (x) ≥ 3t + 15; HAMILTONIAN k-FACTORS IN GRAPHS 223 (iii) when (b − a) ≤ 2, there exist at least a − 2 vertices x's in A such that dG1 \A (x) ≥ 2t + 10. Proof. (i) By Propositions 3 and 7(iv), we can easily prove (i). (ii) Since (b − a) ≥ 3, by Proposition 7(ii) and b − a ≤ 4, for any x(= / x0 ) ∈ A, dG1 \A (x) ≥ 2b − 4t + 2 − t − 1 ≥ 3t + 15. (iii) Let S = {x : dG1 \A (x) ≤ 2t + 9 and x ∈ A}. If |S| ≥ 3, then by Proposition 5, we have ab − b − θ0 + 2 ≤ (a − 3)b + 2(2t + 9) + t + 1. Thus θ0 ≥ 2b − 5t − 17 ≥ 3t − 3 ≥ (b − a)t by b ≥ 4t + 7, contrary to Proposition 4. Proposition 9. If h = 0, let s0 = |{y : y ∈ B and dG1 \A (y) = 0}|. Then s0 ≥ 9. Proof. By (5) we can get −2 ≥ b − s0 − (b − a)t, which implies Proposition 9 by b ≥ 4t + 7 and b − a ≤ 4. Proposition 10. There exists a hamiltonian cycle C 0 in G such that C 0 contains b − a edges with end vertices in B and n − (b − a) edges with one end vertex in A and the other in B. Proof. Since C is a hamiltonian cycle of G, C must contain at least b − a edges of G with end vertices in B. Choose b − a such edges denoted by E 0 and construct a graph G∗ from G by adding all edges between any pair of nonadjacent vertices in A and deleting all edges with end vertices both in B except for E 0 . Then by Proposition 6, for any y ∈ B, dG∗ (y) ≥ dG1 \B (y) ≥ n/2 − 2 − (2t − 1 − 2h). (14) Case 1. h = 1. By Propositions 3 and 7(iv), for any x ∈ A we have dG∗ (x) ≥ a − 1 + dG1 \A (x) ≥ a − 1 + 2t + 11. Thus by Propositions 3 and 6 and a ≥ n/2 − 2 − h, for any x ∈ A and y ∈ B, we can get dG∗ (x) + dG∗ (y) ≥ a − 1 + 2t + 11 + n/2 − 1 − 2t + 2h > n. Now, by joining all nonadjacent pairs of vertices x, y of G∗ with x ∈ A and y ∈ B, we can get a graph H ∗ . Since E 0 ⊆ E(H ∗ ), H ∗ is hamiltonian. Thus by Theorem 4, G∗ has a hamiltonian cycle C 0 . Because |E 0 | = b − a are all the edges of G∗ in B, C 0 must contain E 0 and n − b + a other edges between A and B. Clearly, E(C 0 ) ⊆ E(G). Case 2. h = 0. If (b − a) ≥ 3, by Proposition 7, there exist two vertices, say x1 , x2 ∈ A, such that for any x ∈ A \ {x1 , x2 } we have dG∗ (x) ≥ a − 1 + dG1 \A (x) ≥ a − 1 + 2t + 9. Thus by a ≥ n/2 − 2, for any x ∈ A \ {x1 , x2 } and y ∈ B, we can get dG∗ (x) + dG∗ (y) ≥ a − 1 + 2t + 9 + n/2 − 1 − 2t > n. By joining all nonadjacent pairs of vertices x, y of G∗ with x ∈ A \ {x1 , x2 } and y ∈ B, we can get a graph G∗1 with dG∗1 (y) ≥ a − 2 for any y ∈ B. By Proposition 3 and (b − a) ≥ 3, for any y ∈ B with dG1 \A (y) = 0, we have yxi ∈ E(G1 ) and consequently, dG1 \A (xi ) ≥ s0 ≥ 9 for i = 1, 2 by Proposition 9. Thus for any y ∈ B, we have dG∗1 (xi ) + dG∗1 (y) ≥ a − 1 + 9 + a − 2 ≥ n. Hence, by joining all nonadjacent pairs xi , y of G∗1 with i = 1, 2 and y ∈ B, we can get a graph ∗ H and H ∗ is hamiltonian. Hence, by Theorem 4, G∗1 is hamiltonian and G∗ is hamiltonian. For the same reason as that in Case 1, Proposition 10 holds. If (b−a) ≤ 2, then a ≥ n/2−1. Since by Proposition 4, θ0 ≤ 2t−2, we have dG1 \A (y) ≤ t−1 P for any y ∈ B (otherwise θ0 ≥ dG1 \A (y) + y0 ∈N (y)∩B dG1 \A (y 0 ) ≥ 2t). Thus dG∗ (y) ≥ dG1 \B (y) ≥ n/2 − 2 − (t − 1). 224 JOURNAL OF GRAPH THEORY By Proposition 7 (iii), there exists a vertex, say x1 ∈ A, such that for any x ∈ A \ {x1 } we have dG∗ (x) ≥ a − 1 + dG1 \A (x) ≥ a − 1 + t + 5. Thus for any x ∈ A \ {x1 } and y ∈ B, we can get dG∗ (x) + dG∗ (y) ≥ a − 1 + t + 5 + n/2 − 1 − t > n. Because dG∗ \A (x1 ) ≥ t+1 ≥ 4 by t ≥ 3, as in the preceding cases, by joining all nonadjacent pairs of vertices x, y of G∗ with x ∈ A \ {x1 } and y ∈ B and then joining all nonadjacent pairs x1 , y, we can get a graph H ∗ which is hamiltonian. Thus by Theorem 5, E 0 ⊆ E(G) and E(G∗ \ A) = E 0 , we can derive that Proposition 10 is true. By Proposition 10, let C 0 be the hamiltonian cycle of G which contains b − a edges with end vertices both in B and n − b + a edges with one end in A and the other one in B. We shall prove that G \ C 0 has a t-factor. Let G2 = G \ C 0 . Then by Proposition 6, there exists a vertex, say y1 ∈ B such that for any y ∈ B \ {y1 } we have dG2 \B (y) ≥ dG1 \B (y) − 2 ≥ δ(G1 ) − t − 2. (15) By Proposition 7, for any x ∈ A, we have dG2 \A (x) ≥ dG1 \A (x) − 2 ≥ t − 1. Since tn is even and a + b = n, we can get that (b − a)t is even. Thus by the choice of C 0 and Proposition 5, there exists at least (b − a)t/2 + 2 edges of C contained in G2 \ A. Now, we distinguish the following two cases. Case 1. dG2 \A (x) ≥ t for any x ∈ A. Choose an edge set E 00 of (b − a)t/2 edges of C in G2 with end vertices both in B. We construct a graph G∗1 from G2 by joining all pairs of nonadjacent vertice of A in G2 and deleting all edges in G2 \ A which are not in E 00 . Since by Proposition 7 (v), there exist six vertices, say xi (a − 5 ≤ i ≤ a), in A, such that for any xj ∈ A, 1 ≤ j ≤ a − 6, when (b − a) ≥ 3 or b ≤ 5t + 8, we have dG∗1 (xj ) ≥ a − 1 + dG1 \A (xj ) − 2 ≥ a − 1 + b − t − 2, (16) or when (b − a) ≤ 2 and b ≥ 5t + 9, we have dG∗1 (xj ) ≥ a − 1 + dG1 \A (xj ) − 2 ≥ a − 1 + 4t + 7 − 2. (160 ) Case 1.1. n ≥ 8k − 3. Then by Proposition 7 (iv), there exist two distinct vertices, say xa−1 , xa ∈ A, such that for any xi ∈ A and 1 ≤ i ≤ a − 2, when (b − a) ≥ 3, we have dG∗1 \A (xi ) ≥ dG1 \A (xi ) − 2 ≥ 2t + 7 + 2h, (17) or when (b − a) ≤ 2, we have dG∗1 \A (xi ) ≥ dG1 \A (xi ) − 2 ≥ 2t + 5. (170 ) Notice that a ≥ n/2 − 3 and when (b − a) ≤ 2, a ≥ n/2 − 1 by Proposition 3. Thus for any 1 ≤ i ≤ a − 6 and 2 ≤ j ≤ b, by (15) we have dG∗1 (xi ) + dG∗1 (yj ) ≥ a − 1 + b − t − 2 + n/2 − 2 − t − 2 ≥ n + 2t − 1, or dG∗1 (xi ) + dG∗1 (yj ) ≥ a − 1 + 4t + 7 − 2 + n/2 − 2 − t − 2 ≥ n + 2t − 1. HAMILTONIAN k-FACTORS IN GRAPHS 225 We construct a graph F ∗ from G∗1 by joining all nonadjacent pairs of vertices xi , yj in G∗1 with 1 ≤ i ≤ a − 6 and 2 ≤ j ≤ b. Then by Proposition 6, for any 1 ≤ i ≤ a − 6 we have dF ∗ (xi ) + dF ∗ (y1 ) ≥ a − 1 + b − 1 + n/2 − 2 − 2t − 2 > n + 2t. Thus by joining all nonadjacent pairs of vertices xi , y1 with 1 ≤ i ≤ a − 6, we get a graph F1∗ . If (b − a) ≥ 3 by (17) for any a − 5 ≤ i ≤ a − 2 and y ∈ B, we have dF1∗ (xi ) + dF1∗ (y) ≥ a − 1 + 2t + 7 + 2h + a − 6 ≥ n + 2t − 4. If (b − a) ≤ 2, then by (170 ) for any a − 5 ≤ i ≤ a − 2 and y ∈ B, we also have dF1∗ (xi ) + dF1∗ (y) ≥ a − 1 + 2t + 5 + a − 6 ≥ n + 2t − 4. Hence we finally obtain a graph H ∗ from F1∗ by joining all nonadjacent pairs xi , y in F1∗ for any a − 5 ≤ i ≤ a − 2 and y ∈ B. Case 1.2. n = 8k − 4. If there exist two distinct vertices, say xa−1 , xa ∈ A, such that for any xi ∈ A and 1 ≤ i ≤ a−2 either (17) or (170 ) holds, we can construct a graph H ∗ as that in Case 1.1. Otherwise, by Proposition 7(iv), b − a = 2 and for any x ∈ A and y ∈ B we have dG∗1 (x) + dG∗1 (y) ≥ a − 1 + 2t + 6 − 2 + a − 3 − 2 ≥ n + 2t − 4. Thus we can also construct a graph H ∗ as that in Case 1.1. Now, by the constructure of H ∗ and Theorem 5, we can get that H ∗ has a t-factor implies that ∗ G1 has a t-factor. Thus we need only to show that H ∗ has a t-factor. In fact, since (b − a) ≤ 6 and b ≥ 4t + 7, by Proposition 7, we obtain dG2 \A (xa−1 ) + dG2 \A (xa ) ≥ dG1 \A (xa−1 ) + dG1 \A (xa ) − 4 > 10. Thus, we may assume, without loss of generality, that dG2 \A (xa ) ≥ 6. If t = 3, by dG2 \A (xa−1 ) ≥ t, we can choose three distinct vertices {y1a−1 , y2a−1 , y3a−1 } ⊆ N (xa−1 )∩B and three distinct vertices {y1a , y2a , y3a } ⊆ (N (xa ) \ {y1a−1 , y2a−1 , y3a−1 }) ∩ B and set E ∗ = {xi yji : i = a − 1, a and j = 1, 2, 3}. If t ≥ 4, we choose 2t distinct vertices yim ∈ N (xm ) ∩ B(1 ≤ i ≤ t and m = a − 1, a) and set E ∗ = {xm yim : 1 ≤ i ≤ t and m = a − 1, a}. Let sj = |{z : zyj ∈ E 00 ∪ E ∗ }|, 1 ≤ j ≤ b and without loss of generality, assume that sj ≤ sj+1 (1 ≤ j ≤ b − 1). Then by the choice of E 00 ∪ E ∗ , 0 ≤ sj ≤ t for any 1 ≤ j ≤ b Pb and j=1 sj = (b − a + 2)t. Set pi = t (1 ≤ i ≤ a − 2) and qj = t − sj (1 ≤ j ≤ b). Then qj ≥ qj+1 ≥ 0 for 1 ≤ j ≤ b − 1. By (a − 2 − t)r > 0, for any 1 ≤ r ≤ t we have a−2 X min{pi , r} = (a − 2)r > rt ≥ i=1 r X qj , j=1 and for any t + 1 ≤ r ≤ b we have a−2 X i=1 min{pi , r} = t(a − 2) = (b − (b − a + 2))t = b X j=1 qj ≥ r X qj . j=1 Since for any x ∈ A \ {xa−1 , xa } and y ∈ B, xy is an edge of H ∗ , we can get by Theorem 6, there exists a subgraph F of H ∗ such that dF (xi ) = |NF (xi ) ∩ B| = t for any 1 ≤ i ≤ a − 2 and dF (yj ) = |NF (yj ) ∩ (A \ {xa−1 , xa })| = qj for any 1 ≤ j ≤ b. Thus by adding the edge set E 00 ∪ E ∗ to F , we can get a t-factor of H ∗ . 226 JOURNAL OF GRAPH THEORY Hence G∗1 has a t-factor F 0 . Since (b − a)t/2 edges of E 00 are all the edges which are in B, F 0 must contain E 00 . Thus F 0 can not contain an edge with both ends in A. This shows that F 0 is a t-factor of G2 , contrary to the assumption. Case 2. There exists a vertex, say xa ∈ A, such that dG2 \A (xa ) = t − 1. a } ∈ N (xa ) ∩ B. Since d(xa ) ≥ n/2, N (xa ) ∩ A = / ∅. Without loss of Let {y1a , . . . , yt−1 generality, assume that x1 xa ∈ E(G). Choose an edge set E 00 which contains (b − a)t/2 + 1 edges of C in G2 with end vertices both in B and the edge set {xa yja : 1 ≤ j ≤ t − 1}. We construct a graph G∗1 from G2 by joining all pairs of nonadjacent vertice of A \ {xa } in G2 and deleting all edges in G2 \A which are not in E 00 and deleting all edges xa xi for 2 ≤ i ≤ a−1. Since by Proposition 8, h = 0 and there exist two distinct vertices, say xa−1 , xa ∈ A such that for any xi ∈ A and 1 ≤ i ≤ a − 2, we have dG∗1 \A (xi ) ≥ dG1 \A (xi ) − 2 ≥ 2t + 8. (18) By Proposition 7, there exist six vertices, say xi (a − 5 ≤ i ≤ a), in A, such that for any xj ∈ A, 1 ≤ j ≤ a − 6, when (b − a) ≥ 3 or b ≤ 5t + 8, we have dG∗1 (xj ) ≥ a − 2 + dG1 \A (xj ) − 2 ≥ a − 2 + b − t − 2, (19) or when (b − a) ≤ 2 and b ≥ 5t + 9, we have dG∗1 (xj ) ≥ a − 2 + dG1 \A (xj ) − 2 ≥ a − 2 + 4t + 7 − 2. (190 ) Thus by (15), for any 1 ≤ i ≤ a − 6 and 2 ≤ j ≤ b, we have dG∗1 (xi ) + dG∗1 (yj ) ≥ a − 2 + b − t − 2 + n/2 − 2 − t − 2 ≥ n + 2t − 2, or dG∗1 (xi ) + dG∗1 (yj ) ≥ a − 2 + 4t + 7 − 2 + n/2 − 2 − t − 2 ≥ n + 2t − 2. We construct a graph F ∗ from G∗1 by joining all nonadjacent pairs of vertices xi , yj in G∗1 with 1 ≤ i ≤ a − 6 and 2 ≤ j ≤ b. Then by Proposition 6, for any 1 ≤ i ≤ a − 6 we have dF ∗ (xi ) + dF ∗ (y1 ) ≥ a − 2 + b − 1 + n/2 − 2 − 2t − 2 ≥ n + 2t − 1. Thus by joining all nonadjacent pairs of vertices xi , y1 with 1 ≤ i ≤ a − 5, we get a graph F1∗ . Since (b − a) ≤ 4, by (18) for any a − 5 ≤ i ≤ a − 2 and y ∈ B, we have dF1∗ (xi ) + dF1∗ (y) ≥ a − 2 + 2t + 8 + a − 6 ≥ n + 2t − 4. Hence we finally obtain a graph H ∗ from F1∗ by joining all nonadjacent pairs xi , y in F1∗ for any a − 5 ≤ i ≤ a − 2 and y ∈ B. For the same reason as that in Case 1, by Theorem 5 we need only to show that H ∗ has a t-factor. If t = 3, dG2 \A (xa−1 ) ≥ t + 6 by Proposition 7. Thus we can choose three distinct vertices a−1 a−1 a−1 {y1 , y2 , y3 } ⊆ (N (xa−1 ) \ N (xa )) ∩ B and set E ∗ = {xa−1 yja−1 : j = 1, 2, 3}. If t ≥ 4, we choose t distinct vertices yia−1 ∈ N (xa−1 ) ∩ B(1 ≤ i ≤ t) and set E ∗ = {xa−1 yia−1 : 1 ≤ i ≤ t}. Let sj = |{z : zyj ∈ E 00 ∪ E ∗ }|, 1 ≤ j ≤ b and without loss of generality, assume that sj ≤ sj+1 (1 ≤ j ≤ b − 1). Then by the choice of E 00 ∪ E ∗ , 0 ≤ sj ≤ t for any 1 ≤ j ≤ b Pb and j=1 sj = 2((b − a)t/2 + 1) + t − 1 + t = (b − a + 2)t + 1. Set p1 = t − 1 and pi = t(2 ≤ i ≤ a − 2) and qj = t − sj (1 ≤ j ≤ b). Then qj ≥ qj+1 ≥ 0 for 1 ≤ j ≤ b − 1. HAMILTONIAN k-FACTORS IN GRAPHS 227 By (a − 2 − t)r > 0, for any 1 ≤ r ≤ t − 1 we have a−2 X i=1 min{pi , r} = (a − 2)r > rt ≥ r X qj , j=1 and for any t ≤ r ≤ b we have a−2 X min{pi , r} = t(a − 2) − 1 = (b − (b − a + 2))t − 1 = i=1 b X j=1 qj ≥ r X qj . j=1 Thus for the same reason as that in Case 1, by Theorem 6, there exists a subgraph F of H ∗ such that dF (x1 ) = |NF (x1 ) ∩ B| = t − 1, dF (xi ) = |NF (xi ) ∩ B| = t for any 2 ≤ i ≤ a − 2 and dF (yj ) = |NF (yj ) ∩ (A \ {xa−1 , xa })| = qj for any 1 ≤ j ≤ b. Thus by adding the edge set E 00 ∪ E ∗ ∪ {x1 xa } to F , we can get a t-factor of H ∗ . Hence G∗1 has a t-factor F 0 . Since G∗1 contains only (b − a)t/2 + 1 edges which are in B and dG∗1 (xa ) = t, F 0 must contain E 00 ∪ {x1 xa }. Thus F 0 can not contain an edge with both ends in A \ {xa }. This shows that F 0 is a t-factor of G2 , contrary to the assumption. Therefore, Theorem 2 is true. ACKNOWLEDGMENT The authors are grateful to the referee for the helpful suggestions. References [1] J. A. Bondy and Chvátal, A method in graph theory. Discrete Math. 15 (1976), 111–135. [2] J. A. Bondy and Murty, Graph theory with applications, Macmillean, London, and Elsvevier, New York (1976). [3] G. A. Dirac, Some theorems on abstract graphs. Proc. London Math. Soc. 2 (1952), 69–81. [4] P. Katerinis and D. R. Woodall, Binding numbers of graphs and the existence of k-factors. Quart. J. Math. 38 (1987), 221–228. [5] H. Li and Y. Zhu, Edge-disjoint hamilton cycles in graphs. Ann. N Y Acad. Sci. 576 (1989), 311–322. [6] W. T. Tutte, The factors of graphs. Canad. J. Math. 4 (1952), 314–328.

1/--страниц