This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
Introduction
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 NG(x) of x is the set of vertices of G adjacent to x, and the degree dG(x) of x is |NG(x)|. For S ⊆ V (G), we write NG(S) = ∪x∊SNG(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$\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 dF(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.
Theorem 1
(Anderson [11]). Let G be a graph of order n. If n is even and bind$\begin{array}{}
\left( G \right) \ge \frac{4}{3}
\end{array}$, then G has a 1-factor.
Theorem 2
(Woodall [12]). Let G be a graph. If bind$\begin{array}{}
\left( G \right) \ge \frac{3}{2}
\end{array}$, then G has a Hamiltonian cycle (or a 2-factor).
Theorem 3
(Katerinis and Woodall [13]). Let k ≥ 2 be an integer and let G be a graph of order n ≥ 4k − 6 and binding number bind(G) such that kn is even and bind$\begin{array}{}
\left( G \right) > \frac{{\left( {2k - 1} \right)\left( {n - 1} \right)}}{{k\left( {n - 2} \right) + 3}}
\end{array}$. Then G has a k-factor.
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.
Main Theorems
In this section, we give our main results, which are the following theorems.
Theorem 4
Let k and r be two nonnegative integers with k ≥ 2, and let G be a graph of order n with$\begin{array}{}
n \ge \frac{{\left( {2k - 1} \right)\left( {2k - 3} \right)}}{k}
\end{array}$, and let G have an r-factor Q. Suppose that kn is even, bind$\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}$and$\begin{array}{}
\left| {{N_G}\left( X \right)} \right| > \frac{{\left( {k - 1} \right)n + \left( {2rk - r + 1} \right)\left| X \right| - 2}}{{2k - 1}}
\end{array}$for any nonempty independent subset X of V (G). Then G has a k-factor excluding a given r-factor Q if G − E(Q) is connected.
If r = 0 in Theorem 4, then we obtain the following corollary.
Corollary 5
Let k be a nonnegative integer with k ≥ 2, and let G be a graph of order n with$\begin{array}{}
n \ge \frac{{\left( {2k - 1} \right)\left( {2k - 3} \right)}}{k}
\end{array}$. Suppose that kn is even, bind$\begin{array}{}
\left( G \right) \ge \frac{{\left( {2k - 1} \right)\left( {n - 1} \right)}}{{kn - \left( {2k - 1} \right)}}
\end{array}$and$\begin{array}{}
\left| {{N_G}\left( X \right)} \right| > \frac{{\left( {k - 1} \right)n + |4k - 1)\left| X \right| - 2}}{{2k - 1}}
\end{array}$for any nonempty independent subset X of V (G). Then G has a k-factor.
If Q is a Hamiltonian cycle in Theorem 4, then we obtain the following corollary.
Corollary 6
Let k be a nonnegative integer with k ≥ 2, and let G be a Hamiltonian graph of order n with$\begin{array}{}
n \ge \frac{{\left( {2k - 1} \right)\left( {2k - 3} \right)}}{k}
\end{array}$. Suppose that kn is even, bind$\begin{array}{}
\left( G \right) \ge \frac{{\left( {2k - 1} \right)\left( {n - 1} \right)}}{{kn - 2\left( {3k - 2} \right)}}
\end{array}$and$\begin{array}{}
\left| {{N_G}\left( X \right)} \right| > \frac{{\left( {k - 1} \right)n + |4k - 1)\left| X \right| - 2}}{{2k - 1}}
\end{array}$for any nonempty independent subset X of V (G). Then G has a k-factor excluding a given Hamiltonian cycle C if G − E(C) is connected.
Unfortunately, the authors do not know whether the conditions in Theorem 4 are the best possible or not. Hence, we pose the following conjecture.
Conjecture 7
Let k and r be two nonnegative integers with k ≥ 2, and let G be a graph of order n with$\begin{array}{}
n \ge \frac{{\left( {2k - 1} \right)\left( {2k - 3} \right)}}{k}
\end{array}$, and let G have an r-factor Q. Suppose that kn is even, bind$\begin{array}{}
\left( G \right) \ge \frac{{\left( {2k - 1} \right)\left( {n - 1} \right)}}{{kn - \left( {r + 1} \right)\left( {2k - 1} \right) + 2}}
\end{array}$and$\begin{array}{}
\left| {{N_G}\left( X \right)} \right| \ge \frac{{\left( {k - 1} \right)n + \left( {2rk - r + 1} \right)\left| X \right| - 2}}{{2k - 1}}
\end{array}$for any nonempty independent subset X of V (G). Then G has a k-factor excluding a given r-factor Q if G − E(Q) is connected.
Using Theorem 4, we obtain a binding number condition for a graph to have a k-factor including a given r-factor.
Theorem 8
Let k and r be two nonnegative integers with k ≥ r + 2, and let G be a graph of order n with$\begin{array}{}
n \ge \frac{{\left( {2k - 2r - 1} \right)\left( {2k - 2r - 3} \right)}}{{k - r}}
\end{array}$, and let G have an r-factor Q. Suppose that kn and rn are both even, bind$\begin{array}{}
\left( G \right) \ge \frac{{\left( {2k - 2r - 1} \right)\left( {n - 1} \right)}}{{\left( {k - r} \right)n - \left( {r + 1} \right)\left( {2k - 2r - 1} \right) + 1}}
\end{array}$and$\begin{array}{}
\left| {{N_G}\left( X \right)} \right| > \frac{{\left( {k - r - 1} \right)n + \left( {2rk - 2{r^2} - r + 1} \right)\left| X \right| - 2}}{{2k - 2r - 1}}
\end{array}$for any nonempty independent subset X ofV (G). Then G has a k-factor including a given r-factor Q if G − E(Q) is connected.
Proof. By the assumption of Theorem 8, G has an r-factor Q. Let m = k − r. Then we have m ≥ 2, mn even, $\begin{array}{}
n \ge \frac{{\left( {2m - 1} \right)\left( {2m - 3} \right)}}{m}
\end{array}$, bind$\begin{array}{}
\left( G \right) \ge \frac{{\left( {2m - 1} \right)\left( {n - 1} \right)}}{{mn - \left( {r + 1} \right)\left( {2m - 1} \right) + 1}},\left| {{N_G}\left( X \right)} \right| > \frac{{\left( {m - 1} \right)n + \left( {2rm - r + 1} \right)\left| X \right| - 2}}{{2m - 1}}
\end{array}$ for any nonempty independent subset X of V (G), and G − E(Q) connected. According to Theorem 4, G has an m-factor F′ excluding a given r-factor Q, and G has a k-factor F (F = E(F′) ∪ [E(Q)) including a given r-factor Q. This completes the proof of Theorem 8.
If Q is a Hamiltonian cycle in Theorem 8, then we obtain the following corollary.
Corollary 9
Let k be a nonnegative integer with k ≥ 4, and let G be a Hamiltonian graph of order n with$\begin{array}{}
n \ge \frac{{\left( {2k - 5} \right)\left( {2k - 7} \right)}}{{k - 2}}
\end{array}$. Suppose that kn is even, bind$\begin{array}{}
\left( G \right) \ge \frac{{\left( {2k - 5} \right)\left( {n - 1} \right)}}{{\left( {k - 2} \right)n - 2\left( {3k - 8} \right)}}
\end{array}$and$\begin{array}{}
\left| {{N_G}\left( X \right)} \right| > \frac{{\left( {k - 3} \right)n + \left( {4k - 9} \right)\left| X \right| - 2}}{{2k - 5}}
\end{array}$for any nonempty independent subset X of V (G). Then G has a k-factor including a given Hamiltonian cycle C if G − E(C) is connected.
The previous results on a graph to have a k-factor including a given Hamiltonian cycle are shown in the following
Let k ≥ 2 be an integer and let G be a graph of order n > 8k2 − 2(α + 12)k + 3α + 16, where α = 3 for odd k and α = 4 for even k. Suppose that kn is even and the minimum degree δ (G) of G is at least k. If for any nonadjacent vertices x and y of G, dG(x) + dG(y) ≥ n + α, then G has a k-factor including a given Hamiltonian cycle.
Let k ≥ 2 be an integer and let G be a graph of order n > 12(k −2)2 + 2(5− α)(k − 2) − α. Suppose that kn is even, δ (G) ≥ k and$\begin{array}{}
\max \left\{ {{d_G}\left( x \right),{d_G}\left( y \right)} \right\} \ge \frac{{n + \alpha }}{2}
\end{array}$for each pair of nonadjacent vertices x and y in G, where α = 3 for odd k and α = 4 for even k. Then G has a k-factor including a given Hamiltonian cycle C if G − E(C) is connected.
The Proof of Theorem 4
Let G be a graph, and S, T ⊆ V (G) with S ⋂ T = ∅. We use eG(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)| + eG(V (C), T ) is odd. We write
Let W = G − S − T and let w be the number of components of W. If |S ∪ T| is maximal subject to (1), then |V (C)| ≥ 3 for every component C of W , so that |V (W )| ≥ 3ω.
Let G be a graph of order n with bind(G) ≥ c. Then$\begin{array}{}
\delta \left( G \right) \ge n - \frac{{n - 1}}{c}
\end{array}$.
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
$$\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}$$
where hH(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
$$\begin{array}{}
{k\left| S \right| + {d_{H - S}}\left( T \right) - K\left| T \right| - {\bf{\omega }} \le - 2,}
\end{array}$$
where ω denotes the number of components of H − (S ∪ T ). Obviously,
$$\begin{array}{l}
{{\bf{\omega }} \le n - \left| S \right| - \left| T \right|.}
\end{array}$$
If ω > 0, then let m denote the minimum order of components of H − (S ∪ T ). We shall make use of the obvious facts that
$$\begin{array}{}
{\delta \left( H \right) \le m - 1 + \left| S \right| - \left| T \right|}
\end{array}$$
and
$$\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}$$
Moreover, it follows from Lemma 13 and the choice of S and T that m ≥ 3.
According to Lemma 14 and bind$\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
If 3 ≤ h ≤ k − 1, then using (15) and $\begin{array}{}
\displaystyle
n \ge \frac{{\left( {2k - 1} \right)\left( {2k - 3} \right)}}{k}
\end{array}$, we have