close

Вход

Забыли?

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

?

304

код для вставкиСкачать
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.
Документ
Категория
Без категории
Просмотров
3
Размер файла
128 Кб
Теги
304
1/--страниц
Пожаловаться на содержимое документа