A sufficient condition for the existence of a k-factor excluding a given r-factor

For motivation and background to this work see [1]. In this paper, we consider only finite and simple graphs. Let G = (V (G), E(G)) be a graph, where V (G) denotes its vertex set and E(G) denotes its edge set. A graph is Hamiltonian if it admits a Hamiltonian cycle. For each x ∊ V (G), the neighborhood N_G(x) of x is the set of vertices of G adjacent to x, and the degree d_G(x) of x is |N_G(x)|. For S ⊆ V (G), we write N_G(S) = ∪_x∊SN_G(x). G[S] denotes the subgraph of G induced by S, and G − S = G[V (G) \ S]. A vertex subset S of G is called independent if G[S] has no edges. The symbol δ(G) denotes the minimum degree of G. The binding number of G is defined by bind(G)=min {|NG(S)||S|:∅≠S⊂V(G),NG(S)≠V(G)}$\begin{array}{} \left( G \right) = {\rm{min }}\left\{ {\frac{{\left| {{N_G}\left( S \right)} \right|}}{{\left| S \right|}}:\emptyset \ne S \subset V\left( G \right),{N_G}\left( S \right) \ne V\left( G \right)} \right\} \end{array}$. A spanning subgraph F of G with d_F(x) = k for each x ∊ V (G) is called a k-factor of G.

Many authors studied graph factors [1–10]. Anderson [11] gave a binding number condition for graphs to have 1-factors. Woodall [12] showed a binding number condition for a graph to have a Hamiltonian cycle (or a 2-factor). Katerinis and Woodall [13] obtained a binding number condition for graphs to have k-factors. The following theorems of k-factors in terms of binding number are known.

In this paper, we obtain a binding number condition for a graph to have a k-factor excluding a given r-factor, which is an extension of Theorems 1, 2, and 3. The main result will be given in the following section.

In this section, we give our main results, which are the following theorems.

If r = 0 in Theorem 4, then we obtain the following corollary.

If Q is a Hamiltonian cycle in Theorem 4, then we obtain the following corollary.

Unfortunately, the authors do not know whether the conditions in Theorem 4 are the best possible or not. Hence, we pose the following conjecture.

Using Theorem 4, we obtain a binding number condition for a graph to have a k-factor including a given r-factor.

If Q is a Hamiltonian cycle in Theorem 8, then we obtain the following corollary.

The previous results on a graph to have a k-factor including a given Hamiltonian cycle are shown in the following

Let G be a graph, and S, T ⊆ V (G) with S ⋂ T = ∅. We use e_G(S, T ) to denote the number of edges that join S and T . For an integer k ≥ 1, a component C of G − (S ∪ T ) is called an odd component if k|V (C)| + e_G(V (C), T ) is odd. We write

δG(S,T)=k|S|+dG−S(T)−hG(S,T),$$\begin{array}{} \displaystyle {\delta _G}\left( {S,T} \right) = k|S| + {d_{G - S}}\left( T \right) - {h_G}\left( {S,T} \right), \end{array}$$

where d_G−S(T ) = Σ_x∊Td_G−S(x) and h_G(S, T ) is the number of odd components of G − (S ∪ T ).

The proof of Theorem 4 relies heavily on the following lemmas.

Proof of Theorem 4. According to the assumption of Theorem 4, G has an r-factor Q. Set H = G − E(Q). Then V (H) = V (G). Hence G has a desired factor if and only if H has a k-factor. By way of contradiction, we assume that H has no k-factor. Then, by Lemma 12, there exist two disjoint subsets S and T of V (H) = V (G) such that

δG(S,T)=k|S|+dH−S(T)−K|T|−hH(S,T)≤−2,$$\begin{array}{} {{\delta _G}\left( {S,T} \right) = k\left| S \right| + {d_{H - S}}\left( T \right) - K\left| T \right| - {h_H}\left( {S,T} \right) \le - 2,} \end{array}$$(2)

where h_H(S, T ) denotes the number of odd components of H − (S ∪ T ). And subject to (2), we choose S and T such that |S ∪ T| is as large as possible. From (2), we have

k|S|+dH−S(T)−K|T|−ω≤−2,$$\begin{array}{} {k\left| S \right| + {d_{H - S}}\left( T \right) - K\left| T \right| - {\bf{\omega }} \le - 2,} \end{array}$$(3)

where ω denotes the number of components of H − (S ∪ T ). Obviously,

ω≤n−S−T.$$\begin{array}{l} {{\bf{\omega }} \le n - \left| S \right| - \left| T \right|.} \end{array}$$(4)

If ω > 0, then let m denote the minimum order of components of H − (S ∪ T ). We shall make use of the obvious facts that

δ(H)≤m−1+|S|−|T|$$\begin{array}{} {\delta \left( H \right) \le m - 1 + \left| S \right| - \left| T \right|} \end{array}$$(5)

and

mω≤|V(H)|−|S|−|T|=n−|S|−|T|≤n.$$\begin{array}{} {m\omega \le \left| {V\left( H \right)} \right| - \left| S \right| - \left| T \right| = n - \left| S \right| - \left| T \right| \le n.} \end{array}$$(6)

Moreover, it follows from Lemma 13 and the choice of S and T that m ≥ 3.

According to Lemma 14 and bind(G)≥(2k−1)(n−1)kn−(r+1)(2k−1)+1$\begin{array}{} \left( G \right) \ge \frac{{\left( {2k - 1} \right)\left( {n - 1} \right)}}{{kn - \left( {r + 1} \right)\left( {2k - 1} \right) + 1}} \end{array}$, we have

δ(G)≥n−n−1(2k−1)(n−1)kn−(r+1)(2k−1)+1=(k−1)n+(r+1)(2k−1)−12k−1.$$\begin{array}{} {\delta \left( G \right) \ge n - \frac{{n - 1}}{{\frac{{\left( {2k - 1} \right)\left( {n - 1} \right)}}{{kn - \left( {r + 1} \right)\left( {2k - 1} \right) + 1}}}} = \frac{{\left( {k - 1} \right)n + \left( {r + 1} \right)\left( {2k - 1} \right) - 1}}{{2k - 1}}.} \end{array}$$(7)

which contradicts the assumption that H = G − E(Q) is connected.

If S ≠ ∅, then from (3) and (4) we deduce

0<k|S|+2≤ω≤n−|S|.$$\begin{array}{} {0 < k\left| S \right| + 2 \le \omega \le n - \left| S \right|.} \end{array}$$(8)

Using (8), we have

n−1−k|S|−|S|≥1.$$\begin{array}{} {n - 1 - k\left| S \right| - \left| S \right| \ge 1.} \end{array}$$(9)

In view of (5), (6) and (8), we obtain

δ(H)≤m−1+|S|≤n−|S|ω−1+|S|≤−|S|k|S|+2−1+|S|<−|S|k|S|+1−1+|S|=n−1k+1−(n−1−k|S|−|S|)(k|S|−k)(k+1)(k|S|+1.$$\begin{array}{} {\delta \left( H \right)}&{ \le m - 1 + \left| S \right| \le \frac{{n - \left| S \right|}}{\omega } - 1 + \left| S \right|}\\ {}&{ \le \frac{{ - \left| S \right|}}{{k\left| S \right| + 2}} - 1 + \left| S \right| < \frac{{ - \left| S \right|}}{{k\left| S \right| + 1}} - 1 + \left| S \right|}\\ {}&{ = \frac{{n - 1}}{{k + 1}} - \frac{{\left( {n - 1 - k\left| S \right| - \left| S \right|} \right)\left( {k\left| S \right| - k} \right)}}{{\left( {k + 1} \right)(k\left| S \right| + 1}}.} \end{array}$$

Combining this with (9) and |S| ≥ 1, we have

δ(H)<n−1k+1−(n−1−k|S|−|S|)(k|S|−k(K+1)(k|S|+1≤n−1k+1.$$\begin{array}{} {\delta \left( H \right) < \frac{{n - 1}}{{k + 1}} - \frac{{\left( {n - 1 - k\left| S \right| - \left| S \right|} \right)(k\left| S \right| - k}}{{\left( {K + 1} \right)(k\left| S \right| + 1}} \le \frac{{n - 1}}{{k + 1}}.} \end{array}$$(10)

Note that δ (H) = δ (G) − r. Using (7) and (10), we have

n−1k+1>δ(H)=δ(G)−r≥(K−1)n+(r+1)(2k−1)−12k−1−r(k−1)n+2k−22k−1,$$\begin{array}{} \frac{{n - 1}}{{k + 1}} > \delta \left( H \right) = \delta \left( G \right) - r \ge \frac{{\left( {K - 1} \right)n + \left( {r + 1} \right)\left( {2k - 1} \right) - 1}}{{2k - 1}} - r\frac{{\left( {k - 1} \right)n + 2k - 2}}{{2k - 1}}, \end{array}$$

which is a contradiction since k ≥ 2. Hence, T ≠ ∅. The proof of Claim 3 is complete.

Since T ≠ ∅, we define

h=min{dH−S(x):x∈T}.$$\begin{array}{} h = {\rm{min\{ }}{d_{H - S}}\left( x \right){\rm{:}}x \in T{\rm{\} }}{\rm{.}} \end{array}$$

The following proof splits into four cases by the value of h.

Case 1. h = 0.

Set X = {x : x ∊ T, d_H−S(x) = 0}. Clearly, X ≠ ∅ since h = 0 and X is an independent subset of V (H). It is easy to see that

|S|≥|NH(X)|.$$\begin{array}{} {\left| S \right| \ge \left| {{N_H}\left( X \right)} \right|.} \end{array}$$(11)

Note that |N_H(X)| ≥ |N_G(X)| − r|X|. According to (11) and the assumption of Theorem 4, we obtain

|S|≥|NH(X)|≥|NG(X)|−r|X|>(k−1)n+|X|−22k−1.$$\begin{array}{} \displaystyle {\left| S \right| \ge |{N_H}\left( X \right)\left| \ge \right|{N_G}\left( X \right)\left| { - r\left| X \right|} \right\rangle \frac{{\left( {k - 1} \right)n + \left| X \right| - 2}}{{2k - 1}}.} \end{array}$$(12)

In view of (3), (4), (12), |S| + |T| ≤ n and k ≥ 2, we deduce

−2≥k|S|+dH−s(T)−k|T|−ω≥k|S|+dH−s(T)−k|T|−(n−|S|−|T|)≥k|S|+(T)−|X|−k|T|−n−|S|−|T|=(k+1)|S|+(k−2)|T|−|X|−n≥(k+1)|S|+(k−2)(n−|S|)−|X|−n=(2k−1)|S|−(k−1)n−|X|>(2k−1).(k−|1)n+|X|−22k−1−(k−1)n−|X|=−2.$$\begin{array}{} \displaystyle \begin{array}{l} - 2 \ge k|S| + {d_{H - S}}(T) - k|T| - \omega \\ \ge k|S| + {d_{H - S}}(T) - k|T| - (n - |S| - |T|)\\ \ge k|S| + |T| - |X| - k|T| - n + |S| + |T|\\ {\rm{ = (k + 1)|S| - (k - 2)|T| - |X| - n}}\\ \ge (k + 1)|S| - (k - 2)(n - |S|) - |X| - n\\ {\rm{ = (2k - 1)|S| - (k - 1)n - |X|}}\\ > (2k - 1) \cdot \frac{{(k - 1)n + |X| - 2}}{{2k - 1}} - (k - 1)n - |X|\\ {\rm{ = - 2}}{\rm{.}} \end{array} \end{array}$$

That is a contradiction.

Case 2. 1 ≤ h ≤ k − 1.

Note that δ (H) |S| + h and δ (H) = δ (G) − r. And using (7), we obtain

|S|≥δ(G)−r−h≥(k−1)n+2k−22k−1−h.$$\begin{array}{} \displaystyle \left| S \right| \ge \delta \left( G \right) - r - h \ge \frac{{\left( {k - 1} \right)n + 2k - 2}}{{2k - 1}} - h. \end{array}$$(13)

According to (3), (4), |S| + |T| ≤ n and 1 ≤ h ≤ k − 1, we have

−2≥k|S|+dH−s(T)−k|T|−ω≥k|S|+h(T)−k|T|−(n−|S|−|T|)=(k+1)|S|+(k−1−h)|T|−n≥(k+1)|S|+(k−1−h)(n−|S|)−n=(2k−1)|S|−(k−1)n,$$\begin{array}{} \displaystyle { - 2}&{ \ge k\left| S \right| + {d_{H - s}}\left( T \right) - k\left| T \right| - \omega }\\ {}&{ \ge k\left| S \right| + h\left( T \right) - k\left| T \right| - \left( {n - \left| S \right| - \left| T \right|} \right)}\\ {}&{ = \left( {k + 1} \right)\left| S \right| + \left( {k - 1 - h} \right)\left| T \right| - n}\\ {}&{ \ge \left( {k + 1} \right)\left| S \right| + \left( {k - 1 - h} \right)\left( {n - \left| S \right|} \right) - n}\\ {}&{ = \left( {2k - 1} \right)\left| S \right| - \left( {k - 1} \right)n,} \end{array}$$

that is,

−2≥(2k−h)|S|−(k−h)n.$$\begin{array}{} \displaystyle { - 2 \ge \left( {2k - h} \right)\left| S \right| - \left( {k - h} \right)n.} \end{array}$$(14)

Multiplying (14) by (2k − 1) and rearranging, and then using (13),

0≥(2k−h)(2k−1)|S|−(2k−1)(k−h)n+2(2k−1)≥(2k−h)((k−1)n+2k−2−(2k−1)h)−(2k−1)(k−h)n+2(2k−1)=(h−1)(kn−(2k−1)(2k−h)+1)+2k−1,$$\begin{array}{} \displaystyle 0&{ \ge \left( {2k - h} \right)\left( {2k - 1} \right)\left| S \right| - \left( {2k - 1} \right)\left( {k - h} \right)n + 2\left( {2k - 1} \right)}\\ {}&{ \ge \left( {2k - h} \right)\left( {\left( {k - 1} \right)n + 2k - 2 - \left( {2k - 1} \right)h} \right) - \left( {2k - 1} \right)\left( {k - h} \right)n + 2\left( {2k - 1} \right)}\\ {}&{ = \left( {h - 1} \right)\left( {kn - \left( {2k - 1} \right)\left( {2k - h} \right) + 1} \right) + 2k - 1,} \end{array}$$

that is,

0≥(h−1)(kn−(2k−1)(2k−h)+1)+2k−1.$$\begin{array}{} \displaystyle {0 \ge \left( {h - 1} \right)\left( {kn - \left( {2k - 1} \right)\left( {2k - h} \right) + 1} \right) + 2k - 1.} \end{array}$$(15)

If h = 1, then from (15) we obtain

0≥2k−1>0,$$\begin{array}{} \displaystyle 0 \ge 2k - 1 > 0, \end{array}$$

which is a contradiction.

If h = 2, then by (15) and n≥(2k−1)(2k−3)k$\begin{array}{} \displaystyle n \ge \frac{{\left( {2k - 1} \right)\left( {2k - 3} \right)}}{k} \end{array}$, we obtain

0≥(h−1)(kn−(2k−1)(2k−h)+1)+2k−1=kn−(2k−1)(2k−2)+1+2k−1≥(2k−1)(2k−3)−(2k−1)(2k−2)+1+2k−1=1,$$\begin{array}{} \displaystyle 0&{ \ge \left( {h - 1} \right)\left( {kn - \left( {2k - 1} \right)\left( {2k - h} \right) + 1} \right) + 2k - 1}\\ {}&{ = kn - \left( {2k - 1} \right)\left( {2k - 2} \right) + 1 + 2k - 1}\\ {}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} { \ge \left( {2k - 1} \right)\left( {2k - 3} \right) - \left( {2k - 1} \right)\left( {2k - 2} \right) + 1 + 2k - 1} \end{array}}\\ {\qquad \qquad \;\;\;{\mkern 1mu} \qquad \qquad \qquad \qquad \quad } \end{array}}\\ {}&{ = 1,} \end{array}$$

a contradiction.

If 3 ≤ h ≤ k − 1, then using (15) and n≥(2k−1)(2k−3)k$\begin{array}{} \displaystyle n \ge \frac{{\left( {2k - 1} \right)\left( {2k - 3} \right)}}{k} \end{array}$, we have

0≥(h−1)(kn−(2k−1)(2k−h)+1)+2k−1≥(h−1)(kn−(2k−1)(2k−3)+1)+2k−1≥h−1+2k−1>2k−1>0,$$\begin{array}{} \displaystyle 0&{ \ge \left( {h - 1} \right)\left( {kn - \left( {2k - 1} \right)\left( {2k - h} \right) + 1} \right) + 2k - 1}\\ {}&{ \ge \left( {h - 1} \right)\left( {kn - \left( {2k - 1} \right)\left( {2k - 3} \right) + 1} \right) + 2k - 1}\\ {}&{\begin{array}{*{20}{c}} { \ge h - 1 + 2k - 1}\\ {\qquad \qquad \;\;\;{\mkern 1mu} \qquad \qquad \qquad \qquad \quad } \end{array}}\\ {}&{ > 2k - 1 > 0,} \end{array}$$

that is a contradiction.

Case 3. h = k.

According to (3), we obtain

−2≥k|S|+dH−S(T)−k|T|−ω≥k|S|+h|T|−k|T|−ω=k|S|−ω,$$\begin{array}{} \displaystyle { - 2}&{ \ge k\left| S \right| + {d_{H - S}}\left( T \right) - k\left| T \right| - \omega }\\ {}&{ \ge k\left| S \right| + h\left| T \right| - k\left| T \right| - \omega }\\ {}&{ = k\left| S \right| - \omega ,} \end{array}$$

which implies

ω≥k|S|+2.$$\begin{array}{} \displaystyle {\omega \ge k\left| S \right| + 2.} \end{array}$$(16)

In view of (6) and Claim 3, we have

ω≤n−|S|−|T|m≤n−|S|−1m.$$\begin{array}{} \displaystyle \omega \le \frac{{n - \left| S \right| - \left| T \right|}}{m} \le \frac{{n - \left| S \right| - 1}}{m}. \end{array}$$

Combining this with (16) and m ≥ 3, we infer

k|S|+2≤ω≤n−|S|−|T|m≤n−|S|−1m,$$\begin{array}{} \displaystyle {k\left| S \right| + 2 \le \omega \le \frac{{n - \left| S \right| - \left| T \right|}}{m} \le \frac{{n - \left| S \right| - 1}}{m},} \end{array}$$(17)

which implies

|S|≤n−73k+1.$$\begin{array}{} \displaystyle {\left| S \right| \le \frac{{n - 7}}{{3k + 1}}.} \end{array}$$(18)

Using (7), h = k, δ (H) = δ (G) − r and δ (H) ≤ |S| + h, we deduce

|S|≥(k−1)n+2k−22k−1−k,$$\begin{array}{} \displaystyle {\left| S \right| \ge \frac{{\left( {k - 1} \right)n + 2k - 2}}{{2k - 1}} - k,} \end{array}$$

which contradicts (18) since k ≥ 2 and n≥(2k−1)(2k−3)k$\begin{array}{} \displaystyle n \ge \frac{{\left( {2k - 1} \right)\left( {2k - 3} \right)}}{k} \end{array}$.

Case 4. h ≥ k + 1.

According to (3), we have

−2≥k|S|+dH−S(T)−k|T|−ω≥k|S|+h|T|−k|T|−ω≥k|S|+|T|−ω.$$\begin{array}{} \displaystyle { - 2}&{ \ge k\left| S \right| + {d_{H - S}}\left( T \right) - k\left| T \right| - \omega }\\ {}&{ \ge k\left| S \right| + h\left| T \right| - k\left| T \right| - \omega }\\ {}&{ \ge k\left| S \right| + \left| T \right| - \omega .} \end{array}$$

Combining this with Claim 3, we obtain

ω≥k|S|+|T|+2≥|S|+|T|+2≥3.$$\begin{array}{} \displaystyle \omega \ge k\left| S \right| + \left| T \right| + 2 \ge \left| S \right| + \left| T \right| + 2 \ge 3. \end{array}$$(19)

In view of (5), (6), and (19), m ≥ 3 and δ (G) = δ (H) + r, we obtain

δ(G)=δ(H)+r≤m−1+|S|+|T|+r≤m−1+ω−2+r=m+ω−2+r≤m+ω−3+(m−3)(ω−3)3+r=mω3+r≤n3+r,$$\begin{array}{} \displaystyle {\delta \left( G \right)}&{ = \delta \left( H \right) + r \le m - 1 + \left| S \right| + \left| T \right| + r}\\ {}&{ \le m - 1 + \omega - 2 + r = m + \omega - 2 + r}\\ {}&{ \le m + \omega - 3 + \frac{{\left( {m - 3} \right)\left( {\omega - 3} \right)}}{3} + r}\\ {}&{ = \frac{{m\omega }}{3} + r \le \frac{n}{3} + r,} \end{array}$$

which contradicts (7).

Hence, G has a desired factor, that is, G has a k-factor excluding a given r-factor. This completes the proof of Theorem 4.