 Забыли?

?

# 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 .
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 .
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 . 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 . 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 . 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 . 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 , 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

J. A. Bondy and Chvátal, A method in graph theory. Discrete Math. 15 (1976), 111–135.

J. A. Bondy and Murty, Graph theory with applications, Macmillean, London, and Elsvevier, New
York (1976).

G. A. Dirac, Some theorems on abstract graphs. Proc. London Math. Soc. 2 (1952), 69–81.

P. Katerinis and D. R. Woodall, Binding numbers of graphs and the existence of k-factors. Quart. J.
Math. 38 (1987), 221–228.

H. Li and Y. Zhu, Edge-disjoint hamilton cycles in graphs. Ann. N Y Acad. Sci. 576 (1989), 311–322.

W. T. Tutte, The factors of graphs. Canad. J. Math. 4 (1952), 314–328.
```
###### Документ
Категория
Без категории
Просмотров
3
Размер файла
128 Кб
Теги
304
1/--страниц
Пожаловаться на содержимое документа