Component factors and binding number conditions in graphs

1.   Introduction

We discuss only finite simple graphs in this paper. Let $G = (V(G), E(G))$ be a graph, where $V(G)$ denotes the vertex set of $G$ and $E(G)$ denotes the edge set of $G$. The number of vertices of a graph $G$ is called the order of $G$. For a graph $G$ and $x\in V(G)$, we denote by $d_G(x)$ the degree of $x$ in $G$, and by $N_G(x)$ the set of vertices adjacent to $x$ in $G$. Note that $d_G(x) = |N_G(x)|$. Let $X$ be a vertex subset of $G$. We use $G[X]$ to denote the subgraph of $G$ induced by $X$, and write $G-X = G[V(G)\setminus X]$ and $N_G(X) = \bigcup\limits_{x\in X}{N_{G}(x)}$. For $E'\subseteq E(G)$, we use $G-E'$ to denote the subgraph derived from $G$ by deleting the edges in $E'$. We use $I(G)$ to denote the set of isolated vertices of $G$, and write $i(G) = |I(G)|$. The number of connected components of $G$ is denoted by $\omega(G)$. We denote by $\kappa(G)$ and $\lambda(G)$ the vertex connectivity and the edge connectivity of $G$, respectively. The vertex connectivity of $G$ is simply called the connectivity of $G$. For two graphs $G_1$ and $G_2$, we denote by $G_1\cup G_2$ the union of $G_1$ and $G_2$, and by $G_1\vee G_2$ the join of $G_1$ and $G_2$. We use $K_n$, $P_n$ and $C_n$ to denote the complete graph, the path and the cycle of order $n$, respectively. $K_{n, m}$ is the complete bipartite graph with the bipartition $(X, Y)$, where $|X| = m$, $|Y| = n$. We denote by $T$ a tree, and by $Leaf(T)$ the set of leaves in $T$. An edge of $T$ incident with a leaf is called a pendant edge. Especially, the number of leaves in $T$ is equal to that of pendant edges in $T$ under the case that the order of $T$ is at least 3.

For a set $X$, we use $|X|$ to denote the cardinality of $X$. Woodall ^[15] introduced a parameter, binding number of a graph $G$, denoted by $bind(G)$, which is defined by

For a set $\mathcal{H}$ of connected graphs, an $\mathcal{H}$-factor of a graph $G$ is a spanning subgraph $H$ of $G$ such that every component of $H$ is isomorphic to a member of $\mathcal{H}$. An $\mathcal{H}$-factor is also referred as a component factor. A graph $G$ is called an $(\mathcal{H}, m)$-factor deleted graph if for every $E'\subseteq E(G)$ with $|E'| = m$, $G-E'$ admits an $\mathcal{H}$-factor. Obviously, an $(\mathcal{H}, 0)$-factor deleted graph is equivalent to a graph having an $\mathcal{H}$-factor. An $(\mathcal{H}, 1)$-factor deleted graph is simply called an $\mathcal{H}$-factor deleted graph. A graph $G$ is called an $(\mathcal{H}, n)$-factor critical graph if for every $N\subseteq V(G)$ with $|N| = n$, $G-N$ admits an $\mathcal{H}$-factor. Clearly, an $(\mathcal{H}, 0)$-factor critical graph is equivalent to a graph having an $\mathcal{H}$-factor.

Tutte ^[12] obtained a necessary and sufficient condition for a graph to have a $\{K_2, C_n:n\geq3\}$-factor. Egawa, Kano and Yan ^[2] gave a shorter proof. Kano, Lee and Suzuki ^[5] showed two results for graphs to admit path and cycle factors. Klopp and Steffen ^[10] posed some properties for the existence of $\{K_{1, 1}, K_{1, 2}, C_m:m\geq3\}$-factors in graphs. Amahashi and Kano ^[1] got a criterion for a graph with a $\{K_{1, j}:1\leq j\leq k\}$-factor. Kano, Lu and Yu ^[6] derived a result for a graph having a $\{K_{1, 2}, K_{1, 3}, K_5\}$-factor. Kano and Saito ^[8] posed a sufficient condition for a graph to admit a $\{K_{1, j}:k\leq j\leq2k\}$-factor. Zhou, Bian and Pan ^[23], Zhou ^[21,22], Zhou, Sun and Liu ^[27], Zhou, Yang and Xu ^[30], Kelmans ^[9], Johnson, Paulusma and Wood ^[4], Gao, Wang and Chen ^[3] studied the existence of path-factors in graphs and derived some results for graphs to have path factors. Zhou, Bian and Sun ^[24] presented two results on the existence of component factors in graphs. Wang and Zhang ^[14], Zhou ^[20], Zhou, Liu and Xu ^[26] established some relationships between binding number and graph factors. Some other results on graph factors were derived by Yuan and Hao ^[17,18], Wang and Zhang ^[13], Wu, Yuan and Gao ^[16], Lv ^[11], Zhou, Zhang and Xu ^[31], Zhou^[19], Zhou, Liu and Xu ^[25], Zhou, Sun and Pan ^[28], Zhou, Xu and Sun ^[29]. The following results on component factors of graphs are known.

Theorem 1. (Tutte ^[12]). A graph $G$ admits a $\{K_2, C_n:n\geq3\}$-factor if and only if

for any $X\subset V(G)$.

Theorem 2. (Amahashi and Kano ^[1]). Let $k$ be an integer with $k\geq2$. A graph $G$ admits a $\{K_{1, j}:1\leq j\leq k\}$-factor if and only if

for any $X\subset V(G)$.

Theorem 3. (Kano, Lu and Yu ^[6]). A graph $G$ admits a $\{K_{1, 2}, K_{1, 3}, K_5\}$-factor if

for any $X\subset V(G)$.

In this article, we investigate the existence of component factors in graphs and get four results on component factors with given properties in graphs, which are shown in Sections 2 and 3.

2.   Graph with a $\{P_2, C_3, P_5, \mathcal{T}(3)\}$-factor

In this section, we always assume that $\mathcal{F} = \{P_2, C_3, P_5, \mathcal{T}(3)\}$, where $\mathcal{T}(3)$ is defined as follows: for any $\{1, 3\}$-tree $R$ ($d_R(x)\in\{1, 3\}$ for each $x\in V(R)$), a new tree $T_R$ is derived from $R$ by inserting a new vertex of degree 2 into each edge of $R$, and by adding a new pendant edge to each leaf of $R$. Then the tree $T_R$ is a $\{1, 2, 3\}$-tree admitting $|E(R)|+|Leaf(R)|$ vertices of degree 2 and possesses the same number of leaves as $R$. The collection of such $\{1, 2, 3\}$-trees $T_R$ generated from all $\{1, 3\}$-trees $R$ is denoted by $\mathcal{T}(3)$.

Kano, Lu and Yu ^[7] derived a characterization for a graph with an $\mathcal{F}$-factor.

Theorem 4. (Kano, Lu and Yu ^[7]). A graph $G$ admits an $\mathcal{F}$-factor if and only if

for any $X\subset V(G)$.

Using Theorem 4, we shall verify the following two theorems on the existence of $\mathcal{F}$-factors with given properties.

Theorem 5. A $(2m+1)$-connected graph $G$ is an $(\mathcal{F}, m)$-factor deleted graph if its binding number $bind(G)\geq\frac{4m+2}{2m+3}$, where $m$ is a nonnegative integer.

Theorem 6. An $(n+2)$-connected graph $G$ is an $(\mathcal{F}, n)$-factor critical graph if its binding number $bind(G)\geq\frac{2+n}{3}$, where $n$ is a nonnegative integer.

Remark 1. We now show that Theorem 5 is best possible in the following sense. That is to say, we cannot replace $(2m+1)$-connected graph $G$ and $bind(G)\geq\frac{4m+2}{2m+3}$ by $(2m)$-connected graph $G$ and $bind(G)\geq\frac{4m+2}{2m+4}$ in Theorem 5.

Next, we construct a graph $G = K_{2m}\vee((m+1)K_2\cup(2K_1))$, where $m = 0$ or 1. Then $bind(G) = \frac{4m+2}{2m+4}$ and $G$ is $(2m)$-connected. Let $G' = G-E'$, where $E'\subseteq E((m+1)K_2)$ with $|E'| = m$. We select $X = V(K_{2m})\subseteq V(G')$. Thus, we derive

which implies that $G'$ has no $\mathcal{F}$-factor by Theorem 4, namely, $G$ is not an $(\mathcal{F}, m)$-factor deleted graph.

Remark 2. Now, we show that $bind(G)\geq\frac{2+n}{3}$ in Theorem 6 cannot be replaced by $bind(G)\geq\frac{2+n}{4}$. In the above sense, the result in Theorem 6 is best possible.

We construct a graph $G = K_{n+2}\vee(4K_1)$, where $n$ is a nonnegative integer. Obviously, $G$ is $(n+2)$-connected, and we easily see $bind(G) = \frac{2+n}{4}$. Let $G' = G-D$ for any $D\subseteq V(K_{n+2})$ with $|D| = n$. We choose $X = V(K_{n+2})\setminus D$. Then $|X| = 2$. Thus, we derive

In light of Theorem 4, $G'$ has no $\mathcal{F}$-factor, that is, $G$ is not an $(\mathcal{F}, n)$-factor critical graph.

In what follows, we verify Theorems 5 and 6.

Proof of Theorem 5. Let $G' = G-E'$ for any $E'\subseteq E(G)$ with $|E'| = m$. Then $V(G') = V(G)$ and $E(G') = E(G)\setminus E'$. To prove Theorem 5, it suffices to verify that $G'$ admits an $\mathcal{F}$-factor. We assume that $G'$ does not admit $\mathcal{F}$-factor. Then it follows from Theorem 4 that

for some subset $X$ of $V(G')$.

If $X = \emptyset$, then by (2.1) we admit $i(G')\geq1$. On the other hand, it follows from $\lambda(G)\geq\kappa(G)\geq2m+1$ that $G'$ is connected, which contradicts that $i(G')\geq1$. Hence, $X\neq\emptyset$.

In what follows, we shall consider two cases.

Case 1. $X$ is not a vertex cut set of $G$.

In this case, we derive $\omega(G-X) = \omega(G) = 1$. If $|X|\geq\frac{2}{3}(m+1)$, then we get

which contradicts (2.1).

If $|X| < \frac{2}{3}(m+1)$, then we possess

and so

In terms of (2.2), we admit

which implies that $G'-X$ is a connected graph. Hence, $\omega(G'-X) = 1$. Combining this with $X\neq\emptyset$ and (2.1), we obtain

which is a contradiction.

Case 2. $X$ is a vertex cut set of $G$.

In this case, we possess $\omega(G-X)\geq\omega(G)+1 = 2$. Combining this with $\kappa(G)\geq2m+1$, we derive

We shall discuss the following two subcases.

Subcase 2.1. $i(G-X)\leq1$.

In light of (2.3), we have

which contradicts (2.1).

Subcase 2.2. $i(G-X)\geq2$.

Since $i(G-X)\geq2$, we have $I(G-X)\neq\emptyset$ and $N_G(I(G-X))\neq V(G)$. In terms of the definition of $bind(G)$, we derive

Combining this with (2.1), (2.3) and $bind(G)\geq\frac{4m+2}{2m+3}$, we have

namely,

which contradicts (2.3). This completes the proof of Theorem 5.

Proof of Theorem 6. Let $G' = G-D$ for any $D\subseteq V(G)$ with $|D| = n$. It suffices to verify that $G'$ admits an $\mathcal{F}$-factor. On the contrary, we assume that $G'$ does not have $\mathcal{F}$-factor. Then it follows from Theorem 4 that

for some subset $X$ of $V(G')$.

Claim 1. $|X|\geq2$.

Proof. If $|X|\leq1$, then we obtain

by $G$ being an $(n+2)$-connected graph, and so

which contradicts (2.4). Claim 1 is verified.

In terms of (2.4) and Claim 1, we get

From (2.5), we know $I(G-D\cup X)\neq\emptyset$ and $N_G(I(G-D\cup X))\neq V(G)$. Combining these with (2.5), Claim 1 and the definition of $bind(G)$, we derive

which contradicts $bind(G)\geq\frac{2+n}{3}$. We finish the proof of Theorem 6.

3.   Graph with a $\{K_{1, 1}, K_{1, 2}, \cdots, K_{1, k}, \mathcal{T}(2k+1)\}$-factor

In this section, we always assume that $\mathcal{H} = \{K_{1, 1}, K_{1, 2}, \cdots, K_{1, k}, \mathcal{T}(2k+1)\}$, where $k\geq2$ is an integer and $\mathcal{T}(2k+1)$ is defined as follows: Let $R$ be a tree that satisfies the following conditions: for each $x\in V(R)-Leaf(R)$,

(a) $d_{R-Leaf(R)}(x)\in\{1, 3, \cdots, 2k+1\}$

and

(b) 2 (the number of leaves adjacent to $x$ in $R$)$+d_{R-Leaf(R)}(x)\leq2k+1$.

For such a tree $R$, we derive a new tree $T_R$ as follows:

(c) insert a new vertex of degree 2 into each edge of $R-Leaf(R)$

and

(d) for each vertex $x$ of $R-Leaf(R)$ with $d_{R-Leaf(R)}(x) = 2r+1 < 2k+1$, add $k-r-$(the number of leaves adjacent to $x$ in $R$) pendant edges to $x$.

Then the set of such trees $T_R$ for all trees $R$ satisfying conditions (a) and (b) is denoted by $\mathcal{T}(2k+1)$.

Kano, Lu and Yu ^[7] derived a necessary and sufficient condition for a graph to admit an $\mathcal{H}$-factor.

Theorem 7. (Kano, Lu and Yu ^[7]). Let $k$ be an integer with $k\geq2$. Then a graph $G$ admits an $\mathcal{H}$-factor if and only if

for every $X\subseteq V(G)$.

Lemma 1 (Zhou, Bian and Sun ^[24]). Let $G$ be a graph and $\beta\geq1$ be a real number. Then the following three statements are equivalent.

(i) $i(G-S)\leq\beta|S|$ for all $S\subset V(G)$.

(ii) $\beta|N_G(X)|\geq|X|$ for all independent set $X$ of $G$.

(iii) $\beta|N_G(Y)|\geq|Y|$ for all $Y\subset V(G)$.

Applying Theorem 7, we shall prove the following two theorems on the existence of $\mathcal{H}$-factors with given properties.

Theorem 8. Let $k$ and $m$ be two nonnegative integers with $k\geq2$. Then a $(2m+1)$-connected graph $G$ is an $(\mathcal{H}, m)$-factor deleted graph if its binding number $bind(G)\geq\frac{2}{2k-1}$.

Theorem 9. An $(n+2)$-connected graph $G$ is an $(\mathcal{H}, n)$-factor critical graph if its binding number $bind(G)\geq\frac{2+n}{2k+1}$, where $n$ and $k$ are two nonnegative integers with $k\geq2$.

Remark 3. We now explain that Theorem 8 is best possible in some sense, namely, $G$ being $(2m+1)$-connected and $bind(G)\geq\frac{2}{2k-1}$ in Theorem 8 cannot be replaced by $G$ being $(2m)$-connected and $bind(G)\geq\frac{2}{2k}$. We show this by the following example.

Let $k\geq2$ and $r\geq0$ be two integers, and $m = 1$. We construct a graph $G = K_{2m}\vee((2k)K_1\cup(m+r)K_2)$. Clearly, $G$ is $(2m)$-connected. Set $Y = V(2kK_1)$. Then $Y\neq\emptyset$ and $N_G(Y)\neq V(G)$. Thus, we derive $bind(G) = \frac{|N_G(Y)|}{|Y|} = \frac{2m}{2k} = \frac{2}{2k}$. Let $G' = G-E'$ for any $E'\subseteq E((m+r)K_2)$ with $|E'| = m = 1$. Let $X = V(K_{2m})\subseteq V(G')$. Then $|X| = 2m = 2$ and we get

In light of Theorem 7, $G'$ has no $\mathcal{H}$-factor, that is, $G$ is not $(\mathcal{H}, m)$-factor deleted.

Remark 4. We now claim that $bind(G)\geq\frac{2+n}{2k+1}$ in Theorem 9 cannot be replaced by $bind(G)\geq\frac{2+n}{2k+2}$. To show this, we construct a graph $G = K_{n+2}\vee(2k+2)K_1$, where $n$ and $k$ are two nonnegative integers with $k\geq2$. Obviously, $G$ is $(n+2)$-connected. Select $Q = V((2k+2)K_1)$. Then $Q\neq\emptyset$ and $N_G(Q)\neq V(G)$. Furthermore, we admit $bind(G) = \frac{|N_G(Q)|}{|Q|} = \frac{2+n}{2k+2}$. Let $G' = G-D$ for any $D\subseteq V(K_{n+2})$ with $|D| = n$, and $X = V(K_{n+2})\setminus D$. Then $|X| = 2$. Thus, we admit

According to Theorem 7, $G'$ has no $\mathcal{H}$-factor, namely, $G$ is not $(\mathcal{H}, n)$-factor critical.

Proof of Theorem 8. Let $G' = G-E'$ for any $E'\subseteq E(G)$ with $|E'| = m$. Then $V(G') = V(G)$ and $E(G') = E(G)\setminus E'$. To verify Theorem 8, it suffices to prove that $G'$ possesses an $\mathcal{H}$-factor. By contradiction, we assume that $G'$ has no $\mathcal{H}$-factor. Then by Theorem 7 there exists some vertex subset $X$ of $G'$ such that

If $X = \emptyset$, then it follows from (3.1) that $i(G')\geq1$. On the other hand, by $G$ being $(2m+1)$-connected, $|E'| = m$ and $G' = G-E'$, we admit

which implies that $G'$ is connected, and so $i(G') = 0$, which contradicts that $i(G')\geq1$. Therefore, $X\neq\emptyset$.

Next, we shall discuss two cases.

Case 1. $X$ is not a vertex cut set of $G$.

In this case, we have $\omega(G-X) = \omega(G) = 1$. If $|X|\geq\frac{2}{2k+1}(m+1)$, then by (3.1) we derive

which is a contradiction.

If $|X| < \frac{2}{2k+1}(m+1)$, then it follows from $|E'| = m$, $G' = G-E'$ and $k\geq2$ that

which implies that $G'-X$ is connected. Thus, we have $\omega(G'-X) = 1$. Then according to (3.1), $k\geq2$ and $X\neq\emptyset$, we get

which is a contradiction.

Case 2. $X$ is a vertex cut set of $G$.

In this case, we have $\omega(G-X)\geq\omega(G)+1 = 2$. Note that $G$ is $(2m+1)$-connected. Thus, we obtain

According to (3.2), $k\geq2$, $bind(G)\geq\frac{2}{2k-1}$ and Lemma 1, we get

which contradicts (3.1). Therefore, it follows from Theorem 7 that $G'$ admits an $\mathcal{H}$-factor, which implies that $G$ is an $(\mathcal{H}, m)$-factor deleted graph. Theorem 8 is proved.

Proof of Theorem 9. Let $G' = G-D$ for any $D\subseteq V(G)$ with $|D| = n$. It suffices to verify that $G'$ possesses an $\mathcal{H}$-factor. By contradiction, we assume that $G'$ has no $\mathcal{H}$-factor. Then it follows from Theorem 7 that

for some vertex subset $X$ of $G'$.

Case 1. $|X|\leq1$.

In this case, we derive

which implies that $G'-X$ is connected, and so $i(G'-X) = 0$, which contradicts (3.3).

Case 2. $|X|\geq2$.

It follows from (3.3) that

According to (3.4), we easily see $I(G-D\cup X)\neq\emptyset$ and $N_G(I(G-D\cup X))\neq V(G)$. Combining these with (3.4) and the definition of $bind(G)$, we have

which contradicts that $bind(G)\geq\frac{2+n}{2k+1}$. This completes the proof of Theorem 9.

4.   Conclusions

In this paper, we establish the relationships between binding number and component factors of graphs, and derive some binding number conditions for graphs to be $(\mathcal{H}, m)$-factor deleted graphs or $(\mathcal{H}, n)$-factor critical graphs. Furthermore, we claim that the bounds on binding numbers in the results are best possible.

Acknowledgments

The authors would like to thank the anonymous reviewers for their kind comments and valuable suggestions. This work is supported by Six Talent Peaks Project in Jiangsu Province, China (Grant No. JY-022).

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.