Study on data transmission problem from the existence of Hamiltonian fractional factor

1. Introduction

Due to the similarity, the fractional factor problem is equivalent to a key problem in operation research, that is, the relaxation of the common cardinality matching problem. It is commonly used in a large variety of areas like scheduling, combinatorial polyhedron, and network designing. For instance, it is easy to find it in data transmission network. Some large data packets are transferred to a variety of terminals via certain channels to divide the large ones into small ones, which has been largely improved its efficiency. The possible allocations of data packets can be transferred into another problem: the problem of fractional flow. Hence, it is converted to fractional factor problem in a graph which is produced from a network.

To make it clear, if a graph models the complete network, it should make sure each site is corresponding to a vertex. Every individual channel is corresponding to an edge on it. Commonly, we select the shortest path between vertices to be the path of data transmission in a network. Nevertheless, the data transmission relies heavily on the network flow computation in the setting of software definition network. And the one that has the minimum transmission congestion currently is selected to be the transmission path. In this way, the model of data transmission problem can be converted to be the issue about how to make the fractional factor get rid of some fixed subgraphs.

All the graphs chosen here are only simple graphs. Let \(G=(V(G),E(G))\) be a graph, where \(E(G)\) is the edge set and \(V(G)\) is the vertex set. Then \(n=|V(G)|\) is the order of graph \(G\). The relevant terms appeared without clear definitions can be referred to Bondy and Murty [2].

In what follows, we describe the toughness \(t(G)\) of a graph \(G\): $$t(G)=\min\{\frac{|S|}{\omega(G-S)}|S\subseteq V(G),\omega(G-S)\ge2\},$$ from which, we get \(t(G)=+\infty\), when \(G\) is a non-complete. It serves as an important parameter to be used for the vulnerability of networks measurement.

Suppose that \(f\) and \(g\) are two positive integer-valued functions on \(V(G)\), we get \(0\le g(x)\le f(x)\) for any \(x\in V(G)\). Then, a fractional \((g,f)\)-factor can be denoted as a function \(h\) to map a number in [0,1] to every individual edge. As a result, \(g(x)\le d_{G}^{h}(x)\le f(x)\) for each \(x\in V(G)\), in which is the fractional degree of \(x\) in \(G\) is \(d_{G}^{h}(x)=\sum_{e\in E(x)}h(e)\). A fractional \((a,b)\)-factor with two positive integers: \(a\) and \(b\) and satisfying \(a\le b\) is a function \(h\) to assign a number [0,1] to every individual edge of a graph \(G\). For every vertex \(x\), we get \(a\le d_{G}^{h}(x)\le b\). Then, fractional \((a,b)\)-factor is one of fractional \((g,f)\)-factors on the foundation of \(g(x)=a\) and \(f(x)=b\) for any \(x\in V(G)\). On the condition of \(a=b=k\) for all \(x\in V(G)\) where \(k\ge1\) is an integer, a fractional \((a,b)\)-factor is seen as a fractional \(k\)-factor.

If there is a fractional \((g,f)\)-factor with a Hamiltonian cycle in \(G\), \(G\) includes a Hamiltonian fractional \((g,f)\)-factor. We can sum up that when any independent set of \(G\) is deleted, there exists an ID-Hamiltonian graph if the existing graph of \(G\) pre mitts a Hamiltonian cycle. On the other hand, \(G\) has an ID-Hamiltonian fractional \((g,f)\)-factor, if the existing graph of \(G\) contains a Hamiltonian fractional \((g,f)\)-factor if we delete any one independent set of \(G\).

In SDN applications, the independent set \(I\) is homologous with a website that is highly congested in transmission and a Hamiltonian cycle corresponds to some channels that is highly congested in transmission. After that, we take into account of the Hamiltonian fractional \((g,f)\)-factor and ID-Hamiltonian fractional \((g,f)\)-factor in the networks model to further study the data transmission.

Next, we complicatedly study how the sufficient conditions is like for Hamiltonian fractional \((g,f)\)-factors and ID-Hamiltonian fractional \((g,f)\)-factors in graphs. In a result, three results are gained and they are presented in the following which extend the previous results presented in Gao et al.[1].

Theorem 1. Suppose that \(b,a,\Delta\) are three integers meeting \(\Delta\ge0\), \(3\le a\le b\), and \(G\) is a Hamiltonian graph of order \(n>\frac{(a+b-5)(a+b-3)}{a+\Delta-2}\). \(g, f\) are assumed to be integer-valued functions on \(V(G)\) as well. Hence, \(a\le g(x)\le f(x)-\Delta\le b-\Delta\) for every \(x\in V(G)\). If $$\delta(G)\ge\frac{a+(b-1-\Delta)n+b-3}{a-3+b}$$ and $$\delta(G)>\frac{2\alpha(G)+(b-\Delta-2)n-1}{b+a-4},$$ so \(G\) possesses a Hamiltonian fractional \((g,f)\)-factor.

Theorem 2. Suppose that \(b,a,\Delta\) are integers meeting \(\Delta\ge0\), \(3\le a\le b\), and \(G\) is a Hamiltonian graph of order \(n\ge b+2\). \(f\),\(g\) are assumed to be integer-valued functions on \(V(G)\) as well. Hence, \(a\le g(x)\le f(x)-\Delta\le b-\Delta\) for every \(x\in V(G)\). If \(t(G)\ge b-1-\Delta+\frac{b-1-\Delta}{a+\Delta-2}\), then \(G\) possesses a Hamiltonian fractional \((g,f)\)-factor.

Theorem 3. \(b,a,\Delta\) are chosen to be three integers meeting \(\Delta\ge0\), \(3\le a\le b\), and \(G\) is an ID-Hamiltonian graph. And \(f,g\) are integer-valued functions on \(V(G)\). Hence, \(a\le g(x)\le f(x)-\Delta\le b-\Delta\) for every \(x\in V(G)\). If

and $$\kappa(G)\ge\frac{4(a-2+\Delta)+(b+1-\Delta)^{2}}{4(a-2+\Delta)}\alpha(G),$$ after that, \(G\) possesses the ID-Hamiltonian fractional \((g,f)\)-factor.

The tricks to demonstrate the main achievements are on the foundation of the lemmas in the following.

Lemma 4. (Liu and Zhang [3]) Assume that \(G\) is a graph and \(H=G[T]\) such that \(1\le d_{G}(x)\le k-1\) and \(\delta (H)\ge1\) for every \(x\in V(H)\) in which \(k\ge2\) and \(T\subseteq V(G)\). \(T_{1},\dots,T_{k-1}\) are assumed to be a partition of the vertices of \(H\) meeting \(d_{G}(x)=j\) for every \(x\in T_{j}\) in which there are several empty \(T_{j}\). On the basis that there is a vertex of degree at most \(k-2\) in \(G\) in \(H\)'s every component, \(H\) possesses a covering set \(C=V(H)-I\) and a largest independent set \(I\), therefore, $$\sum\limits_{j=1}^{k-1}(k-j)c_{j}\le \sum\limits_{j=1}^{k-1}(k-2)(k-j)i_{j},$$ in which \(c_{j}=|C\cap T_{j}|\) and \(i_{j}=|I\cap T_{j}|\) for \(j=1,\dots,k-1\).

Lemma 5. (Liu and Zhang [3]) Assume that \(G\) is a graph and \(H=G[T]\) so \(d_{G}(x)= k-1\) for each \(x\in V(H)\). There isn't component of \(H\) isomorphic to \(K_{k}\) in which \(k\ge2\) and \(T\subseteq V(G)\). After that, there is a covering set \(C=V(H)-I\) of \(H\) and an independent set \(I\) and meeting $$|V(H)|\le(k-\frac{1}{k+1})|I|$$ and $$|C|\le (k-\frac{1}{1+k}-1)|I|.$$

Lemma 6. (Anstee [4]) Suppose \(g\) and \(f\) are integer-valued functions on the vertex set of a graph \(G\) so for every \(x\in V(G)\), \(0\le g(x)\le f(x)\). If and only if for every subset \(S\) of \(V(G)\), \(g(T)-d_{G-S}(T)\le f(S)\), in which \(T=\{x\in V(G)-S|d_{G-S}(x)\le g(x)-1\}\), \(G\) has a fractional \((g,f)\)-factor .

Apparently, Lemma 6 equals to the lemmas below.

Lemma 7. Assume \(g\) and \(f\) be integer-valued functions on the vertex set of a graph \(G\) so \(0\le g(x)\le f(x)\) for every \(x\in V(G)\). \(G\) has a fractional \((g,f)\)-factor on the condition of $$f(S)+d_{G-S}(T)-g(T)\ge0$$ for the whole mutually disjoint subsets \(S, T\) of \(V(G)\).

Lemma 8. (Chvátal [5]) If \(G\) is a non-complete graph, \(t(G)\le\frac{1}{2}\delta(G)\).

Proof of the Main Results

In the following, we present the detailed proofs for three main conclusions.

Proof of Theorem 1.

Let \(G'=G-E(C)\). Concerning the definition of Hamiltonian graph and the condition of Theorem 1, \(G\) admits a Hamiltonian cycle \(C\). Obviously, \(G\) contains the expected fractional factor if \(H\) contains a fractional \((f-2,g-2)\)-factor. In view of contradiction, we presume that \(G'\) doesn't have fractional \((f-2,g-2)\)-factor. Thus, considering Lemma 7, several disjoint subset \(T\) and \(S\) of \(V(H)\) meeting The suitable subsets \(T\) and \(S\) with the smallest \(|T|\) are chosen.
On the condition of \(T=\emptyset\), using (2) we get \(-1\ge(\Delta+a-2)|S|\ge 0\), a contradiction. Thus, \(T\ne\emptyset\). Define \(h=\min\{d_{R-S}(x): x\in T\}\). We infer, Thus, we concern the facts below.

Claim 9. For any \(x\in T\), \(d_{G'-S}(x)\le b-3-\Delta\).

Proof. The subset \(T-\{x\}\) and \(S\) meets (2) as well, if \(d_{G¡ä-S}(x)\ge b-2-\Delta\) for some \(x\in T\). This is contradictory with \(T\).

Claim 10. \(d_{G-S}(x)\le d_{G'-S}(x)+2\le b-1-\Delta\) for any \(x\in T\).

Proof. We get from \(G'=G-E(C)\) and Claim 9, $$d_{G-S}(x)\le 2+d_{G'-S}(x)\le b-1-\Delta$$ for all \(x\in T\).

Taking the concepts of \(h\) and Claim 10 into consideration, we get \(0\le h\le b-1-\Delta\). In what follows, we present two cases on the value of \(h\).
Case 1. \(h=0\).
Set \(X=\{x\in T: d_{G-S}(x)=0\}\), \(Y_{1}=\{x\in Y: N_{G-S}(x)\subseteq T\}\) , \(Y=\{x\in T:d_{G-S}(x)=1\}\) and \(Y_{2}=Y-Y_{1}\). \(G[Y_{1}]\) has largest degree at most 1 in \(G-S\). Set \(Z\) as the largest independent set of \(G[Y_{1}]\). \(|Z|\ge\frac{1}{2}|Y_{1}|\) is yielded. \(X\cap Z\cap Y_{2}\) is an independent set of \(G\) on the basis of definitions. Therefore, we get Considering (2), (3), (4) and Claim 10, we deduce \begin{eqnarray*} \alpha(G)-1&\ge&|X|+\frac{1}{2}|Y|+(\Delta+a-2)|S|+d_{G'-S}(T)-(b-2-\Delta)|T|\\ &\ge&\frac{1}{2}|Y|+(\Delta+a-2)|S|+d_{G-S}(T)-2|T|+|X|-(b-2-\Delta)|T|\\ &=&\frac{1}{2}|Y|+(\Delta+a-2)|S|+d_{G-S}(T)+|X|-(b-\Delta)|T|\\ &=&\frac{1}{2}|Y|+(\Delta+a-2)|S|+d_{G-S}(T-X\cup Y)+|Y|+|X|-(b-\Delta)|T|\\ &=&(\Delta+a-2)|S|+\frac{3}{2}|Y|+d_{G-S}(T-X\cup Y)+|X|-(b-\Delta)|T|\\ &\ge&\frac{3}{2}|Y|+2|T-X\cup Y|+(\Delta+a-2)|S|+|X|-(b-\Delta)|T|\\ &=&(\Delta+a-2)|S|-(b-\Delta-2)|T|-(|X|+\frac{1}{2}|Y|)\\ &\ge&(\Delta+a-2)\delta(G)-\alpha(G)-(b-2-\Delta)|T|, \end{eqnarray*} i.e., As \(b\ge3\), \(|S|+|T|\le n\), (3) and(5), we obtain \begin{eqnarray*} 0&\le& n-|T|-|S|\le n-\frac{(\Delta+a-2)\delta(G)-2\alpha(G)+1}{b-2-\Delta}-\delta(G)\\ &=&\frac{2\alpha(G)-1-(a+b-4)\delta(G)+(b-\Delta-2)n}{b-\Delta-2}, \end{eqnarray*} that is $$\delta(G)\le\frac{2\alpha(G)+(b-2-\Delta)n-1}{b+a-4}.$$ Here it contradicts to \(\delta(G)>\frac{(b-\Delta-2)n+2\alpha(G)-1}{a+b-4}\).
Case 2. \(1\le h\le b-\Delta-1\).
As \(|S|+|T|\le n\) and (2), we deduce \begin{eqnarray*} -1&\ge&(a-2+\Delta)|S|+d_{G'-S}(T)-(b-2-\Delta)|T|\\ &\ge&(\Delta+a-2)|S|+d_{G-S}(T)-2|T|-(b-2-\Delta)|T|\\ &=&(\Delta+a-2)|S|+d_{G-S}(T)-(b-\Delta)|T|\\ &\ge&(\Delta+a-2)|S|+h|T|-(b-\Delta)|T|\\ &=&(\Delta+a-2)|S|-(b-h-\Delta)|T|\\ &\ge&(\Delta+a-2)|S|-(b-h-\Delta)(n-|S|)\\ &=&(b+a-h-2)|S|-(b-h-\Delta)n, \end{eqnarray*} Here it indicates Using (3) and (6), we deduce Subcase 2.1 \(h=1\).
Concerning (7), get $$\delta(G)\le\frac{(b-1-\Delta-1)n}{b+a-3}+1=\frac{b+a+(b-1-\Delta)n-4}{b+a-3},$$ it get conflict with \(\delta(G)\ge\frac{(b-\Delta-1)n+a+b-3}{a+b-3}\).
Subcase 2.2 \(2\le h\le b-1-\Delta\).
Set \(\Phi(h)=\frac{(b-\Delta-h)n-1}{a+b-h-2}+h\). As \(n>\frac{(b+a-5)(b+a-3)}{a-2+\Delta}\) as well, we get \begin{eqnarray*} \Phi'(h)&=1+&\frac{(b-\Delta-h)n-n(b+a-2-h)-1}{(b+a-2-h)^{2}}\\ &=&\frac{-(\Delta-2+a)n-1}{(b+a-h-2)^{2}}+1\le\frac{-(\Delta-2+a)n-1}{(b+a-4)^{2}}+1\\ &<&\frac{-(b-5+a)(b-3+a)-1}{(b-4+a)^{2}}+1=0. \end{eqnarray*} Hence, \(\max\{\Phi(h)\}=\Phi(2)\). Based on \(n>\frac{(b-5+a)(b-3+a)}{\Delta+a-2}\) and (7), we have $$\delta(G)\le \Phi(h)\le \Phi(2)=\frac{(b-2-\Delta)n-1}{b-4+a}+2< \frac{(b-1-\Delta)n+b+a-3}{b+a-3},$$ which has conflicts with \(\delta(G)\ge\frac{(b-\Delta-1)n+a+b-3}{b+a-3}\).
Based in the above discussion, it is summed up that \(G'\) possesses a fractional \((g-2,f-2)\)-factor. Therefore, we complete Theorem 1.

Proof of Theorem 2

\(G\) is taken as a non complete graph, as \(G\) holds a Hamiltonian fractional \((g,f)\)-factor by the order of graph when \(G\) is complete. Set \(G'=G-E(C)\). Concerning definition of Hamiltonian graph and the situation of Theorem 2, \(G\) admits a Hamiltonian cycle \(C\). Apparently, \(G\) contains the expected fractional factor if \(H\) contains a fractional \((g-2,f-2)\)-factor. Due to their mutual conflicts, it is assumed that there isn't any fractional \((g-2,f-2)\)-factor in \(G'\). By means of Lemma 6, several subsets \(S\) of \(V(G')\) meeting where \(T=\{x\in V(G')-S, d_{G'-S}(x)\le b-3-\Delta\}\). For every \(x\in T\), we obtain For (8) and (9), we get we get \(\delta(G)\ge 2t(G)\ge 2(b-\Delta-1)+\frac{2(b-1-\Delta)}{a-2+\Delta}>b-\Delta\) by Lemma 8, as \(G\) is a non complete graph. Therefore, we obtain \(|S|\ne1\) and \(S\ne\emptyset\) from (10).Set \(T_{0}=\{x\in V(H')| d_{G-S}(x)=0\}\). Suppose \(\lambda\) is the number of the components of \(H'=G[T]\) isomorphic to \(K_{b-\Delta}\). After deleting \(\lambda\) components isomorphic to \(K_{b-\Delta}\), we take \(H\) as the subgraph. If \(|V(H)|=0\), considering(10) we get $$(b-\Delta)(|T_{0}|+\lambda)>(a+\Delta-2)|S|$$ and $$2\le|S|< \frac{(b-\Delta)(|T_{0}|+\lambda)}{a+\Delta-2}.$$ Hence, we infer $$|T_{0}|+\lambda>\frac{2(\Delta-2+a)}{b-\Delta}.$$ If \(\omega(G-S)\ge|T_{0}|+\lambda>1\), we infer \begin{eqnarray*} t(G)&\le&\frac{|S|}{\omega(G-S)}\le\frac{|S|}{|T_{0}|+\lambda}<\frac{(b-\Delta)(|T_{0}|+\lambda)}{(a+\Delta-2)(|T_{0}|+\lambda)}=\frac{b-\Delta}{a+\Delta-2}\\ &\le&b-1-\Delta+\frac{b-1-\Delta}{a-2+\Delta}, \end{eqnarray*} which has conflicts with \(t(G)\ge b-1-\Delta+\frac{b-1-\Delta}{a+\Delta-2}\).
If \(|T_{0}|+\lambda=1\), then \(|S|+d_{G-S}(x)\ge d_{G}(x)\ge\delta(G)\ge2t(G)\ge2(b-1-\Delta)+\frac{2(b-1-\Delta)}{a-2+\Delta}\). We have \(d_{G-S}(x)\ge2(b-1-\Delta)+\frac{2(b-1-\Delta)}{a-2+\Delta}-|S|>2(b-1-\Delta)+\frac{2(b-1-\Delta)}{a-2+\Delta}-\frac{b-\Delta}{a-2+\Delta}\), which has conflicts with (9). Here, we work on \(|V(H)|\ge1\). Set \(H=H_{1}\cup H_{2}\) where \(H_{1}\) is the combined production of \(H\)'s elements that satisfy \(d_{G-S}(x)=b-1-\Delta\) for every vertex \(x\in V(H_{1})\) and \(H_{2}=H-H_{1}\). By means of Lemma 5, there is a largest independent set \(I_{1}\) and the covering set \(C_{1}=V(H_{1})-I_{1}\) of \(H_{1}\) such that and Set \(T_{j}=\{x\in V(H_{2})|d_{G-S}(x)=j\}\) for \(1\le j\le b-1-\Delta\). Clearly, \(\delta(H_{2})\ge1\) and \(\Delta(H_{2})\le b-\Delta-1\). Every element of \(H_{2}\) holds a vertex of degree. In \(G-S\), it is at its ultimate of \(b-2-\Delta\) from the concepts of \(H_{2}\) and \(H\). Based on Lemma 4, \(H_{2}\) holds the covering set \(C_{2}=V(H_{2})-I_{2}\) and the largest independent set \(I_{2}\), then where \(c_{j}=|C_{2}\cap T_{j}|\) and \(i_{j}=|I_{2}\cap T_{j}|\) for each \(j=1,\dots,b-\Delta-1\). Let \(W=V(G)-T-S\) and \(U=S\cup C_{1}\cup(N_{G}(I_{1})\cap W))\cup C_{2}\cup (N_{G}(I_{2})\cap W)\). We deduce and If \(\omega(G-U)>1\), we get If \(\omega(G-U)=1\), then (16) holds as well.
By (14), (15) and (16), we get By means of (10), we get As (17) and (18), we get Considering \(t(G)\ge b-1-\Delta+\frac{b-\Delta-1}{a+\Delta-2}\), we deduce \((a-2+\Delta)t(G)+\Delta\-b ge(a-2+\Delta)(b-1-\Delta)-1\ge1\). By (19), we infer By (11) and (12), we get $$(a-2+\Delta)|C_{1}|+|V(H_{1})|\le [(b-\Delta-\frac{1}{b-\Delta+1})+(a-2+\Delta)(b-1-\Delta-\frac{1}{b+1-\Delta})]|I_{1}|.$$ By (13) and (20), we get \begin{eqnarray*}\label{21} &\quad&\sum\limits_{j=1}^{b-1-\Delta}(b-j-\Delta)(b-2-\Delta)i_{j}+[(b-\frac{1}{b-\Delta+1}-\Delta)\\ &\quad&+(b-1-\Delta-\frac{1}{b+1-\Delta})(a-2+\Delta)]|I_{1}|\\ &>&\sum\limits_{j=1}^{b-1-\Delta}((a-2+\Delta)t(G) -b+j-(a-2+\Delta)j+\Delta)i_{j}+1+(a-2+\Delta)t(G)|I_{1}|. \end{eqnarray*} In result, one or two cases here turns out to be successful.
Case 1. \((a-2+\Delta)(b-\frac{1}{b-\Delta+1}-1-\Delta)+(b-\frac{1}{b-\Delta+1}-\Delta)>1+(a-2+\Delta)t(G)\).
We get \begin{eqnarray*} t(G)&<&b-1-\frac{1}{a-2+\Delta}-\Delta-\frac{1}{b-1+\Delta}+\frac{b-\Delta-\frac{1}{b-\Delta+1}}{a-2+\Delta}\\ &=&b-\Delta-1-\frac{1}{a+\Delta-2}+\frac{b-a-2\Delta+2}{(b-\Delta+1)(a+\Delta-2)}+\frac{(b-\Delta)^{2}-1}{(b-\Delta+1)(a-2+\Delta)}\\ &<&b+\frac{(b-\Delta)^{2}-1}{(b-\Delta+1)(a+\Delta-2)}-1-\Delta=b+\frac{b-1-\Delta}{a+\Delta-2}-1-\Delta, \end{eqnarray*} which has conflicts with \(t(G)\ge b+\frac{b-\Delta-1}{a+\Delta-2}-1-\Delta\).
Case 2. At least one \(j\) exists, so $$(b-j-\Delta)(b-2-\Delta)>(a-2+\Delta)t(G)+j+\Delta-b-(a-2+\Delta)j.$$ It implies As \(j\le b-1-\Delta\), referring to (21), we get $$b+(b-1-\Delta)(a-2+\Delta)-1-\Delta>(a-2+\Delta)t(G).$$ It reveals $$t(G)< b+\frac{b-1-\Delta}{a-2+\Delta}-1-\Delta,$$ which contradicts to \(t(G)\ge b+\frac{b-1-\Delta}{a-2+\Delta}-1-\Delta\).

Proof of Theorem 3

Considering the assumption of Theorem 3,for all independent sets \(X\) in \(G\), \(G-X\) allows a Hamiltonian cycle \(C\) to exist. \(R=G-X\) for any independent set \(X\subseteq V(G)\). Taking into account of the concept of ID-Hamiltonian graph and the assumption, there is a Hamiltonian cycle \(C\) in \(R\). Let \(H=R-E(C)\). Thus, on the condition that $H$ possesses a fractional \((g-2,f-2)\)-factor, \(G\) allows the expected fractional factor. As summed up, there isn't any fractional \((g-2,f-2)\)-factor in H. There are several subsets \(S\) of \(V(H)=V(R)\) meeting in which \(T=\{x\in V(H)-S,d_{H-S}(x)\le b-3-\Delta\}\).
If \(T=\emptyset\), by (22) we get $$-1\ge(a-2+\Delta)|S|\ge0,$$ a contradiction. Hence, \(T\ne\emptyset\).
\(x_{1}\) is the vertex having the least degree in \(R[T]\) if we take \(x_{1}\in T\). Let \(T_{1}=T\) and \(N_{1}=N_{R}[x_{1}]\cap T\). For \(i\ge2\), if \(T-\cup_{1\le j< i}N_{j}\ne\emptyset\), we continue set \(T_{i}=T-\cup_{1\le j< i}N_{j}\). In what follows, \(x_{i}\) is the vertex having the least degree in \(R[T_{i}]\) if we take \(x_{i}\in T_{i}\). Let \(N_{i}=N_{R}[x_{i}]\cap T_{i}\). We go on the processes until \(T_{i}=\emptyset\) for several \(i\), for \(i=m+1\). In light of the concept mentioned, \(\{x_{1}, x_{2},\cdots,x_{m}\}\) is an independent set of \(R\). Obviously, \(T\ne\emptyset\) and \(m\ge1\). Set \(|N_{i}|=n_{i}\), \(|T|=\sum_{1\le i\le m}n_{i}\). Suppose \(U=V(R)-(S\cup T)\), \(\kappa(R-S)=t\).

Claim 11. \(d_{R-S}(x)\le 2+d_{H-S}(x)\le b-1-\Delta\) for any \(x\in T\).

Proof. Concerning \(T\) and \(H=R-E(C)\), we get $$d_{R-S}(x)\le 2+d_{H-S}(x)\le b-1-\Delta=2+(b-3-\Delta)$$ for any \(x\in T\).

Claim 12. \(\alpha(G)\le\kappa(G)-\frac{(b+a+1)(b+a-3)}{4(a-2+\Delta)}\).

Proof. If \(\alpha(G)< \frac{(b+a+1)(b+a-3)}{(b+1-\Delta)^{2}}\), then considering (1), we get \begin{eqnarray*} \kappa(G)&\ge&\frac{(a-3+b)(a+1+b)}{(b+1-\Delta)^{2}}+\frac{(a-3+b)(a+1+b)}{4(a-2+\Delta)}\\ &>&\alpha(G)+\frac{(a-3+b)(a+1+b)}{4(a-2+\Delta)}. \end{eqnarray*} If \(\alpha(G)\ge\frac{(a-3+b)(a+1+b)}{(b+1-\Delta)^{2}}\), then by \(\kappa(G)\ge\frac{4(a-2+\Delta)+(b+1-\Delta)^{2}}{4(a-2+\Delta)}\alpha(G)\), we get \begin{eqnarray*} \kappa(G)&\ge&\frac{(b+1-\Delta)^{2}+4(a+\Delta-2)}{4(a+\Delta-2)}\alpha(G)=\alpha(G)+\frac{(b+1-\Delta)^{2}}{4(a-2+\Delta)}\alpha(G)\\ &\ge&\alpha(G)+\frac{(b+1-\Delta)^{2}}{4(a-2+\Delta)}\frac{)(a-3+b)(a+1+b}{(b+1-\Delta)^{2}}\\ &=&\alpha(G)+\frac{(a-3+b)(a+1+b)}{4(a-2+\Delta)}. \end{eqnarray*} Here, we succeed in the proof of Claim 12.

Claim 13. \(U\ne\emptyset\) or \(m\ne1\).

Proof. Take \(m=1\), \(U=\emptyset\). Concerning (22), Claim 11 and \(x_{1}\), we yield \begin{eqnarray*} -1&\ge&(a-2+\Delta)|S|+d_{H-S}(T)-(b-2-\Delta)|T|\\ &\ge&(a-2+\Delta)|S|+d_{R-S}(T)-(b--2\Delta)|T|-2|T|\\ &=&(a-2+\Delta)|S|+d_{R-S}(T)-(b-\Delta)|T|\\ &=&(a-2+\Delta)|S|+n_{1}(n_{1}-1)-(b-\Delta)n_{1}, \end{eqnarray*} which means

For (23), Claim 12, \(R=G-X\) and \(|X|\le\alpha(G)\), we get \begin{eqnarray*} |V(G)|&=&|R(R)|+|X|=|T|+|S|+|X|=n_{1}+|S|+|X|\\ &\le&\frac{-n_{1}^{2}+(b-\Delta+1)n_{1}-1}{a+\Delta-2}+n_{1}+\alpha(G)\\ &=&\frac{-n_{1}^{2}+(a-1+b)n_{1}-1}{a+\Delta-2}+\alpha(G)\le\alpha(G)+\frac{(a-1+b)^{2}-4}{4(a-2+\Delta)}\\ &\le&\alpha(G)+\frac{(a-1+b)(a-3+b)}{4(a-2+\Delta)}\le\kappa(G), \end{eqnarray*} which has conflicts with \(|V(G)|>\kappa(G)\). Claim 13 is successful.

Claim 14. \(d_{R-S}(T)\ge\sum_{1\le i\le m}n_{i}(n_{i}-1)+\frac{mt}{2}\).

The proof of Claim 14 is the same as proof of Claim 3.4 in Gao et al. [1], and we skip here. By \(|T|=\sum_{1\le i\le m}n_{i}\), (22), Claim 11 and Claim 14, we have \begin{eqnarray*} -1&\ge&d_{H-S}(T)+(a-2+\Delta)|S|-(b-2-\Delta)|T|\\ &\ge&d_{R-S}(T)+(a-2+\Delta)|S|-2|T|-(b-2-\Delta)|T|\\ &=&d_{R-S}(T)+(a-2+\Delta)|S|-(b-\Delta)|T|\\ &\ge&\sum_{1\le i\le m}n_{i}(n_{i}-1)+(a-2+\Delta)|S|+\frac{mt}{2}-(b-\Delta)\sum_{1\le i\le m}n_{i}\\ &=&\sum_{1\le i\le m}(n_{i}^{2}-(b+1-\Delta)n_{i})+(a-2+\Delta)|S|+\frac{mt}{2}, \end{eqnarray*} i.e., Let \(\Phi(n_{i})=n_{i}^{2}-(b-\Delta+1)n_{i}\). It is easy to say that \(\min\{\Phi(n_{i})\}=-\frac{(b-\Delta+1)^{2}}{4}\). Hence, we infer According to (24) and (25), we deduce

Claim 15. \(-\frac{(b-\Delta+1)^{2}}{4}+\frac{t}{2}< 0\).

Proof. Let \(-\frac{(b-\Delta+1)^{2}}{4}+\frac{t}{2}\ge0\). By (26), \(m\ge1\), \(|S|\ge0\), we obtain $$-1\ge(a-2+\Delta)|S|+\frac{mt}{2}-\frac{(b+1-\Delta)^{2}m}{4}\ge0,$$ a contradiction. We accomplished 15.

Note \(\{x_{1},x_{2},\cdots,x_{m}\}\) is one independent set of \(R\). We obtain By \(R=G-X\) and (27), we get \(R=G-X\) and \(\kappa(R-S)=t\). Apparently, In light of (26), (28), (29), \(|X|\le\alpha(G)\), Claim 15, \(\kappa(G)\ge \frac{4(a-2+\Delta)+(b-\Delta+1)^{2}}{2}\), and \(\kappa(G)\ge\frac{4(a-2+\Delta)+(b+1-\Delta)^{2}}{4(a-2+\Delta)}\alpha(G)\), we get \begin{eqnarray*} -1&\ge&\frac{mt}{2}+(a-2+\Delta)|S|-\frac{(b+1-\Delta)^{2}m}{4}\\ &=&(a+\Delta-2)|S|+(-\frac{(b-\Delta+1)^{2}}{4}+\frac{t}{2})m\\ &\ge&(-\frac{(b+1-\Delta)^{2}}{4}+\frac{t}{2})\alpha(G)+(a-2+\Delta)(\kappa(G)-|X|-t)\\ &\ge&(a-2+\Delta)(\kappa(G)-\alpha(G)-t)+(-\frac{(b+1-\Delta)^{2}}{4}+\frac{t}{2})\alpha(G)\\ &\ge&(\kappa(G)-\frac{4(a+\Delta-2)\kappa(G)}{(b+1-\Delta)^{2}+4(a+\Delta-2)}-t)(a-2+\Delta)\\ &\quad&+(-\frac{(b+1-\Delta)^{2}}{4}+\frac{t}{2})\frac{4(a-2+\Delta)\kappa(G)}{4(a-2+\Delta)+(b+1-\Delta)^{2}}\\ &=&(a-2+\Delta)t(\frac{2\kappa(G)}{(b+1-\Delta)^{2}+4(a-2+\Delta)})-1\ge0, \end{eqnarray*} a contradiction. In result, the proof of Theorem 3 is accomplished.

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Competing Interests

The author(s) do not have any competing interests in the manuscript.