Independent set conditions for all fractional ( g,f,n ′,m )-critical deleted NFV networks

Abstract

Network function virtualization (NFV) can be regarded as the latest trick development in the provisioning of network service. Software programs are running on virtual machines and industry standard servers to replace the traditional hardware middleboxes, and thus lead to flexibility, service agility and cost decreasing. A basic problem in NFV service chain provisioning is the ability of resource scheduling which equals to the existence of fractional factor. The concept of all fractional (g, f, n′, m)-critical deleted graph is the extension of fractional (g, f, n′, m)-critical deleted graph. In this paper, we consider the resource scheduling problem in NFV networks using graph theory, and an independent set degree condition and an independent set neighborhood union condition for all fractional (g, f, n′, m)-critical deleted graphs are determined. Furthermore, we show that the result are tight on independent set condition.

Keywords

NFV network resource scheduling all fractional factor independent set degree condition independent set neighborhood union condition

1 Introduction

The construction of a service chain for a new network in the traditional way needs configuring and buying particular hardware devices, and physically cabling them into a specific sequence. The spending of constructing and maintaining such hardware system can be high, and the corresponding hardware solution is always over-provisioned which account for a waste of hardware resources in non-peak hours.

Network function virtualization (NFV), a paradigm shift improved by engineering users exemplified by Vodafone, China Mobile and AT&T, purposes to deal with the above problems in view of simplifying and speeding up the advancement of network services. The European Telecommunications Standards Institute (ETSI) published a series of white papers on NFV in 2012, including the use cases, challenges and opportunities, industry progresses and architectural modeling. The virtual network functions (VNFs) can be instantiated according to the requirements without the demand of new devices installation. It enables network operators to upgrade, construct and delete service chains in an inexpensive and flexible way.

One of the basic problem in NFV service chain provisioning is the ability of resource scheduling which equals to the existence of fractional factor. It inspires us to discuss the theoretical problem using graph theory.

Let G = (V (G), E (G)) be a graph with vertex set V (G) and edge set E (G) which corresponds to cite set and channel set in the NFV network respectively. For any x ∈ V (G), we use d_G (x) and N_G (x) to denote the degree and the neighborhood of x in G, respectively. Set N_G [x] = N_G (x) ∪ {x}, G [S] as the subgraph induced by S, and G - S = G [V (G) \ S]. For two subsets S, T ⊂ V (G) with S ∩ T = ∅, set e_G (S, T) = | {e = xy|x ∈ S, y ∈ T} |. Denote δ (G) = min {d_G (x) : x ∈ V (G)}. More notations and terminologies appeared but not defined clearly in our article can refer to Bondy and Mutry [1].

Assume that g and f are two non-negative integer-valued functions on V (G) with g (x) ≤ f (x) for any x ∈ V (G). A fractional (g, f)-factor is considered as a real number function h which assigns to each edge in a graph G a real number in [0,1] satisfying g (x) ≤ ∑_e∈E(x)h (e) ≤ f (x) for each vertex x. If g (x) = a and f (x) = b for any x ∈ V (G), then a fractional (g, f)-factor is called a fractional [a, b]-factor, and it will be reduced to a fractional k-factor if g (x) = f (x) = k (here k ≥ 1 is an integer) for any vertex x. In the whole paper, we always assume that n is the order of G, i.e., the number of vertices in graph G.

We say that G has all fractional (g, f)-factors if G has a fractional p-factor for any p : V (G) → N satisfying g (x) ≤ p (x) ≤ f (x) for all x ∈ V (G). If g (x) = a, f (x) = b for each x ∈ V (G) and G has all fractional (g, f)-factors, then G has all fractional [a, b]-factors.

A graph G is called an all fractional (g, f, m)-deleted graph if after deleting any m edges, the rest graph still has all fractional (g, f)-factors. A graph G is called an all fractional (g, f, n′)-critical graph if after deleting any n′ vertices, the rest graph still has all fractional (g, f)-factors. Gao et al. [18] combined these two concepts all fractional (g, f, m)-deleted graph and all fractional (g, f, m)-critical graph together. A graph G is called an all fractional (g, f, n′, m)-critical deleted graph if after deleting any n′ vertices of G the remaining graph of G is still an all fractional (g, f, m)-deleted graph. An all fractional (g, f, n′, m)-critical deleted graph is an all fractional (a, b, n′, m)-critical deleted graph if g (x) = a, f (x) = b for any vertex x.

All fractional (g, f, n′, m)-critical deleted graph reflects the feasibility of effective use of resources in resource scheduling network. More conclusions on the topic with fractional factor, fractional deleted graphs, fractional critical and other engineering applications can refer to Gao and Gao [3], Gao and Wang [5 –8], Gao et al. [9 –13], Gao [14], Maldonado et al. [15], Ansari [16] and Fouda et al. [17].

In this paper, we study the relationship between independent set restriction in graph and the sufficient condition for all fractional (g, f, n′, m)-critical deleted graphs. Our main results to be proved in the next section can be stated as follows.

Theorem 1.Let G be a graph of order n, and let a, b, n′, m, and i be non-negative integers such that i ≥ 2, 1 ≤ a ≤ b, $n > \frac{(a + b) (2 m + ib - 2)}{a} + n^{'}$ and $δ (G) \geq \frac{b^{2} (i - 1)}{a} + 2 m + n^{'}$ . Let g, f be two integer-valued functions defined on V (G) such that a ≤ g (x) ≤ f (x) ≤ b for each x ∈ V (G). If G satisfies $max {d_{G} (x_{1}), d_{G} (x_{2}), \dots, d_{G} (x_{i})} \geq \frac{bn + {an}^{'}}{a + b}$ for any independent subset {x₁, x₂, …, x_i} of V (G), then G is an all fractional (g, f, n′, m)-critical deleted graph.

Set n′ = 0 in Theorem 1, then the following becomes necessary for independent set degree condition on all fractional (g, f, m)-deleted graphs.

Corollary 1.Let G be a graph of order n, and let a, b, m, and i be non-negative integers such that i ≥ 2, 1 ≤ a ≤ b, $n > \frac{(a + b) (2 m + ib - 2)}{a}$ and $δ (G) \geq \frac{b^{2} (i - 1)}{a} + 2 m$ . Let g, f be two integer-valued functions defined on V (G) such that a ≤ g (x) ≤ f (x) ≤ b for each x ∈ V (G). If G satisfies $max {d_{G} (x_{1}), d_{G} (x_{2}), \dots, d_{G} (x_{i})} \geq \frac{bn}{a + b}$ for any independent subset {x₁, x₂, …, x_i} of V (G), then G is an all fractional (g, f, m)-deleted graph.

Set m = 0 in Theorem 1, then we deduce the following corollary on the independent set degree condition of all fractional (g, f, n′)-critical graphs.

Corollary 2.Let G be a graph of order n, and let a, b, n′, and i be non-negative integers such that i ≥ 2, 1 ≤ a ≤ b, $n > \frac{(a + b) (ib - 2)}{a} + n^{'}$ and $δ (G) \geq \frac{b^{2} (i - 1)}{a} + n^{'}$ . Let g, f be two integer-valued functions defined on V (G) such that a ≤ g (x) ≤ f (x) ≤ b for each x ∈ V (G). If G satisfies $max {d_{G} (x_{1}), d_{G} (x_{2}), \dots, d_{G} (x_{i})} \geq \frac{bn + {an}^{'}}{a + b}$ for any independent subset {x₁, x₂, …, x_i} of V (G), then G is an all fractional (g, f, n′)-critical graph.

Theorem 2.Let G be a graph of order n. Let a, b, n′, m be four integers with i ≥ 2, 1 ≤ a ≤ b and n′, m ≥ 0. Let g, f be two integer-valued functions defined on V (G) such that a ≤ g (x) ≤ f (x) ≤ b for each x ∈ V (G). If $δ (G) \geq \frac{b^{2} (i - 1)}{a} + 2 m + n^{'}$ , $n > \frac{(a + b) (i (a + b) + 2 m - 2)}{a} + n^{'}$ , and $| N_{G} (x_{1}) \cup N_{G} (x_{2}) \cup \dots \cup N_{G} (x_{i}) | \geq \frac{bn + {an}^{'}}{a + b}$ for any independent subset {x₁, x₂, …, x_i} of V (G), then G is an all fractional (g, f, n′, m)-critical deleted graph.

Set n′ = 0 in Theorem 2, we infer the independent set neighborhood union condition for all fractional (g, f, m)-deleted graphs.

Corollary 3.Let G be a graph of order n. Let a, b, i be four integers with i ≥ 2, 1 ≤ a ≤ b and m ≥ 0. Let g, f be two integer-valued functions defined on V (G) such that a ≤ g (x) ≤ f (x) ≤ b for each x ∈ V (G). If $δ (G) \geq \frac{b^{2} (i - 1)}{a} + 2 m$ , $n > \frac{(a + b) (i (a + b) + 2 m - 2)}{a}$ , and $| N_{G} (x_{1}) \cup N_{G} (x_{2}) \cup \dots \cup N_{G} (x_{i}) | \geq \frac{bn}{a + b}$ for any independent subset {x₁, x₂, …, x_i} of V (G), then G is an all fractional (g, f, m)-deleted graph.

Set m = 0, then Theorem 2 becomes the independent set neighborhood union condition for a graph to be all fractional (g, f, n′)-critical.

Corollary 4.Let G be a graph of order n. Let a, b, n′ be four integers with i ≥ 2, 1 ≤ a ≤ b and n′ ≥ 0. Let g, f be two integer-valued functions defined on V (G) such that a ≤ g (x) ≤ f (x) ≤ b for each x ∈ V (G). If $δ (G) \geq \frac{b^{2} (i - 1)}{a} + n^{'}$ , $n > \frac{(a + b) (i (a + b) - 2)}{a} + n^{'}$ , and $| N_{G} (x_{1}) \cup N_{G} (x_{2}) \cup \dots \cup N_{G} (x_{i}) | \geq \frac{bn + {an}^{'}}{a + b}$ for any independent subset {x₁, x₂, …, x_i} of V (G), then G is an all fractional (g, f, n′)-critical graph.

The proof of our main results is based on the following lemma which is the necessary and sufficient condition of all fractional (g, f, n′, m)-critical deleted graphs.

Lemma 1. (Gao et al. [18]) Let a, b, m and n′ be nonnegative integers with 1 ≤ a ≤ b, and let G be a graph of order n with n ≥ b + n′ + m + 1. Let g, f : V (G) → Z⁺ be two valued functions with a ≤ g (x) ≤ f (x) ≤ b for each x ∈ V (G), and H be a subgraph of G with m edges. Then G is all fractional (g, f, n′, m)-critical deleted if and only if

$\begin{matrix} g (S) - f (T) + \sum_{x \in T} d_{G - S} (x) \\ \geq & max_{U \subseteq S, | U | = n^{'}, H \subseteq E (G - U), | H | = m} {g (U) \\ + \sum_{x \in T} d_{H} (x) - e_{H} (S, T)}, \end{matrix}$ (1) for any non-disjoint subsets S, T ⊆ V (G) with |S| ≥ n′.

2 Proof of Main Results

In this section, we present the proof of the main results in our paper.

2.1 Proof of Theorem 1

Suppose that G satisfies the conditions of Theorem 1 but is not an all fractional (g, f, n′, m)-critical deleted graph. Obviously, T≠ ∅. Otherwise, (1) establishes. In terms of Lemma 1 and the fact ∑_x∈Td_H (x) - e_H (T, S) ≤2m, there exist disjoint subsets S, T ⊆ V (G) such that

$\begin{matrix} a | S | - b | T | + \sum_{x \in T} d_{G - S} (x) - 2 m - {an}^{'} \\ \leq & a (| S | - n^{'}) + \sum_{x \in T} (d_{G - S} (x) - d_{H} (x) \\ + e_{H} (x, S) - b) \\ \leq & g (S - U) + \sum_{x \in T} (d_{G - S} (x) - d_{H} (x) \\ + e_{H} (x, S) - f (x)) \leq - 1 . \end{matrix}$ (2) We select S and T with minimum |T|. If there exists x ∈ T satisfying d_G-S (x) ≥ g (x), then the subsets S and T \ {x} satisfy (2) as well. This contradicts the selection criterion of S and T. It implies that d_G-S (x) ≤ g (x) -1 ≤ b - 1 for any x ∈ T.

Let d₁ = min {d_G-S (x) |x ∈ T} and choose x₁ ∈ T such that d_G-S (x₁) = d₁. If z ≥ 2 and $T \ (\cup_{j = 1}^{z - 1} N_{T} [x_{j}]) \neq \emptyset$ , let $d_{z} = min {d_{G - S} (x) | x \in T \ (\cup_{j = 1}^{z - 1} N_{T} [x_{j}])}$ and select $x_{z} \in T \ (\cup_{j = 1}^{z - 1} N_{T} [x_{j}])$ such that d_G-S (x_z) = d_z. So, we get a sequence such that 0 ≤ d₁ ≤ d₂ ≤ ⋯ ≤ d_π ≤ g (x) -1 ≤ b - 1 and an independent set {x₁, x₂, …, x_π} ⊆ T. Claim 1. |T| ≥ b (i - 1) +1.

Proof. Assume that |T| ≤ b (i - 1). Then $| S | + d_{1} \geq d_{G} (x_{1}) \geq δ (G) \geq \frac{b^{2} (i - 1)}{a} + 2 m + n^{'}$ . By (2) and 0 ≤ d₁ ≤ b - 1, we infer $\begin{matrix} 2 m + {an}^{'} - 1 \\ \geq & a | S | + d_{1} | T | - b | T | \\ = & | T | (d_{1} - b) + a | S | \\ \geq & (\frac{b^{2} (i - 1)}{a} - d_{1} \\ + 2 m + n^{'}) a + (i - 1) (d_{1} - b) b \\ = & (b (i - 1) - a) d_{1} + b^{2} (i - 1) - b^{2} (i - 1) \\ + {an}^{'} + 2 ma \\ \geq & 2 m + {an}^{'} . \end{matrix}$ This produces a contradiction.

Since |T| ≥ b (i - 1) +1 and d_G-S (x) ≤ b - 1, we deduce π ≥ i. Therefore, an independent set {x₁, x₂, …, x_i} ⊆ T is existed.

In view of the condition of the theorem, we get $\frac{bn + {an}^{'}}{a + b} \leq max {d_{1}, d_{2}, \dots, d_{i}} \leq | S | + d_{i}$ and thus $| S | \geq \frac{bn + {an}^{'}}{a + b} - d_{i} .$ (3)

In light of $| N_{T} [x_{j}] | - | N_{T} [x_{j}] \cap (\cup_{z = 1}^{j - 1} N_{T} [x_{z}]) | \geq 1,$ $j = 2, 3, \dots, i - 1$ and $\begin{matrix} | \cup_{z = 1}^{j} N_{T} [x_{z}] | & \leq & \sum_{z = 1}^{j} | N_{T} [x_{z}] | \\ \leq \sum_{z = 1}^{j} (d_{G - S} (x_{z}) + 1) \\ = & \sum_{z = 1}^{j} (d_{z} + 1), j = 1, 2, \dots, i, \end{matrix}$ we deduce $\begin{matrix} 2 m + {an}^{'} - 1 \\ \geq & a | S | - b | T | + | N_{T} [x_{1}] | d_{1} + (| N_{T} [x_{2}] | \\ - | N_{T} [x_{1}] \cap N_{T} [x_{2}] |) d_{2} + (| N_{T} [x_{i - 1}] | \\ - | (\cup_{j = 1}^{i - 2} N_{T} [x_{j}]) \cap N_{T} [x_{i - 1}] |) d_{i - 1} \\ + \dots + (| T | - | \cup_{j = 1}^{i - 1} N_{T} [x_{j}]) | |) d_{i} \\ \geq & a | S | + | T | (d_{i} - b) + | N_{T} [x_{1}] | (d_{1} - d_{i}) \\ + \sum_{j = 2}^{i - 1} d_{j} - d_{i} \sum_{j = 2}^{i - 1} | N_{T} [x_{j}] | \\ = & a | S | + | T | (d_{i} - b) + (d_{1} + 1) (d_{1} - d_{i}) \\ + \sum_{j = 2}^{i - 1} d_{j} - d_{i} \sum_{j = 2}^{i - 1} (d_{j} + 1) \\ = & a | S | + | T | (d_{i} - b) + d_{1}^{2} \\ + \sum_{j = 1}^{i - 1} d_{j} - d_{i} \sum_{j = 1}^{i - 1} (d_{j} + 1) . \end{matrix}$ It implies $\begin{matrix} (b - d_{i}) (n - | S | - | T |) \\ \geq & a | S | + | T | (d_{i} - b) + \sum_{j = 1}^{i - 1} d_{j} \\ + d_{1}^{2} - d_{i} \sum_{j = 1}^{i - 1} (d_{j} + 1) - 2 m - {an}^{'} + 1 . \end{matrix}$ Equivalently,

$\begin{matrix} 0 & \leq & (b - d_{i}) n - | S | (a + b - d_{i}) \\ + d_{i} \sum_{j = 1}^{i - 1} d_{j} + (i - 1) d_{i} \\ - \sum_{j = 1}^{i - 1} d_{j} - d_{1}^{2} + 2 m + {an}^{'} - 1 . \end{matrix}$ (4) By means of (3), (4), d₁ ≤ d₂ ≤ ⋯ ≤ d_i ≤ b - 1 and $n > \frac{(2 m + ib - 2) (a + b)}{a} + n^{'}$ , we infer $\begin{matrix} 0 \leq n (b - d_{i}) + d_{i} \sum_{j = 1}^{i - 1} d_{j} \\ - (\frac{b n + a n^{'}}{a + b} - d_{i}) (a + b - d_{i}) \\ - \sum_{j = 1}^{i - 1} d_{j} + d_{i} (i - 1) - d_{1}^{2} + 2 m + a n^{'} - 1 \\ = d_{i} \sum_{j = 1}^{i - 1} d_{j} + d_{i} (a + b) - \frac{a n}{a + b} d_{i} - \sum_{j = 1}^{i - 1} d_{j} \\ + d_{i} (i - 1) - d_{1}^{2} - d_{i}^{2} + \frac{a d_{i}}{a + b} n^{'} + 2 m - 1 \\ = (d_{i} d_{1} - d_{1}^{2} - d_{1}) - \frac{a n}{a + b} d_{i} + (d_{i} - 1) \sum_{j = 2}^{i - 1} d_{j} \\ + \frac{a d_{i}}{a + b} n^{'} + d_{i} (a + b + i - 1) + 2 m - d_{i}^{2} - 1 \\ \leq (d_{i} \frac{d_{i} - 1}{2} - {(\frac{d_{i} - 1}{2})}^{2} - \frac{d_{i} - 1}{2}) \\ - d_{i} \frac{a n}{a + b} + (d_{i} - 1) \sum_{j = 2}^{i - 1} d_{i} \\ + \frac{a d_{i}}{a + b} n^{'} + (a + b + i - 1) d_{i} + 2 m - d_{i}^{2} - 1 \\ = (a + b + \frac{1}{2}) d_{i} + d_{i}^{2} (i - \frac{11}{4}) + \frac{a d_{i}}{a + b} n^{'} + \frac{1}{4} \\ + 2 m - \frac{a n}{a + b} d_{i} - 1 \\ < (a + b + \frac{1}{2}) d_{i} + d_{i}^{2} (i - \frac{11}{4}) + 2 m \\ - d_{i} (i b + 2 m - 2) - \frac{3}{4} \\ = d_{i} (a + b + \frac{5}{2} - i b) + (i - \frac{11}{4}) d_{i}^{2} \\ + 2 (1 - d_{i}) m - \frac{3}{4} . \end{matrix}$ Now, we consider the following two cases:

Case 1. If d_i > 0, then by 2 (1 - d_i) m ≤ 0, we infer $0 < (a + b + \frac{5}{2} - ib) d_{i} + d_{i}^{2} (i - \frac{11}{4}) - \frac{3}{4} .$ (5) Set $h (d_{i}) = (a + b + \frac{5}{2} - ib) d_{i} + d_{i}^{2} (i - \frac{11}{4}) - \frac{3}{4} .$ (6) • If $i \leq \frac{11}{4}$ , then i must equal to 2. Thus, $h (d_{i}) = (a - b + \frac{5}{2}) d_{i} - d_{i}^{2} \frac{3}{4} - \frac{3}{4} .$ If $b \geq \frac{5}{2} + a$ , clearly h (d_i) <0. If b = a + 2, then $h (d_{i}) = \frac{d_{i}}{2} - \frac{3 d_{i}^{2}}{4} - \frac{3}{4} < 0$ . If b = a + 1, then $h (d_{i}) = \frac{3}{2} d_{i} - \frac{3}{4} d_{i}^{2} - \frac{3}{4}$ and max {h (d_i)} = d (1) =0. If a = b = k, then $n > \frac{(a + b) (ib + 2 m - 2)}{a} + n^{'}$ can be rewritten as n ≥ 4k + 4m + n′ - 3. In terms of Theorem 7 in Gao and Yan [19] (it determined that G is a fractional (k, n′, m)-critical deleted graph if n ≥ 4k + n′ + 4m - 3, δ (G) ≥ k + n′ + m and $max {d (u), d (v)} \geq \frac{n + n^{'}}{2}$ for each pair of non-adjacent vertices u and v of G, where k ≥ 2, m, n′ ≥ 0), we ensure that G is a fractional (k, n′, m)-critical deleted graph unless a = b = 1. If a = b = 1, then d₂ = 0 by d_i ≤ k - 1, but it is contradictory with the assumption that d_i > 0. • If $i > \frac{11}{4}$ (it means i ≥ 3 since i is an integer), then max {h (d_i)} = max {h (0), h (b - 1)}. Since $h (0) = - \frac{3}{4} < 0$ and (if b - 1 ≠0, then b ≥ 2) $\begin{matrix} h (b - 1) \\ = (a + b - i b + \frac{5}{2}) (b - 1) + (b - 1)^{2} (i - \frac{11}{4}) - \frac{3}{4} \\ = (a - i - \frac{7}{4} b + \frac{21}{4}) (b - 1) - \frac{3}{4} . \end{matrix}$ If b ≥ 3, then h (b - 1) <0 by b ≥ a and $a - i - \frac{7}{4} b + \frac{21}{4} \leq 0$ . If b = 2, then using i ≥ 3, we yield $(b - 1) h = (a - i - \frac{7}{4} b + \frac{21}{4}) (b - 1) - \frac{3}{4} \leq 0$ . If a = b = 1, then $(b - 1) h = - \frac{3}{4} < 0$ . Therefore, we conclude that max {h (d_i)} ≤0 in the case $i > \frac{11}{4}$ .

Case 2. If d_i = 0, then d₁ = ⋯ = d_i = 0. In terms of (1.3), we obtain $| S | \geq \frac{bn + {an}^{'}}{a + b}$ and $| T | \leq n - | S | \leq \frac{an - {an}^{'}}{a + b}$ . Since d_G-S (T) ≥ ∑_x∈Td_H (x) - e_H (T, S), we yield $\begin{matrix} g (S - U) + d_{G - S} (T) - f (T) \\ - (\sum_{x \in T} d_{H} (x) - e_{H} (T, S)) \\ \geq & a \cdot (\frac{bn + {an}^{'}}{a + b} - n^{'}) - b \cdot \frac{an - {an}^{'}}{a + b} \\ + (d_{G - S} (T) - \sum_{x \in T} d_{H} (x) + e_{H} (T, S)) \\ \geq & 0, \end{matrix}$ is also a contradiction. This completes the proof of the theorem.

2.2 Proof of Theorem 2

Suppose that G satisfies the conditions of Theorem 2 but is not an all fractional (g, f, n′, m)-critical deleted graph. Clearly, T≠ ∅. Otherwise, (1) establishes. In terms of Lemma 1 and the fact ∑_x∈Td_H (x) - e_H (T, S) ≤2m, there exist disjoint subsets S, T ⊆ V (G) satisfying

$\begin{matrix} a | S | - b | T | + \sum_{x \in T} d_{G - S} (x) - 2 m - {an}^{'} \\ \leq & g (S - U) + \sum_{x \in T} (d_{G - S} (x) - d_{H} (x) \\ + e_{H} (x, S) - f (x)) \leq - 1 . \end{matrix}$ (7) We select S and T with minimum |T|. Hence, as discussed in the proof of Theorem 1, we infer d_G-S (x) ≤ g (x) -1 ≤ b - 1 for any x ∈ T.

Let d₁ = min {d_G-S (x) |x ∈ T} and select x₁ ∈ T with d_G-S (x₁) = d₁. If z ≥ 2 and $T \ (\cup_{j = 1}^{z - 1} N_{T} [x_{j}]) \neq \emptyset$ , let $d_{z} = min {d_{G - S} (x) | x \in T \ (\cup_{j = 1}^{z - 1} N_{T} [x_{j}])}$ and select $x_{z} \in T \ (\cup_{j = 1}^{z - 1} N_{T} [x_{j}])$ with d_G-S (x_z) = d_z. Thus, it generates a sequence with 0 ≤ d₁ ≤ d₂ ≤ ⋯ ≤ d_π ≤ g (x) -1 ≤ b - 1 and an independent set {x₁, x₂, …, x_π} ⊆ T.

As discussed in Claim ?? in last subsection, we have |T| ≥ b (i - 1) +1. Hence, π ≥ i, and we can select an independent set {x₁, x₂, …, x_i} ⊆ T.

In light of independent set neighborhood union condition described in the theorem, we infer $\begin{matrix} \frac{bn + {an}^{'}}{a + b} & \leq & | N_{G} (x_{1}) \cup N_{G} (x_{2}) \cup \dots \cup N_{G} (x_{i}) | \\ \leq & | S | + \sum_{j = 1}^{i} d_{j} \end{matrix}$ and $| S | \geq \frac{bn + {an}^{'}}{a + b} - \sum_{j = 1}^{i} d_{j} .$ (8)

Since $| N_{T} [x_{j}] | - | N_{T} [x_{j}] \cap (\cup_{z = 1}^{j - 1} N_{T} [x_{z}]) | \geq 1,$ $j = 2, 3, \dots, i - 1$ and $\begin{matrix} | \cup_{z = 1}^{j} N_{T} [x_{z}] | \leq \sum_{z = 1}^{j} | N_{T} [x_{z}] | \\ \leq & \sum_{z = 1}^{j} (d_{G - S} (x_{z}) + 1) = \sum_{z = 1}^{j} (d_{z} + 1), \\ j = 1, 2, \dots, i, \end{matrix}$ we deduce $\begin{matrix} 2 m + {an}^{'} - 1 \\ \geq & a | S | - b | T | + | N_{T} [x_{1}] | d_{1} + (| N_{T} [x_{2}] | \\ - | N_{T} [x_{1}] \cap N_{T} [x_{2}] |) d_{2} + \dots + (| N_{T} [x_{i - 1}] | \\ - | (\cup_{j = 1}^{i - 2} N_{T} [x_{j}]) \cap N_{T} [x_{i - 1}] |) d_{i - 1} \\ + (| T | - | \cup_{j = 1}^{i - 1} N_{T} [x_{j}]) |) d_{i} \\ \geq & a | S | + | T | (d_{i} - b) + \sum_{j = 2}^{i - 1} d_{j} \\ + | N_{T} [x_{1}] | (d_{1} - d_{i}) - d_{i} \sum_{j = 2}^{i - 1} | N_{T} [x_{j}] | \\ = & a | S | + (d_{1} + 1) (d_{1} - d_{i}) + \sum_{j = 2}^{i - 1} d_{j} \\ + | T | (d_{i} - b) - d_{i} \sum_{j = 2}^{i - 1} (d_{j} + 1) \\ = & a | S | + | T | (d_{i} - b) + \sum_{j = 1}^{i - 1} d_{j} + d_{1}^{2} \\ - d_{i} \sum_{j = 1}^{i - 1} (d_{j} + 1), \end{matrix}$ which implies $\begin{matrix} (b - d_{i}) (n - | S | - | T |) \\ \geq & a | S | + \sum_{j = 1}^{i - 1} d_{j} + | T | (d_{i} - b) + d_{1}^{2} \\ - d_{i} \sum_{j = 1}^{i - 1} (d_{j} + 1) - 2 m - {an}^{'} + 1 . \end{matrix}$ Equivalently,

$\begin{matrix} 0 & \leq & (b - d_{i}) n + d_{i} \sum_{j = 1}^{i - 1} d_{j} - | S | (a + b - d_{i}) \\ - \sum_{j = 1}^{i - 1} d_{j} + d_{i} (i - 1) - d_{1}^{2} \\ + 2 m + {an}^{'} - 1 . \end{matrix}$ (9) By means of (8), (9), d₁ ≤ d₂ ≤ ⋯ ≤ d_i ≤ b - 1 and $n > \frac{(i (a + b) + 2 m - 2) (a + b)}{a} + n^{'}$ , we have $\begin{matrix} 0 \leq (b - d_{i}) n - (\frac{b n + a n^{'}}{a + b} - \sum_{j = 1}^{i} d_{j}) (a + b - d_{i}) \\ + d_{i} \sum_{j = 1}^{i - 1} d_{j} - \sum_{j = 1}^{i - 1} d_{j} \\ + d_{i} (i - 1) - d_{1}^{2} + 2 m + a n^{'} - 1 \\ = - \frac{a n}{a + b} d_{i} + (a + b) \sum_{j = 1}^{i} d_{j} - d_{i} \sum_{j = 1}^{i} d_{j} \\ + d_{i} \sum_{j = 1}^{i - 1} d_{j} - \sum_{j = 1}^{i - 1} d_{j} \\ + (i - 1) d_{i} + \frac{a n^{'}}{a + b} d_{i} - d_{1}^{2} + 2 m - 1 \\ = - d_{i} \frac{a n}{a + b} + (d_{1} (a + b - 1) - d_{1}^{2}) \\ + (a + b - 1) \sum_{j = 2}^{i - 1} d_{j} + (a + b + i - 1) d_{i} \\ + \frac{a n^{'}}{a + b} d_{i} - d_{i}^{2} + 2 m - 1 \\ \leq - d_{i} \frac{a n}{a + b} + d_{i} (a + b - 1) + (a + b - 1) \sum_{j = 2}^{i - 1} d_{i} \\ + (a + b + i - 1) d_{i} + d_{i} \frac{a n^{'}}{a + b} - d_{i}^{2} + 2 m - 1 \\ = i d_{i} (a + b) - d_{i} \frac{a n}{a + b} + \frac{a n^{'}}{a + b} d_{i} - d_{i}^{2} + 2 m - 1. \end{matrix}$ If d_i > 0, then $0 < {id}_{i} (a + b) - d_{i} \frac{an}{a + b} + \frac{{an}^{'}}{a + b} d_{i} - d_{i}^{2} + 2 m - 1 \leq 0$ since $n > \frac{(i (a + b) + 2 m - 2) (a + b)}{a} + n^{'}$ and 2 (1 - d_i) m ≤ 0, a contradiction.

If d_i = 0, then d₁ = ⋯ = d_i = 0. In view of (2), we deduce $| S | \geq \frac{bn + {an}^{'}}{a + b}$ and $| T | \leq n - | S | \leq \frac{an - {an}^{'}}{a + b}$ . By virtue of d_G-S (T) ≥ ∑_x∈Td_H (x) - e_H (T, S), we yield $\begin{matrix} g (S) + d_{G - S} (T) - f (T) - {an}^{'} \\ - (\sum_{x \in T} d_{H} (x) - e_{H} (T, S)) \\ \geq a \cdot \frac{bn + {an}^{'}}{a + b} - b \cdot \frac{an - {an}^{'}}{a + b} - {an}^{'} \\ + (d_{G - S} (T) - \sum_{x \in T} d_{H} (x) + e_{H} (T, S)) \\ \geq 0, \end{matrix}$ is also a contradiction.

Therefore, the desired theorem is proved.

3 Sharpness

Theorem 1 and Theorem 2 are best possible, to some extent, under the condition. Actually, we can construct some graphs such that the independent set degree condition in Theorem 1 can’t be replaced by $max {d_{G} (x_{1}), d_{G} (x_{2}), \dots, d_{G} (x_{i})} \geq \frac{bn + {an}^{'}}{a + b} - 1$ and the independent set neighborhood union condition in Theorem 2 can’t be replaced by $| N_{G} (x_{1}) \cup N_{G} (x_{2}) \cup \dots \cup N_{G} (x_{i}) | \geq \frac{bn + {an}^{'}}{a + b} - 1$ .

Let G₁ = K_bt+n′ be a complete graph, G₂ = (at + 1) K₁ be a graph consisting of at + 1 isolated vertices, and G = G₁ ∨ G₂, where t is sufficiently large and n′ is sufficiently small. Then n = |G₁| + |G₂| = t (a + b) + n′ + 1, and for any independent set {x₁, x₂, …, x_i} ⊆ V (G₂), we have $\begin{matrix} \frac{b n + a n^{'}}{a + b} > \max {d_{G} (x_{1}), d_{G} (x_{2}), \dots, d_{G} (x_{i})} \\ = b t + n^{'} > \frac{b n + a n^{'}}{a + b} - 1, \end{matrix}$ and $\begin{matrix} \frac{bn + {an}^{'}}{a + b} > | N_{G} (x_{1}) \cup N_{G} (x_{2}) \cup \dots \cup N_{G} (x_{i}) | \\ = bt + n^{'} > \frac{bn + {an}^{'}}{a + b} - 1 . \end{matrix}$ Let S = V (G₁), and g (x) = f (x) = a for any x ∈ V (G₁); T = V (G₂), and g (x) = f (x) = b for any x ∈ V (G₂). Then $\begin{matrix} g (S) - f (T) + d_{G - S} (T) \\ - \max_{U \subseteq S, | U | = n^{'}, H \subseteq E (G - U), | H | = m} {g (U) \\ + \sum_{x \in T} d_{H} (x) - e_{H} (T, S)} \\ = a | S - U | - b | T | = a (b t) - b (a t + 1) = - b < 0. \end{matrix}$ Hence, G is not an all fractional (g, f, n′, m)-critical deleted graph.

Conflict of Interests

The authors hereby declare that there is no conflict of interests regarding the publication of this paper.

Footnotes

Acknowledgments

We thank the reviewers for their constructive comments in improving the quality of this paper.

References

Bondy

J.A.

, Mutry

U.S.R.

, Graph Theory, Springer, Berlin, 2008.

H.L.

, Simplified existence theorems on all fractional [a, b]-factors, Discrete Applied Mathematics161 (2013), 2075–2078.

Gao

and Gao

, Toughness condition for a graph to be a fractional (g, f, n)-critical deleted graph, The Scientific World Journal2014, 7. Article ID 369798. 10.1155/2014-369798.

Zhou

S.Z.

and Sun

Z.R.

, On all fractional (a, b, k)-critical graphs, Acta Mathematica Sinica30(4) (2014) 696–702.

Gao

and Wang

W.F.

, New isolated toughness condition for fractional (g, f, n)-critical graphs, Colloquium Mathematicum147 (2017), 55–66.

Gao

and Wang

W.F.

, A tight neighborhood union condition on fractional (g, f, n’, m)-critical deleted graphs, Colloquium Mathematicum147 (2017), 291–298.

Gao

and Wang

W.F.

, Toughness and fractional critical deleted graph, Utilitas Mathematica98 (2015), 295–310.

Gao

and Wang

W.F.

, A neighborhood union condition for fractional (k, m)-deleted graphs, Ars Combinatoria113 (2014), 225–233.

Gao

, Guirao

J.L.G.

and Wu

H.L.

, Two tight independent set conditions for fractional (g, f, m)-deleted graphs systems, Qualitative Theory of Dynamical SystemsDOI: 10.1007/s12346-016-0222-z.

10.

Gao

, Liang

, Xu

T.W.

and Zhou

J.X.

, Degree conditions for fractional (g, f, n’, m)-critical deleted graphs and fractional ID-(g, f, m)-deleted graphs, Bulletin of the Malaysian Mathematical Sciences Society39 (2016), 315–330.

11.

Gao

, Liang

, Xu

T.W.

and Zhou

J.X.

, Tight toughness condition for fractional (g, f, n)-critical graphs, Journal of the Korean Mathematical Society51 (2014), 55–65.

12.

Gao

and Wang

W.F.

, The eccentric connectivity polynomial of two classes of nanotubes, Chaos, Solitons and Fractals89 (2016), 290–294.

13.

Gao

, Liang

and Chen

Y.H.

, An isolated toughness condition for graphs to be fractional (k, m)-deleted graphs, Utilitas Mathematica105 (2017), 303–316.

14.

Gao

, A sufficient condition for a graph to be fractional (a, b, n)-critical deleted graph, Ars Combinatoria119 (2015), 377–390.

15.

Maldonado

, Prada

and Senosiain

M.J.

, On linear operators and bases on Kothe spaces, Applied Mathematics and Nonlinear Sciences1(2) (2016), 617–624.

16.

Ansari

A.A.

, Investigation of the effect of albedo and oblateness on the circular restricted four variable body problem, Applied Mathematics and Nonlinear Sciences2(2) (2017), 529–542.

17.

Fouda

D.A.

, Hamdy

, Nouh

, Beheary

, Bakrey

and Saad

S.M.

, Model atmosphere analysis of two new early-type O4 dwarfs stars, Applied Mathematics and Nonlinear Sciences2(2) (2017), 559–564.

18.

Gao

, Zhang

Y.Q.

and Chen

Y.J.

, Neighborhood condition for all fractional (g, f, n’, m)-critical deleted graphs, Open Physics, In press.

19.

Gao

and Yan

C.C.

, A note on fractional (g, f, n’, m)-critical deleted graph, Advances in Computational Mathematics and its Applications1 (2012), 53–55.