Feasibility analysis of data transmission in SDN

Abstract

In the setting of software definition network (SDN), whether there exists an available transmission plan between any two sites is equal to whether there exists a fractional factor after deleting certain vertices and edges in the corresponding graph. A graph G is called a fractional ID-(a, b, m)-deleted graph if after deleting any independent-set I, the remaining graph G - I is a fractional (a, b, m)-deleted graph. A fractional (g, f)-factor F of a graph G is called a Hamiltonian fractional (g, f)-factor if F includes a Hamiltonian cycle. Furthermore, we say that G has a ID-Hamiltonian fractional (g, f)-factor if after deleting any independent set of G the remaining graph of G includes a Hamiltonian fractional (g, f)-factor. In this paper, we first give a binding number condition for a graph to be a fractional ID-(a, b, m)-deleted graph, and then two sufficient conditions for graphs to have ID-Hamiltonian fractional (g, f)-factors are obtained.

Keywords

Fractional factor software definition network binding number

1 Introduction

The problem of fractional factor can be considered as a relaxation of the well-known cardinality matching problem. It has wide-ranging applications in areas such as scheduling, network design and the combinatorial polyhedron. For instance, several large data packets are sent to various destinations through several channels in a communication network. The efficiency of this work can be improved if large data packets are partitioned into small parcels. The feasible assignment of data packets can be seen as a fractional flow problem and it becomes a fractional factor problem when the destinations and sources of a network are disjointed.

The whole network can be regarded as a graph. Each site corresponds to a vertex and each channel corresponds to an edge in the graph. In normal network, the data transmission is based on the selection of shortest path between vertices. However, in software definition network, the data transmission relies on the computation of network flow. It choices the path with minimum transmission congestion in the present moment. From this point of view, the model of data transmission problem in SDN is just the existence of fractional factor in the corresponding graph.

All graphs considered in this paper are finite, loopless, and without multiple edges. Let G be a graph with the vertex set V (G) and the edge set E (G). Let n = |V (G) |. For a vertex x ∈ V (G), the degree and the neighborhood of x in G are denoted by d_G (x) and N_G (x), respectively. Let Δ (G) and δ (G) denote the maximum degree and the minimum degree of G, respectively. For S ⊆ V (G), we denote by G [S] the subgraph of G induced by S, and letG - S = G [V (G) ∖ S]. For two disjointed subsets S and T of V (G), we use e_G (S, T) to denote the number of edges with one end in S and the other in T. The binding number bind(G) of a graph G is defined as follows: $\begin{matrix} bind (G) & = & min {\frac{| N_{G} (X) |}{| X |} | \emptyset \neq X \subseteq V (G), \\ N_{G} (X) \neq V (G)} . \end{matrix}$

It is an important parameter which is used to measure the vulnerability of networks.

Let g and f be two positive integer-valued functions on V (G) such that 0 ≤ g (x) ≤ f (x) for any x ∈ V (G). A fractional (g, f)-factor is a function h which assigns a number in [0,1] to each edge so that $g (x) \leq d_{G}^{h} (x) \leq f (x)$ for each x ∈ V (G), where $d_{G}^{h} (x) = \sum_{e \in E (x)} h (e)$ is called the fractional degree of x in G. A fractional (a, b)-factor (here a and b are both positive integers and a ≤ b) is a function h that assigns to each edge of a graph G a number in [0,1] so that for each vertex x we have $a \leq d_{G}^{h} (x) \leq b$ . Clearly, fractional (a, b)-factor is a special case of fractional (g, f)-factor when g (x) = a and f (x) = b for any x ∈ V (G). If a = b = k (k ≥ 1 is an integer) for all x ∈ V (G), then a fractional (a, b)-factor is just a fractional k-factor.

A graph G is called a fractional (a, b, m)-deleted graph if for each edge subset H ⊆ E (G) with |H| = m, there exists a fractional (a, b)-factor h such that h (e) =0 for all e ∈ H. That is, after removing any m edges, the resulting graph still has a fractional (a, b)-factor.

A graph is called fractional independent-set-deletable (a, b, m)-deleted graph (in short, fractional ID-(a, b, m)-deleted graph) if G - I is a fractional (a, b, m)-deleted graph for every independent set I of G. If a = b = k, then a fractional ID-(a, b, m)-deleted graph is a fractional ID-(k, m)-deleted graph. If m = 0, then a fractional ID-(a, b, m)-deleted graph is just a fractional ID-(a, b)-factor-criticalgraph.

We say that G includes a Hamiltonian fractional (g, f)-factor if G has a fractional (g, f)-factor containing a Hamiltonian cycle. A graph G is said to be an ID-Hamiltonian graph if after deleting any independent set of G the remaining graph of G admits a Hamiltonian cycle. We say that G has an ID-Hamiltonian fractional (g, f)-factor if after deleting any independent set of G the remaining graph of G includes a Hamiltonian fractional (g, f)-factor.

In SDN, the independent set I is corresponding to the website with high transmission congestion and m edges corresponding to several channels with high transmission congestion. Thus, we study the data transmission problem via considering the ID-(a, b, m)-deleted graph and ID-Hamiltonian fractional (g, f)-factor in the networks model.

Zhou [1] gave the binding number condition for a graph to be a fractional (k, m)-deletedgraph.

Theorem 1. (Zhou [1]) Let k ≥ 2 and m ≥ 0 be two integers, and let G be a graph of order n with $n \geq 4 k - 6 + \frac{2 m}{k - 1}$ . If $bind (G) > \frac{(2 k - 1) (n - 1)}{k (n - 2) - 2 m + 2},$ then G is a fractional (k, m)-deleted graph.

Zhou [2] studied the relationship between binding number and the fractional ID-k-factor-critical graph and proved the following theorem.

Theorem 2. (Zhou [2]) Let k be an integer with k ≥ 2, and let G be a graph of order p with p ≥ 6k - 9. If $bind (G) > \frac{(3 k - 1) (p - 1)}{kp - 2 k + 2}$ , then G is fractional ID-k-factor-critical.

More related results can refer to [3 –8].

In this paper, we first generalize the fractionalID-k-factor-critical graph to the fractionalID-(a, b, m)-deleted graph and obtain a binding number condition for a graph to be fractional ID-(a, b, m)-deleted.

Theorem 3. Let a, b, r and m be four integers such that 2 ≤ a ≤ b - r, r ≥ 0, and m ≥ 0. Let G be a graph of order n such that $n \geq \frac{(a + b - 3) (2 a + b + r) + 1 + 2 m}{a + r}$ . If $bind (G) > \frac{(2 a + b + r - 1) (n - 1)}{(a + r) n - (a + b - 2) - 2 m}$ , then G is fractional ID-(a, b, m)-deleted.

We obtain the following corollary by setting r = 0 in Theorem 3.

Corollary 1. Let a, b and m be two integers with 2 ≤ a ≤ b and m ≥ 0. Let G be a graph of order n with $n \geq \frac{(a + b - 3) (2 a + b) + 1 + 2 m}{a}$ . If $bind (G) > \frac{(2 a + b - 1) (n - 1)}{an - (a + b - 2) - 2 m}$ , then G is fractional ID-(a, b, m)-deleted.

We yield the following corollary by setting m = 0 in Theorem 3.

Corollary 2. Let a, b and r be three integers such that 2 ≤ a ≤ b - r and r ≥ 0, and let G be a graph of order n, where $n \geq \frac{(a + b - 3) (2 a + b + r) + 1}{a + r}$ . If $bind (G) > \frac{(2 a + b + r - 1) (n - 1)}{(a + r) n - (a + b - 2)}$ , then G is fractional ID-(a, b)-factor-critical.

We obtain the following corollary by setting r = 0 in Corollary 2.

Corollary 3. Let a and b be two integers with 2 ≤ a ≤ b, and let G be a graph of order n, where $n \geq \frac{(a + b - 3) (2 a + b) + 1}{a}$ . If $bind (G) > \frac{(2 a + b - 1) (n - 1)}{an - (a + b - 2)}$ , then G is fractional ID-(a, b)-factor-critical.

Secondly, we investigate ID-Hamiltonian fractional (g, f)-factors in graphs and obtain the following two results.

Theorem 4. Let G be a graph of order n, and a, b be two integers with 2 ≤ a ≤ b. 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 $n \geq \frac{(a + b - 4) (b + 2 a - 4) + 1}{a - 2}$ (if a ≠ 2) and $δ (G) \geq \frac{(a + b - 2) n}{b + 2 a - 4}$ , then G has a ID-Hamiltonian fractional (g, f)-factor.

Theorem 5.Let a, b be two integers with 2 ≤ a ≤ b, and G be an ID-Hamiltonian graph of order $n \geq \frac{(a + b - 5) (b + 2 a - 4) + 1}{a - 2}$ . 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 $| N_{G} (X) | \geq \frac{(a + b - 3) n + \frac{b + 2 a - 5}{a + b - 3} | X | - a + 1}{b + 2 a - 5}$ for every non-empty independent subset X of V (G), and $δ (G) > \frac{(a + b - 3) n + a + b - 4}{b + 2 a - 5},$ then G has a ID-Hamiltonian fractional (g, f)-factor.

The proof of our main results is based on the following lemmas:

Lemma 1. (Gao [9]) Let G be a graph, a, b be two non-negative integers such that a ≤ b. Then G is fractional (a, b, m)-deleted if and only if

$\begin{matrix} b | S | - a | T | + d_{G - S} (T) \\ \geq max_{H \subseteq E (G), | H | = m} {\sum_{x \in T} d_{H} (x) - e_{H} (T, S)} \end{matrix}$ (1) for all disjoint subsets S, T of V (G).

Lemma 2. (Woodall [10]) Let c be a positive real, and let G be a graph of order n with bind (G) > c. Then $δ (G) \geq n - \frac{n - 1}{bind (G)} > n - \frac{n - 1}{c}$ .

Lemma 3. (Anstee [11]) Suppose that f and g are two integer-valued functions defined on the vertex set of a graph G such that 0 ≤ g (x) ≤ f (x) for each x ∈ V (G). Then G has a fractional (g, f)-factor if and only if for every subset S of V (G), g (T) - d_G-S (T) ≤ f (S),where T = {x ∈ V (G) ∖ S | d_G-S (x) ≤ g (x) -1}.

Clearly, Lemma 3 is equal to the following version.

Lemma 4. Suppose that f and g are two integer-valued functions defined on the vertex set of a graph G such that 0 ≤ g (x) ≤ f (x) for each x ∈ V (G). Then G has a fractional (g, f)-factor if and only if $f (S) + d_{G - S} (T) - g (T) \geq 0$ for all disjoint subsets S, T of V (G).

2 Proof of Theorem 3

Let X be an independent set of G and H = G - X. To prove Theorem 3, we only need to verify that H admits is fractional (a, b, m)-deleted. Suppose that H is not fractional (a, b, m)-deleted. Then from Lemma 1 and the fact that ∑_x∈Td_H (x) - e_H (T, S) ≤2m, there exists certain disjointed subsets S, T of V (H) satisfying $b | S | + d_{H - S} (T) - a | T | - 2 m \leq - 1 .$ (2)

We denote that bind (G) = λ. In terms of Lemma 2 and the assumption in Theorem 3, we infer

$\begin{matrix} δ (G) & \geq & n - \frac{n - 1}{λ} \\ > & \frac{(a + b - 1) n + a + b + 2 m - 2}{2 a + b + r - 1} . \end{matrix}$ (3)

Assume that T =∅. By virtue of (2), we have -1 ≥ b|S|≥0, a contradiction. Thus, we verify that T≠ ∅. In what follows, we set d = min {d_H-S (x) : x ∈ T}. We now determine the following claims.

Claim 1. |S| ≥ δ (G) - |X| - d.

Proof. We select x₁ ∈ T such that d_H-S (x₁) = d. Then, we deduce

$\begin{matrix} δ (G) & \leq & d_{G} (x_{1}) \\ \leq & d_{G - X - S} (x_{1}) + | X | + | S | \\ = & d_{H - S} (x_{1}) + | X | + | S | \\ = & d + | X | + | S |, \end{matrix}$ (4) which reveals $| S | \geq δ (G) - | X | - d .$

Therefore, Claim 1 is established. □

Claim 2. |X| ≤ n - δ (G).

Proof. It is not hard to check that d_G (x) ≥ δ (G) for any x ∈ V (G). Thus, d_G (x) ≥ δ (G) for any x ∈ X. Since X is an independent set of G, we get $n \geq d_{G} (x) + | X | \geq δ (G) + | X |$ for each x ∈ X, and thus $| X | \leq n - δ (G) .$

The proof of Claim 2 is now completed. □

We discuss the following two cases according to the value of d.

Case 1.d = 0.

In this situation, we first prove the below claim.

Claim 3.λ ≤ a + b + 2m - 1.

Proof. If λ > a + b - 1 +2m. Then, by virtue of (3) and 2 ≤ a ≤ b - r, we obtain $\begin{matrix} δ (G) & \geq & n - \frac{n - 1}{λ} = n - \frac{n}{λ} + \frac{1}{λ} > n - \frac{n}{λ} \\ > & n - \frac{n}{a + b - 1 + 2 m} = \frac{(a + b - 2 + 2 m) n}{a + b - 1 + 2 m} \\ \geq & \frac{(a + b) n + 2 m}{2 a + b + r} . \end{matrix}$

The last step is established since $\begin{matrix} (a + b - 2 + 2 m) n (2 a + b + r) \\ - (a + b - 1 + 2 m) ((a + b) n + 2 m) \\ = n [(a + b - 2 + 2 m) (2 a + b + r) \\ - (a + b - 1 + 2 m) (a + b)] \\ - 2 m (a + b - 1 + 2 m) \\ = n [(a + b) (a + r - 1) + (2 m - 2) (a + r)] \\ - 2 m (a + b - 1 + 2 m) \\ \geq (a + b) (a + r - 1) \\ \frac{(a + b - 3) (2 a + b + r) + 1 + 2 m}{a + r} \\ + (2 m - 2) (a + r) \\ \frac{(a + b - 3) (2 a + b + r) + 1 + 2 m}{a + r} \\ - 2 m (a + b - 1 + 2 m) \\ = (a + b) ((a + b - 3) (2 a + b + r) + 1 + 2 m) \\ - \frac{((a + b - 3) (2 a + b + r) + 1 + 2 m) (a + b)}{a + r} \\ + (2 m - 2) ((a + b - 3) (2 a + b + r) + 1 + 2 m) \\ - 2 m (a + b - 1 + 2 m) . \end{matrix}$

Set $\begin{matrix} f (m) \\ = (a + b) ((a + b - 3) (2 a + b + r) + 1 + 2 m) \\ - \frac{((a + b - 3) (2 a + b + r) + 1 + 2 m) (a + b)}{a + r} \\ + (2 m - 2) ((a + b - 3) (2 a + b + r) + 1 + 2 m) \\ - 2 m (a + b - 1 + 2 m) . \end{matrix}$

We deduce that $\begin{matrix} 0 < f^{'} (m) = 2 (a + b) - \frac{2 (a + b)}{b + r} \\ + 2 [(a + b - 3) (2 a + b + r) - (a + b - 1) - 2] . \end{matrix}$

Thus, $\begin{matrix} (a + b - 2 + 2 m) n (2 a + b + r) \\ - (a + b - 1 + 2 m) ((a + b) n + 2 m) \\ \geq (a + b) ((a + b - 3) (2 a + b + r) + 1) \\ - \frac{((a + b - 3) (2 a + b + r) + 1) (a + b)}{a + r} \\ - 2 ((a + b - 3) (2 a + b + r) + 1) \\ = (a + b - 2) ((a + b - 3) (2 a + b + r) + 1) \\ - \frac{((a + b - 3) (2 a + b + r) + 1) (a + b)}{a + r} \\ = ((a + b - 3) (2 a + b + r) + 1) \\ \cdot [(a + b - 2) - \frac{a + b}{a + r}] \\ = ((a + b - 3) (2 a + b + r) + 1) \\ \cdot [(a + b) (1 - \frac{1}{b + r}) - 2] \\ \geq ((a + b - 3) (2 a + b + r) + 1) \\ \cdot [(a + b) (1 - \frac{1}{2 + 0}) - 2] \\ = ((a + b - 3) (2 a + b + r) + 1) [\frac{a + b}{2} - 2] \\ \geq 0 . \end{matrix}$

Combining this with (2), n ≥ |X| + |S| + |T|, Claim 1, and Claim 2, we deduce $\begin{matrix} - 1 & \geq & b | S | + d_{H - S} (T) - a | T | - 2 m \\ \geq & (a + r) | S | - (b - r) | T | - 2 m \\ \geq & (a + r) | S | - (b - r) (n - | X | - | S |) - 2 m \\ = & (a + b) | S | - (b - r) n + (b - r) | X | - 2 m \\ \geq & (a + b) (δ (G) - | X |) - (b - r) n \\ + (b - r) | X | - 2 m \\ = & (a + b) δ (G) - (b - r) n - (a + r) | X | - 2 m \\ \geq & (a + b) δ (G) - (b - r) n \\ - (a + r) (n - δ (G)) - 2 m \\ = & (2 a + b + r) δ (G) - (a + b) n - 2 m > 0, \end{matrix}$ a contradiction. Hence, the Claim 3 holds. □

Let Y = {x : x ∈ T, d_H-S (x) =0}. Since Y≠ ∅, N_G (V (G)\ (X ∪ S)) ∩ Y = ∅ and |N_G (V (G) \ (X ∪ S)) | ≤ n - |Y|, we have, $\begin{matrix} bind (G) & = & λ \leq \frac{| N_{G} (V (G) \ (X \cup S)) |}{| V (G) \ (X \cup S) |} \\ \leq & \frac{n - | Y |}{n - | X | - | S |}, \end{matrix}$ i.e., $| S | \geq (1 - \frac{1}{λ}) n - | X | + \frac{1}{λ} | Y | .$ (5)

In terms of (2), (3), (5), Claim 2, Claim 3 and |X| + |S| + |T| ≤ n, we get $\begin{matrix} - 1 & \geq & (a + r) | S | + | T | - | Y | - (b - r) | T | - 2 m \\ = & (a + r) | S | - (b - r - 1) | T | - | Y | - 2 m \\ \geq & (a + r) | S | - (b - r - 1) (n - | X | - | S |) \\ - | Y | - 2 m \\ = & (a + b - 1) | S | - (b - r - 1) n \\ + (b - r - 1) | X | - | Y | - 2 m \\ \geq & (a + b - 1) ((1 - \frac{1}{λ}) n - | X | + \frac{1}{λ} | Y |) - 2 m \\ - (b - r - 1) n + (b - r - 1) | X | - | Y | \\ = & (a + r) n - \frac{(a + b - 1) n}{λ} - (a + r) | X | \\ + (\frac{a + b - 1}{λ} - 1) | Y | - 2 m \\ \geq & (a + r) n - \frac{(a + b - 1) n}{λ} - (a + r) | X | \\ + (\frac{a + b - 1}{λ} - 1) | Y | - 2 m \\ \geq & (a + r) n - \frac{(a + b - 1) n}{λ} \\ - (a + r) (n - δ (G)) + \frac{a + b - 1}{λ} - 1 - 2 m \\ = & - \frac{(a + b - 1) n}{λ} + (a + r) δ (G) \\ + \frac{a + b - 1}{λ} - 1 - 2 m \\ \geq & - \frac{(a + b - 1) n}{λ} + (a + r) (n - \frac{n - 1}{λ}) \\ + \frac{a + b - 1}{λ} - (a + b - 1) - 2 m \\ = & - \frac{(2 a + b + r - 1) (n - 1)}{λ} + (a + r) n \\ - (a + b - 1) - 2 m, \end{matrix}$ which implies $λ \leq \frac{(2 a + b + r - 1) (n - 1)}{(a + r) n - (a + b - 2) - 2 m},$ which contradicts the assumption of Theorem 3.

Case 2.d ≥ 1.

Using (2), Claim 1, Claim 2 and n ≥ |S| + |T| + |X|, we infer $\begin{matrix} - 1 & \geq & (a + r) | S | - (b - r - d) | T | - 2 m \\ \geq & (a + r) | S | - (b - r - d) (n - | X | - | S |) - 2 m \\ = & (a + b - d) | S | + (b - r - d) | X | \\ - (b - r - d) n - 2 m \\ \geq & (a + b - d) (δ (G) - | X | - d) + (b - r - d) | X | \\ - (b - r - d) n - 2 m \\ = & (a + b - d) δ (G) - (a + r) | X | - d (a + b - d) \\ - (b - r - d) n - 2 m \\ \geq & (a + b - d) δ (G) - (a + r) (n - δ (G)) \\ - d (a + b - d) - (b - r - d) n - 2 m \\ = & (2 a + b + r - d) δ (G) - d (a + b - d) \\ - (a + b - d) n - 2 m . \end{matrix}$

It implies that $δ (G) \leq \frac{(a + b - d) (n + d) - 1 + 2 m}{2 a + b + r - d} .$ (6)

If d = 1 in (6), then we have $δ (G) \leq \frac{(a + b - 1) (n + 1) - 1 + 2 m}{2 a + b + r - 1} .$

It contradicts (3). Let $F (d) = \frac{(a + b - d) (n + d) - 1 + 2 m}{2 a + b + r - d}$ . According to $n \geq \frac{(a + b - 3) (2 a + b + r) + 1 + 2 m}{a + r}$ , we get F′ (h) <0, and so F (h) attains its maximum value at d = 2. Thus, we have $δ (G) \leq F (2) = \frac{(a + b - 2) (n + 2) - 1 + 2 m}{2 a + b + r - 2} .$ (7)

By $n \geq \frac{(a + b - 3) (2 a + b + r) + 1 + 2 m}{a + r}$ , we obtain $\begin{matrix} δ (G) & \leq & \frac{(a + b - 2) (n + 2) - 1 + 2 m}{2 a + b + r - 2} \\ \leq & \frac{(a + b - 1) n + a + b - 2 + 2 m}{2 a + b + r - 1}, \end{matrix}$ which contradicts (3). This completes the proof of Theorem 3. □

3 Proof of Theorem 4

By the hypothesis of Theorem 4, G - X has a Hamiltonian cycle C for any independent set X ⊆ V (G). Obviously, C is an ID-Hamiltonian fractional (2, f)-factor of G, and so Theorem 4 holds for a = 2 and g (x) = a for each x ∈ V (G). In the following, we may assume that b ≥ a ≥ 3.

For any independent set X ⊆ V (G), we write R = G - X. In terms of the condition of Theorem 4 and the definition of ID-Hamiltonian graph, R admits a Hamiltonian cycle C. Let H = R - E (C). Clearly, G includes the desired fractional factor if H contains a fractional (g - 2, f - 2)-factor. By way of contradiction, we assume that H has no fractional (g - 2, f - 2)-factor. Then by Lemma 3, there exists some subset S of V (H) satisfying

$\begin{matrix} (a - 2) | S | + d_{H - S} (T) - (b - 2) | T | \\ \leq (f - 2) (S) + d_{H - S} (T) - (g - 2) (T) \leq - 1, \end{matrix}$ (8) where T = {x : x ∈ V (H) - S, d_H-S (x) ≤ b - 3}.

Note that H = R - E (C). Thus, we have $d_{H - S} (x) \geq d_{R - S} (x) - 2$ (9) for each x ∈ T. In light of (8) and (9), we obtain $(a - 2) | S | + d_{R - S} (T) - b | T | \leq - 1,$ (10) and it follows from (8) and the definition of T that $T = {x : x \in V (R) - S, d_{R - S} (x) \leq b - 1} .$ (11)

If T =∅, then by (10) we obtain -1 ≥ (a - 2) |S|≥0, which is contradiction. Hence, T≠ ∅. Also, we define h = min {d_R-S (x) : x ∈ T}. According to (11), we have 0 ≤ h ≤ b - 1.

By considering a vertex x₁ of T with d_R-S (x₁) = h, we note that it can have neighbors in S, X, and h additional neighbors. This gives the following bound on δ (G), i.e., δ (G) ≤ |S| + |X| + h. As a consequence, $| S | \geq δ (G) - | X | - h .$ (12)

According to (10), (12), |X| ≤ n - δ (G) (as X is an independent set), and n ≥ |X| + |S| + |T|, we obtain $\begin{matrix} - 1 & \geq & (a - 2) | S | + d_{R - S} (T) - b | T | \\ \geq & (a - 2) | S | - (b - h) | T | \\ \geq & (a - 2) | S | - (b - h) (n - | X | - | S |) \\ = & (a + b - 2 - h) | S | + (b - h) | X | - (b - h) n \\ \geq & (a + b - 2 - h) (δ (G) - | X | - h) \\ + (b - h) | X | - (b - h) n \\ = & (a + b - 2 - h) δ (G) - (a - 2) | X | \\ - h (a + b - 2 - h) - (b - h) n \\ \geq & (a + b - 2 - h) δ (G) - (a - 2) (n - δ (G)) \\ - h (a + b - 2 - h) - (b - h) n \\ = & (b + 2 a - 4 - h) δ (G) \\ - (a + b - 2 - h) (n + h) \\ \geq & (b + 2 a - 4 - h) \frac{(a + b - 2) n}{b + 2 a - 4} \\ - (a + b - 2 - h) (n + h) \\ = & (h + \frac{(a - 2) n}{b + 2 a - 4} - (a + b - 2)) h, \end{matrix}$ i.e., $- 1 \geq (h + \frac{(a - 2) n}{b + 2 a - 4} - (a + b - 2)) h .$ (13)

If h = 0, then by (13) we have -1 ≥0, a contradiction. If h = 1, then (13) implies $n \leq \frac{(a + b - 4) (b + 2 a - 4)}{a - 2},$ which contradicts that $n \geq \frac{(a + b - 4) (b + 2 a - 4) + 1}{a - 2}$ .

In the following, we consider 2 ≤ h ≤ b - 1. Combining this with (13) and $n \geq \frac{(a + b - 4) (b + 2 a - 4) + 1}{a - 2}$ , we obtain $\begin{matrix} - 1 & \geq & (h + \frac{(a - 2) n}{b + 2 a - 4} - (a + b - 2)) h \\ \geq & (2 + \frac{(a + b - 4) (b + 2 a - 4) + 1}{b + 2 a - 4} \\ - (a + b - 2)) h \\ \geq & \frac{2}{b + 2 a - 4} > 0, \end{matrix}$ which is a contradiction. This completes the proof of Theorem 4. □

4 Proof of Theorem 5

It is easy to see that Theorem 5 holds for a = 2 and g (x) = a for each vertex x. Hence, we may assume that a ≥ 3.

For any independent set X ⊆ V (G), we write R = G - X. It is obvious that R includes a Hamiltonian cycle C. Set H = R - E (C). In order to prove Theorem 5, we need only to prove that H admits a fractional (g - 2, f - 2)-factor. By way of contradiction, we assume that H has no fractional (g - 2, f - 2)-factor. Then from Lemma 3, there exists some subset S ⊆ V (H) such that

$\begin{matrix} (a - 2) | S | + d_{H - S} (T) - (b - 2) | T | \\ \leq (f - 2) (S) + d_{H - S} (T) - (g - 2) (T) \leq - 1, \end{matrix}$ (14) where T = {x : x ∈ V (H) - S, d_H-S (x) ≤ b - 3}.

In terms of H = R - E (C), we obtain d_H-S (x) ≥ d_R-S (x) -2 for any x ∈ T. Combining this with (14), we have $(a - 2) | S | + d_{R - S} (T) - b | T | \leq - 1,$ (15) and $T = {x : x \in V (R) - S, d_{R - S} (x) \leq b - 1} .$ (16)

It follows from (15) that T≠ ∅. In the following, we define h = min {d_R-S (x) : x ∈ T}. In terms of (16), we obtain 0 ≤ h ≤ b - 1. For 1 ≤ h ≤ b - 1, we apply the same argument as in Theorem 4. In the following, we need only to consider h = 0.

Let Y = {x : x ∈ T, d_R-S (x) =0}. It is obvious that Y≠ ∅ and Y is an independent set of G. Thus, we have $| N_{G} (Y) | \leq | S | + | X |$ (17) and $| N_{G} (Y) | \geq \frac{(a + b - 3) n + \frac{a + 2 b - 5}{a + b - 3} | Y | - a + 1}{b + 2 a - 5} .$ (18)

Using (15), (80), |X| ≤ n - δ (G) (as X is an independent set), n ≥ |X| + |S| + |T|, and $δ (G) > \frac{(a + b - 3) n + a + b - 4}{b + 2 a - 5}$ , we have $\begin{matrix} - 1 & \geq & (a - 2) | S | + d_{R - S} (T) - b | T | \\ \geq & (a - 2) | S | + | T | - | Y | - b | T | \\ = & (a - 2) | S | - (b - 1) | T | - | Y | \\ \geq & (a - 2) | S | - (b - 1) (n - | X | - | S |) - | Y | \\ = & (a + b - 3) | S | + (b - 1) | X | - | Y | - (b - 1) n \\ \geq & (a + b - 3) (| N_{G} (Y) | - | X |) + (b - 1) | X | \\ - | Y | - (b - 1) n \\ = & (a + b - 3) | N_{G} (Y) | - (a - 2) | X | \\ - | Y | - (b - 1) n \\ \geq & (a + b - 3) | N_{G} (Y) | - (a - 2) (n - δ (G)) \\ - | Y | - (b - 1) n \\ = & (a + b - 3) | N_{G} (Y) | + (a - 2) δ (G) \\ - | Y | - (a + b - 3) n \\ > & (a + b - 3) | N_{G} (Y) | - (a + b - 3) n \\ + (a - 2) \frac{(a + b - 3) n + a + b - 4}{b + 2 a - 5} - | Y | \\ = & (a + b - 3) | N_{G} (Y) | - | Y | \\ - \frac{(a + b - 3)^{2} n - (a - 1) (a + b - 3)}{b + 2 a - 5} - 1, \end{matrix}$ that is $| N_{G} (Y) | < \frac{(a + b - 3) n + \frac{a + 2 b - 5}{a + b - 3} | Y | - a + 1}{b + 2 a - 5},$ which contradicts (81). Theorem 5 is proved. □

5 Conclusion and discussion

Finally, we present the following problem for our further studies.

Problem 1. Is it possible to weaken the binding number condition $bind (G) > \frac{(2 a + b + r - 1) (n - 1)}{(a + r) n - (a + b - 2) - 2 m}$ for the existence of fractional ID-(a, b, m)-deleted graphs in Theorem 3?

Problem 2. Let G be a graph of order $n \geq \frac{(a + b - 4) (b + 2 a - 4) + 1}{a - 2}$ , and a, b be two integers with 2 ≤ a ≤ b. 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). For a positive integer ɛ, $δ (G) \geq \frac{(a + b - 2) n - ɛ}{b + 2 a - 4} .$

Does G admits a ID-Hamiltonian fractional (g, f)-factor?

Problem 3. Let a, b be two integers with 2 ≤ a ≤ b, and G be an ID-Hamiltonian graph of order $n \geq \frac{(a + b - 5) (b + 2 a - 4) + 1}{a - 2}$ . 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). For two positive integers ɛ and η, $| N_{G} (X) | \geq \frac{(a + b - 3) n + \frac{b + 2 a - 5}{a + b - 3} | X | - a + 1 - ɛ}{b + 2 a - 5}$ for every non-empty independent subset X of V (G), and $δ (G) > \frac{(a + b - 3) n + a + b - 4 - η}{b + 2 a - 5} .$

Does G contains a ID-Hamiltonian fractional (g, f)-factor?

Conflict of interests

The authors 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

Zhou

, A sufficient condition for graphs to be fractional(k, m)-deleted graphs, Appl Math Lett24 (2011), 1533–1538.

Zhou

, Binding numbers for fractional ID-k-factor-critical graphs, Acta Math Sin (Engl Ser)30(1) (2014), 181–186.

Gao

, Guo

and Wang

K.Y.

, Ontology algorithm using singular value decomposition and applied in multidisciplinary, Cluster Comput19(4) (2016), 2201–2210.

Gao

and Wang

W.F.

, The fifth geometric arithmetic index of bridge graph and carbon nanocones, J DifferEqu Appl (2016). https://dx-doi-org.web.bisu.edu.cn/10.1080/10236198.2016.1197214

Gao

and Wang

W.F.

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

Gao

, Guirao

J.L.G.

and Wu

H.L.

, Two tight independent set conditions for fractional (g, f, m)-deleted graphs systems, Qual Theory Dyn Syst, In press.

Guirao

J.L.G.

and Luo

A.C.J.

, New trends in nonlinear dynamics and chaoticity, Nonlinear Dynam84 (2016), 1–2.

Maldonado

, Prada

and Senosiain

M.J.

, On linear operators and bases on Köthe spaces, Appl Math Nonl Sc1(2) (2016), 617–624.

Gao

, Some results on fractional deleted graphs, Doctoral disdertation of Soochow university, 2012.

10.

Woodall

D.R.

, The binding number of a graph and its Anderson number, J Combin Theory Ser B15 (1973), 225–255.

11.

Anstee

R.P.

, Simplified existence theorems for (g, f)-factors, Discrete Appl Math27 (1990), 29–38.