A [k, k + 1]-Factor Containing A Given Hamiltonian Cycle

Cai Mao-cheng ^{∗} Yanjun Li Institute of Systems Science

Chinese Academy of Sciences, Beijing 100080, P.R. China

          caimc@bamboo.iss.ac.cn    cogt@bamboo.iss.ac.cn

Mikio Kano Department of Computer and Information Sciences Ibaraki University, Hitachi 316, Japan

                      kano@cis.ibaraki.ac.jp

Abstract

We prove the following best possible result. Let k ≥ 2 be an integer and G be a graph of order n with minimum degree at least k. Assume n ≥ 8k − 16 for even n and n ≥ 6k −13 for odd n. If the degree sum of each pair of nonadjacent vertices of G is at least n, then for any given Hamiltonian cycle C of G, G has a [k, k + 1]-factor containing C.

Submitted: December 15, 1997; Accepted: November 27, 1998.

MR Subject Number: 05C75 Keywords: [k, k + 1]-factor, Hamiltonian cycle, degree condition

1 Introduction

All graphs under consideration are undirected, finite and simple. A graph G consists of a non-empty set V (G) of vertices and a set E(G) of edges. For two vertices x and y of G, let xy and yx denote an edge joining x to y. Let X be a subset of V (G).

∗Research supported partially by the exchange program between Chinese Academy of Sciences and Japan Society for Promotion of Sciences and by National Natural Science Foundation of China.

We write G[X] for the subgraph of G induced by X, and define \overline{X} := V (G) \ X. The subset X is said to be independent if no two vertices of X are adjacent in G. Sometimes x is used for a singleton {x}. For a vertex x of G, we denote by d_{G}(x) the degree of x in G, that is, the number of edges of G incident with x. We denote by δ(G) the minimum degree of G. For integers a and b, 0 ≤ a ≤ b, an [a, b]-factor of G is defined to be a spanning subgraph F of G such that

a ≤ d_{F} (x) ≤ b for all x ∈ V (G),

and an [a, a]-factor is abbreviated to an a-factor. A subset M of E(G) is called a matching if no two edges of M are adjacent in G. For two graphs H and K, the union H ∪ K is the graph with vertex set V (H) ∪ V (K) and edge set E(H) ∪ E(K), and the join H + K is the graph with vertex set V (H) ∪ V (K) and edge set E(H) ∪ E(K) ∪ {xy | x ∈ V (H) and y ∈ V (K)}. Other notation and definitions not defined here can be found in [1].

We first mention some known results concerning our theorem.

Theorem A ([9]) Let G be a graph of order n ≥ 3. If the degree sum of each pair of nonadjacent vertices is at least n, then G has a Hamilton cycle.

Theorem B ([3]) Let k be a positive integer and G be a graph of order n with n ≥ 4k − 5, kn even, and δ(G) ≥ k. If the degree sum of each pair of nonadjacent vertices is at least n, then G has a k-factor.

Combining the above two theorems, we can say that if a graph G satisfies the conditions in Theorem B, then G has a Hamilton cycle C together with a connected [k, k + 2]-factor containing C, which is the union of C and a k-factor of G [4].

Theorem C ([8]) Let k ≥ 3 be an integer and G be a connected graph of order n with n ≥ 4k − 3, kn even, and δ(G) ≥ k. If for each pair (x, y) of nonadjacent vertices of V (G),

max\{d_{G}(x), d_{G}(y)\} ≥ \frac{n}{2} ,

then G has a k-factor.

Theorem D ([2]) Let k ≥ 3 be an odd integer and G be a connected graph of odd order n with n ≥ 4k − 3, and δ(G) ≥ k. If for each pair (x, y) of nonadjacent vertices of G,

max\{d_{G}(x), d_{G}(y)\} ≥ \frac{n}{2} ,

then G has a connected [k, k + 1]-factor.

Theorem E ([5]) Let G be a connected graph of order n, let f and g be two positive integer functions defined on V (G) which satisfy 2 ≤ f(v) ≤ g(v) for each vertex v ∈ V (G). Let G have an [f, g]-factor F and put μ = min{f(v) : v ∈ V (G)}. Suppose that among any three independent vertices of G there are (at least) two vertices with degree sum at least n − μ. Then G has a matching M such that M and F are edgedisjoint and M + F is a connected [f, g + 1]-factor of G.

The purpose of this paper is to extend “connected [k, k +1]-factor” in some of the above theorems to “[k, k + 1]-factor containing a given Hamiltonian cycle”, which is obviously a 2-connected [k, k + 1]-factor.

Our main result is the following

Theorem 1 Let k ≥ 2 be an integer and G be a graph of order n ≥ 3 with δ(G) ≥ k. Assume n ≥ 8k − 16 for even n and n ≥ 6k − 13 for odd n. If for each pair (x, y) of nonadjacent vertices of G,

d_{G}(x) + d_{G}(y) ≥ n,  (1)

then for any given Hamiltonian cycle C, G has a [k, k + 1]-factor containing C.

Now we conclude this section with a new result concerning our theorem.

Theorem F [11] Let k ≥ 2 be an integer and G be a connected graph of order n such that n ≥ 8k − 4, kn is even and δ(G) ≥ n/2. Then G has a k-factor containing a Hamiltonian cycle.

For a graph G of order n, the condition δ(G) ≥ n/2 does not guarantee the existence of a k-factor which contains a given Hamiltonian cycle of G. Let n ≥ 5 and k ≥ 3 be integers, and set

m = \{ \begin{matrix}\frac{n}{2} + 2 & for even n, \\ \frac{n+3}{2} & for odd n. \end{matrix}

Let C_{m} = (v_{1}v_{2} … v_{m}) be a cycle of order m and P_{n−m} = (v_{m+1}v_{m+2} … v_{n}) a path of order n − m. Then the join G := C_{m} + P_{n−m} has no k-factor containing the Hamiltonian cycle (v_{1}v_{2} … v_{n}) but satisfies δ(G) ≥ n/2.

2 Proof

Our proof depends on the following theorem, which is a special case of Lovász’s (g, f)-factor theorem [7]([10]).

Theorem 2 Let G be a graph and a and b be integers such that 1 ≤ a < b. Then G has an [a, b]-factor if and only if

γ(S, T) := b|S| − a|T | + ∑_{x∈T} d_{G−S}(x) ≥ 0

for all disjoint subsets S, T ⊆ V (G).

Proof of Theorem 1 We may assume k ≥ 3 since G has C for k = 2. Let

H := G − E(C), U := \{x ∈ V (G) | d_{G}(x) ≥ \frac{n}{2}\}, W := V (G) \ U, ρ := k − 2.

Then V (H) = V (G), ρ ≥ 1,

d_{H}(x) = d_{G}(x) − 2 ≥ ρ for all x ∈ V (H),

n ≥ 8ρ for even n and n ≥ 6ρ − 1 for odd n. Moreover the induced subgraph G[W] is a complete graph since d_{G}(x) + d_{G}(y) < n for any two vertices x and y of W.

Obviously, G has a required factor if and only if H has a [ρ, ρ+1]-factor. Suppose, to the contrary, that H has no such factor. Then, by Theorem 2, there exist disjoint subsets S and T of V (H) such that

γ(S, T) = (ρ + 1)s − ρt + ∑_{x∈T} d_{H−S}(x) < 0.  (2)

where t = |T | and s = |S|.

If d_{H−S}(v) ≥ ρ for some v ∈ T, then γ(S, T) ≥ γ(S, T \ {v}), and thus (2) is still holds for S and T \ {v}. Thus we may assume that

d_{H−S}(x) ≤ ρ − 1 for all x ∈ T.  (3)

If S = ∅, then γ(∅, T) = −ρt + ∑_{x∈T} d_{H}(x) ≥ 0 as d_{H}(x) ≥ ρ for all x ∈ V (H). Thus

s ≥ 1.  (4)

If t ≤ ρ + 1, then we have

γ(S, T) ≥ (ρ + 1)s − ρt + ∑_{x∈T}(d_{H}(x) − s)
≥ (ρ + 1)s − ρt + t(ρ − s)
= s(ρ + 1 − t) ≥ 0.

This contradicts (2). Hence

t ≥ ρ + 2.  (5)

We now prove the next Claim:

Claim 1. s ≤ \frac{n}{2} − 3 if n is even, and s ≤ \frac{n−5}{2} if n is odd.

Assume that n is even and s ≥ (n/2) − 2. Let q := s − (n/2) + 2 ≥ 0 and r := n − s − t ≥ 0. Then it follows from ρ ≥ 1 and n ≥ 8ρ that

γ(S, T) = (ρ + 1)q + ρ(r + q) + ∑_{x∈T} d_{H−S}(x) + \frac{n}{2} − 4ρ − 2
≥ 2q + r + q + ∑_{x∈T} d_{H−S}(x) − 2.

Hence we may assume q = 0 and r ≤ 1 since otherwise γ(S, T) ≥ 0. If r = 1 and ∑_{x∈T} d_{H−S}(x) ≥ 1, then γ(S, T) ≥ 0. If r = 0 and ∑_{x∈T} d_{H−S}(x) ≥ 1, then V (H) = S ∪ T and

∑_{x∈T} d_{H−S}(x) = ∑_{x∈T} d_{H[T]}(x) = 2|E(H[T])| ≡ 0 (mod 2),

and so γ(S, T) ≥ 0. Therefore it suffices to show that ∑_{x∈T} d_{H−S}(x) ≥ 1 under the assumption that q = 0 and 0 ≤ r ≤ 1.

Suppose that ∑_{x∈T} d_{H−S}(x) = 0, q = 0 and 0 ≤ r ≤ 1. Let \overline{S} := V (G) \ S ⊇ T, X := \{x ∈ \overline{S} | d_{G}(x) ≥ n/2\} and Y := \overline{S} \ X. Then a complete graph G[Y] is contained in C, and it follows from s = (n/2) − 2 that for each vertex x ∈ X, there exist two edges of C which join x to two vertices in \overline{S}. Hence we have

|X|+|Y |−1 = |\overline{S}|−1 ≥ |E(G[\overline{S}])∩E(C)| ≥ |X|+1+|E(G[Y])| = |X|+1+\frac{|Y |(|Y | − 1)}{2},

which implies |Y | ≥ 2 + |Y |(|Y | − 1)/2. Now we get a contradiction, because it is obvious that there is no nonnegative integral solution of |Y | to this quadratic inequality. Therefore Claim 1 holds for even n.

We next assume that n is odd and s ≥ (n − 3)/2. Let q := s − (n − 3)/2 ≥ 0 and r := n − s − t ≥ 0. Then it follows from ρ ≥ 1 and n ≥ 6ρ − 1 that

γ(S, T) = (ρ + 1)q + ρ(r + q) + ∑_{x∈T} d_{H−S}(x) + \frac{n}{2} − 3ρ − \frac{3}{2}
≥ 2q + r + q + ∑_{x∈T} d_{H−S}(x) − 2.

Hence, by the same argument as above, we may assume that q = 0, 0 ≤ r ≤ 1 and ∑_{x∈T} d_{H−S}(x) = 0. Let X := \{x ∈ \overline{S} | d_{G}(x) ≥ (n + 1)/2\} and Y := \overline{S} \ X. Then we similarly obtain |Y | ≥ 2 + |Y |(|Y | − 1)/2, and derive a contradiction. Consequently Claim 1 also holds for odd n.

Claim 2. T ∩ U ≠ ∅.

Indeed, assume T ⊆ W. Then G[T] is a complete graph and |E(G[T])| = t(t−1)/2. Since C is a Hamiltonian cycle, |E(G[T]) ∩ E(C)| ≤ t − 1. Hence

∑_{x∈T} d_{H−S}(x) ≥ 2|E(G[T]) \ E(C)| ≥ t(t − 1) − 2(t − 1) = (t − 1)(t − 2).

Thus

γ(S, T) ≥ (ρ + 1)s − ρt + (t − 1)(t − 2)
≥ (ρ + 1)s − ρt + (t − 1)ρ  (by (5))
= (ρ + 1)s − ρ > 0.  (by (4))

This contradicts (2).

Claim 3. T ∩ W ≠ ∅.

Suppose T ⊆ U and n is even. Then for every x ∈ T, we have by (3)

\frac{n}{2} ≤ d_{G}(x) ≤ d_{H−S}(x) + s + 2 ≤ ρ + s + 1,

which implies d_{H−S}(x) ≥ (n/2) − s − 2 and ρ + s + 2 − n/2 ≥ 1. Hence

γ(S, T) ≥ (ρ + 1)s − ρt + t(\frac{n}{2} − s − 2)
= (ρ + 1)s − t(ρ + s + 2 − \frac{n}{2})
≥ (ρ + 1)s − (n − s)(ρ + s + 2 − \frac{n}{2})
= (ρ + 1)s + (\frac{n}{2} − s − 3 + \frac{n}{2} + 3)(\frac{n}{2} − s − 3 − 2ρ + ρ + 1)
= (\frac{n}{2} − s − 3)^{2} + (\frac{n}{2} − s − 3)(\frac{n}{2} + 3 − 2ρ) + n − 6ρ
≥ 0.  (by n ≥ 8ρ and Claim 1)

This contradicts (2).

Next assume T ⊆ U and n is odd. Then for every x ∈ T, we have

\frac{n + 1}{2} ≤ d_{G}(x) ≤ d_{H−S}(x) + s + 2 ≤ ρ + s + 1,

which implies d_{H−S}(x) ≥ (n/2) − s − (3/2) and ρ + s + (3/2) − (n/2) ≥ 1. Hence

γ(S, T) ≥ (ρ + 1)s − ρt + t(\frac{n}{2} − s − \frac{3}{2})
= (ρ + 1)s − t(ρ + s + \frac{3}{2} − \frac{n}{2})
≥ (ρ + 1)s − (n − s)(ρ + s + \frac{3}{2} − \frac{n}{2})
= (\frac{n}{2} − s − \frac{5}{2})^{2} + (\frac{n}{2} − s − \frac{5}{2})(\frac{n}{2} + \frac{5}{2} − 2ρ) + n − 5ρ
≥ 0.  (by n ≥ 6ρ − 1 and Claim 1)

This contradicts (2). Therefore Claim 2 is proved.

Now put

T_{1} := T ∩ U, T_{2} := T ∩ W, t_{1} = |T_{1}|, t_{2} := |T_{2}|.

By Claims 2 and 3, we have t_{1} ≥ 1 and t_{2} ≥ 1. It is clear that d_{H−S}(x) ≥ d_{G}(x)−s−2 for all x ∈ T, in particular, for every y ∈ T_{1},

d_{H−S}(y) ≥ \{ \begin{matrix}\frac{n}{2} − s − 2 & if n is even \\ \frac{n}{2} − s − \frac{3}{2} & if n is odd. \end{matrix}  (6)

It follows from (3) that

\frac{n}{2} − ρ − s − 2 ≤ −1 if n is even, and \frac{n}{2} − ρ − s − \frac{3}{2} ≤ −1 if n is odd. (7)

By Claim 1 and by the above inequalities, we have

ρ ≥ 2.  (8)

For every x ∈ T_{2}, we have d_{H−S}(x) ≥ t_{2} − 3 by the fact that G[W] is a complete graph, and obtain the following inequality from (3).

t_{2} ≤ ρ + 2.  (9)

In order to complete the proof, we consider two cases. Assume first n is even. By making use of n ≥ 8ρ, (6), (7), (8), (9) and Claim 1, we have

γ(S, T) ≥ (ρ + 1)s − ρ(t_{1} + t_{2}) + t_{1}(\frac{n}{2} − s − 2)
= (ρ + 1)s − ρt_{2} + t_{1}(\frac{n}{2} − s − 2 − ρ)
≥ (ρ + 1)s − ρt_{2} + (n − s − t_{2})(\frac{n}{2} − ρ − s − 2)
= (\frac{n}{2} − s − 3)^{2} + (\frac{n}{2} − s − 3)(\frac{n}{2} + 3 − 2ρ − t_{2})
+ n − 6ρ − t_{2}
≥ 2ρ − t_{2} ≥ ρ + 2 − t_{2} ≥ 0.

This contradicts (2).

We next assume n is odd. Let r := n − s − t. It is easy to see that

∑_{x∈T_{2}} d_{H−S}(x) ≥ 2|E(G[T_{2}]) \ E(C)| ≥ t_{2}(t_{2} − 1) − 2(t_{2} − 1) = (t_{2} − 1)(t_{2} − 2). (10)

By using n ≥ 6ρ − 1, (6), (7), (8) (9) and (10), we have

γ(S, T) ≥ (ρ + 1)s − ρ(t_{1} + t_{2}) + t_{1}(\frac{n}{2} − s − \frac{3}{2}) + (t_{2} − 1)(t_{2} − 2)
= (ρ + 1)s + t_{1}(\frac{n}{2} − ρ − s − \frac{3}{2}) − ρt_{2} + (t_{2} − 1)(t_{2} − 2)
≥ (ρ + 1)s + (n − s − t_{2} − r)(\frac{n}{2} − ρ − s − \frac{3}{2}) − ρt_{2} + (t_{2} − 1)(t_{2} − 2)
= (\frac{n}{2} − s − \frac{5}{2})^{2} + (\frac{n}{2} − s − \frac{5}{2})(\frac{n}{2} + \frac{5}{2} − t_{2} − 2ρ)

+ n − 5ρ + (t_{2} − 1)(t_{2} − 2) − t_{2} + r(ρ + s + \frac{3}{2} − \frac{n}{2})

= (\frac{n}{2} − s − \frac{5}{2})^{2} + ρ − 1 + (t_{2} − 1)(t_{2} − 2) − t_{2} + r.

Since (t_{2} − 1)(t_{2} − 2) − t_{2} ≥ −2 with equality only when t_{2} = 2, we have ρ − 1 + (t_{2} − 1)(t_{2} − 2) − t_{2} + r ≥ ρ − 1 − 2 + r = ρ − 2 + r − 1 ≥ r − 1 and thus γ(S, T) ≥ 0 unless s = (n − 5)/2, t_{2} = 2 r = 0, ρ = 2 and (10) holds with equality. Since t_{2} = 2 and (10) holds with equality,

|E(G[T_{2}])| = |E(G[T_{2}]) ∩ E(C)| = 1.

Since s = (n + 1)/2 − 3 and ρ = 2, it follows from (3) and (6) that

d_{H−S}(x) = 1 and d_{G}(x) = \frac{n + 1}{2} for all x ∈ T_{1}.

This implies that all the edges of C incident with vertices in T_{1} are contained in E(G[T]) \ E(G[T_{2}]), and thus the number of such edges is at least t_{1} + 1. Therefore |E(G[T]) ∩ C| ≥ t_{1} + 1 + 1 = t, contradicting the fact that C is a Hamiltonian cycle of G. Consequently the theorem is proved.

Remark. The condition that n ≥ 8k − 16 for even n and n ≥ 6k − 13 for odd n in Theorem 1 are best possible. To see this, either let n be an even integer such that 2k ≤ n < 8k − 16 and put m = (n/2) + 2, or let n be an odd integer such that 2k − 1 ≤ n < 6k − 13 and put m = (n + 3)/2. Let C_{m} = (v_{1}v_{2} … v_{m}) be a cycle of order m and P_{n−m} = (v_{m+1}v_{m+2} … v_{n}) a path of order n − m. Then the join G := C_{m} + P_{n−m} has no [k, k + 1]-factor containing Hamiltonian cycle (v_{1}v_{2} … v_{n}) but satisfies δ(G) ≥ k and d_{G}(x) + d_{G}(y) ≥ n for all nonadjacent vertices x and y of G.

We explain why G has no such factor when n is even. By setting S = {v_{m+1}, …, v_{n}} and T = {v_{1}, …, v_{m}} in (2), we obtain γ(S, T) = (k−1)(n/2−2)−(k−2)(n/2+2)+2 < 0, which implies G has no such factor.

References

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, American Elsevier, New York (1976).

[2] Cai Mao-cheng, Connected [k, k + 1]-factors of graphs, submitted.

[3] T. Iida and T. Nishimura, An Ore-type condition for the existence of k-factors in graphs, Graphs and Combinat. 7 (1991) 353-361.

[4] M. Kano, Some current results and problems on factors of graphs, Proc. 3rd China-USA Internat. Conf. on Graph Theory and Its Application, World Sci. Publishing, River Edge, NJ, (1994) 93-98.

[5] Yanjun Li and Cai Mao-cheng, A degree condition for the existence of connected factors, Australasian Journal of Combinatorics 14 (1995) 77-83.

[6] Yanjun Li and Cai Mao-cheng, A degree condition for graphs to have [a, b]- factors, J. Graph Theory 27 (1998) 1-6.

[7] L. Lovász, Subgraphs with prescribed valencies, J. Combin. Theory 8 (1970) 391-416.

[8] T. Nishimura, A degree condition for the existence of k-factors, J. Graph Theory 16 (1992) 141-151.

[9] O. Ore, A note on Hamilton circuit, Amer. Math. Soc. 4 (1947) 107-111.

[10] W.T. Tutte, Graph factors, Combinatorica 1 (1981) 79-97.

[11] B. Wei and Y. Zhu, Hamiltonian k-factors in graphs, submitted.