Analysis of fractional factor system for data transmission in SDN

Owing to the similarities and for convenience, the fractional factor problem and the cardinality matching problem could be treated in the same way. Besides, the fractional factor has been widely used in various fields in scheduling, network design and the combinatorial polyhedron. To be clear, an example of network application is given. As we all know, some of the large data packets are sent to different terminals through channels. If the large packets can be divided into smaller parcels, the work efficiency can be largely improved. Hence, the feasible assignment of data packets is just a fractional flow problem, that is to say, it is transformed into a fractional factor problem if the information terminals and sources are not matched.

The whole network can be represented by a graph where each site and each channel are corresponding to a vertex and an edge, respectively. Normally, the data transmission depends on how the shortest path between vertices is selected. Nevertheless, it is the computation of network flow that influences the data transmission in software definition network, and the path where the transmission congestion is the lightest is chosen. In this way, the model of data transmission problem in SDN is transformed into the existence of fractional factor in its corresponding graph.

All graphs that appeared in this paper are finite, loopless, and have no 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 dictated by d_G(x) and N_G(x), respectively. Let Δ(G) and δ(G) represent the maximum degree and the minimum degree of G, respectively. For S ⊆V(G), we dictate by G[S] the subgraph of G obtained by S, and let G −S = G[V(G)\S]. For two disjointed subsets S and T of V(G), e_G(S,T) is used to denote the number of edges with one end in S and the other in T.

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)≤dGh(x)≤f(x) $g\left( x \right)\le d_{G}^{h}\left( x \right)\le f\left( x \right)$for each x ∈ V(G), where dGh(x)=∑e∈E(x) $d_{G}^{h}\left( x \right)=\sum\limits_{e\in E\left( x \right)}^{\,}{\,}$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≤dGh(x)≤b. $a\le d_{G}^{h}\left( x \right)\le 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.

If for each edge subset H ⊆E (G) with |H|=m, a graph G is called a fractional (a,b,m)-deleted graph. There exists a fractional (a,b)-factor h such that h(e) = 0 for all e ∈ H. When any m edges are removed, the resulting graph still has a fractional (a,b)-factor. If G −I is a fractional (a,b,m)-deleted graph for every independent set I of G, a graph is a fractional independent-set-deletable (a,b,m)-deleted graph (shortly, fractional ID-(a,b,m)-deleted graph). 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-critical graph.

If G has a fractional (g, f )-factor containing a Hamiltonian cycle, it is said that G includes a Hamiltonian fractional (g, f )-factor. A graph G is called an ID-Hamiltonian graph if after deleting any independent set of G the remaining graph of G admits a Hamiltonian cycle. Then, 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.

Here, back to SDN, the independent set I represents the website with high transmission congestion and m edges stand for several channels with high transmission congestion. Therefore, the data transmission problem is studied by taking the ID-(a,b,m)-deleted graph and ID-Hamiltonian fractional (g, f )-factor in the networks model into account.

Some recent results on the exist fractional factor, computer network designing and related fields can be referred in the studies by Liu et al. [4], Virk and Quraish [5], and Knor et al. [3].

In this paper, we investigate ID-Hamiltonian fractional (g, f )-factors in graphs and obtain the following two results that are the generalization of the result published in the study by Gong et al. [2].

By the hypothesis of Theorem 1, 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 1 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 1 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

(1) a + Δ<!-- Δ --> −<!-- − --> 2 S + d H −<!-- − --> S T −<!-- − --> b −<!-- − --> Δ<!-- Δ --> −<!-- − --> 2 T ≤<!-- ≤ --> f −<!-- − --> 2 S + d H −<!-- − --> S T −<!-- − --> g −<!-- − --> 2 T ≤<!-- ≤ --> −<!-- − --> 1 , $$\begin{align}& \left( a+\Delta -2 \right)\left| S \right|+{{d}_{H-S}}\left( T \right)-\left( b-\Delta -2 \right)\left| T \right|\\ & \le \left( f-2 \right)\left( S \right)+{{d}_{H-S}}\left( T \right)-\left( g-2 \right)\left( T \right)\le -1, \\ \end{align}$$

where T = {x : x ∈ V(H)−S,d_H−S(x) ≤ b−Δ−3}.

Note that H = R −E(C). Thus, we have

(2) dH−S(x)≥dR−S(x)−2 $${{d}_{H-S}}\left( x \right)\ge {{d}_{R-S}}\left( x \right)-2$$

for each x ∈ T. In light of (1) and (2), we obtain

(3) (a+Δ−2)| S |+dR−S(T)−(b−Δ)| T |≤−1, $$\left( a+\Delta -2 \right)\left| S \right|+{{d}_{R-S}}\left( T \right)-\left( b-\Delta \right)\left| T \right|\le -1,$$

and it follows from (1) and the definition of T that

(4) T={ x:x∈V(R)−S,dR−S(x)≤b−Δ−1 }. $$T=\left\{ x:x\in V\left( R \right)-S,{{d}_{R-S}}\left( x \right)\le b-\Delta -1 \right\}.$$

If T = / 0, then by (3) we obtain −1 ≥ (a+Δ−2)|S| ≥ 0, which is contradiction. Hence, T ≠ / 0. Also, we define h = min{d_R−S(x) : x ∈ T}. According to (4), 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,

(5) | S |≥δ(G)−| X |−h. $$\left| S \right|\ge \delta \left( G \right)-\left| X \right|-h.$$

According to (3), (5), |X| ≤ n −δ(G) (as X is an independent set), and n ≥ |X|+|S|+|T|, we obtain

−<!-- − --> 1 ≥<!-- ≥ --> a + Δ<!-- Δ --> −<!-- − --> 2 S + d R −<!-- − --> S T −<!-- − --> b −<!-- − --> Δ<!-- Δ --> T ≥<!-- ≥ --> a + Δ<!-- Δ --> −<!-- − --> 2 S −<!-- − --> b −<!-- − --> Δ<!-- Δ --> −<!-- − --> h T ≥<!-- ≥ --> a + Δ<!-- Δ --> −<!-- − --> 2 S −<!-- − --> b −<!-- − --> Δ<!-- Δ --> −<!-- − --> h n −<!-- − --> X −<!-- − --> S = a + b −<!-- − --> 2 −<!-- − --> h S + b −<!-- − --> Δ<!-- Δ --> −<!-- − --> h X −<!-- − --> b −<!-- − --> Δ<!-- Δ --> −<!-- − --> h n ≥<!-- ≥ --> 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 ≥<!-- ≥ --> 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 ≥<!-- ≥ --> b + 2 a + Δ<!-- Δ --> −<!-- − --> 4 −<!-- − --> h a + b −<!-- − --> 2 n b + 2 a + Δ<!-- Δ --> −<!-- − --> 4 −<!-- − --> a + b −<!-- − --> 2 −<!-- − --> h n + h = h + a + Δ<!-- Δ --> −<!-- − --> 2 n b + 2 a + Δ<!-- Δ --> −<!-- − --> 4 −<!-- − --> a + b −<!-- − --> 2 h , $$\begin{align}& -1\ge \left( a+\Delta -2 \right)\left| S \right|+{{d}_{R-S}}\left( T \right)-\left( b-\Delta \right)\left| T \right| \\ & \,\,\,\,\,\,\,\ge \left( a+\Delta -2 \right)\left| S \right|-\left( b-\Delta -h \right)\left| T \right| \\ & \,\,\,\,\,\,\,\ge \left( a+\Delta -2 \right)\left| S \right|-\left( b-\Delta -h \right)\left( n-\left| X \right|-\left| S \right| \right) \\ & \,\,\,\,\,\,=\left( a+b-2-h \right)\left| S \right|+\left( b-\Delta -h \right)\left| X \right|-\left( b-\Delta -h \right)n \\ & \,\,\,\,\,\,\ge \left( a+b-2-h \right)\left( \delta \left( G \right)-\left| X \right|-h \right)+\left( b-\Delta -h \right)\left| X \right|-\left( b-\Delta -h \right)n \\ & \,\,\,\,\,\,=\left( a+b-2-h \right)\delta \left( G \right)-\left( a+\Delta -2 \right)\left| X \right|-h\left( a+b-2-h \right)-\left( b-\Delta -h \right)n \\ & \,\,\,\,\,\,\ge \left( a+b-2-h \right)\delta \left( G \right)-\left( a+\Delta -2 \right)\left( n-\delta \left( G \right) \right)-h\left( a+b-2-h \right)-\left( b-\Delta -h \right)n \\ & \,\,\,\,\,\,\,=\left( b+2a+\Delta -4-h \right)\delta \left( G \right)-\left( a+b-2-h \right)\left( n+h \right) \\ & \,\,\,\,\,\,\,\ge \left( b+2a+\Delta -4-h \right)\frac{\left( a+b-2 \right)n}{b+2a+\Delta -4}-\left( a+b-2-h \right)\left( n+h \right) \\ & \,\,\,\,\,\,\,=\left( h+\frac{\left( a+\Delta -2 \right)n}{b+2a+\Delta -4}-\left( a+b-2 \right) \right)h, \\ \end{align}$$

i.e.,

(6) −<!-- − --> 1 ≥<!-- ≥ --> h + a + Δ<!-- Δ --> −<!-- − --> 2 n b + 2 a + Δ<!-- Δ --> −<!-- − --> 4 −<!-- − --> a + b −<!-- − --> 2 h . $$-1\ge \left( h+\frac{\left( a+\Delta -2 \right)n}{b+2a+\Delta -4}-\left( a+b-2 \right) \right)h.$$

If h = 0, then by (6) we have −1 ≥ 0, a contradiction. If h = 1, then (6) implies

n≤(a+b−4)(b+2a+Δ−4)a+Δ−2, $$n\le \frac{\left( a+b-4 \right)\left( b+2a+\Delta -4 \right)}{a+\Delta -2},$$

which contradicts that n≥(a+b−4)(b+2a+Δ−4)+1a+Δ−2. $n\ge \frac{\left( a+b-4 \right)\left( b+2a+\Delta -4 \right)+1}{a+\Delta -2}.$

In the following, we consider 2 ≤ h ≤ b−Δ−1. Combining this with (6) and n≥(a+b−4)(b+2a−4)+1a+Δ−2, $n\ge \frac{\left( a+b-4 \right)\left( b+2a-4 \right)+1}{a+\Delta -2},$we obtain

−1≥(h+(a+Δ−2)nb+2a+Δ−4)−(a+b−2))h≥(2+(a+b−4)(b+2a+Δ−4)+1b+2a+Δ−4−(a+b−2))h≥2b+2a+Δ−4>0, $$\begin{align}& -1\ge \left( h+\frac{\left( a+\Delta -2 \right)n}{b+2a+\Delta -4} \right)-\left( a+b-2 \right))h \\ & \,\,\,\,\,\,\ge \left( 2+\frac{\left( a+b-4 \right)\left( b+2a+\Delta -4 \right)+1}{b+2a+\Delta -4}-\left( a+b-2 \right) \right)h \\ & \,\,\,\,\,\,\ge \frac{2}{b+2a+\Delta -4}>0, \\ \end{align}$$

which is a contradiction. This completes the proof of Theorem 1.

It is easy to see that Theorem 2 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 2, 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

(7) a + Δ<!-- Δ --> −<!-- − --> 2 S + d H −<!-- − --> S T −<!-- − --> b −<!-- − --> Δ<!-- Δ --> −<!-- − --> 2 T ≤<!-- ≤ --> f −<!-- − --> 2 S + d H −<!-- − --> S T −<!-- − --> g −<!-- − --> 2 T ≤<!-- ≤ --> −<!-- − --> 1 , $$\begin{align}& \left( a+\Delta -2 \right)\left| S \right|+{{d}_{H-S}}\left( T \right)-\left( b-\Delta -2 \right)\left| T \right|\\ & \le \left( f-2 \right)\left( S \right)+{{d}_{H-S}}\left( T \right)-\left( g-2 \right)\left( T \right)\le -1, \\ \end{align}$$

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 (7), we have

(8) (a+Δ−2)| S |+dR−S(T)−(b−Δ)| T |≤−1, $$\left( a+\Delta -2 \right)\left| S \right|+{{d}_{R-S}}\left( T \right)-\left( b-\Delta \right)\left| T \right|\le -1,$$

and

(9) T={ x:x∈V(R)−S,dR−S(x)≤b−Δ−1 }. $$T=\left\{ x:x\in V\left( R \right)-S,{{d}_{R-S}}\left( x \right)\le b-\Delta -1 \right\}.$$

It follows from (8) that T ≠ / 0. In the following, we define h = min{d_R−S(x) : x ∈ T}. In terms of (9), we obtain 0 ≤ h ≤ b −Δ−1. For 1 ≤ h ≤ b −Δ−1, we apply the same argument as in Theorem 1. 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 ≠ /0 and Y is an independent set of G. Thus, we have

(10) | NG(Y) |≤| S |+| X | $$\left| {{N}_{G}}\left( Y \right) \right|\le \left| S \right|+\left| X \right|$$

and

(11) | NG(Y) |≥(a+b−3)n+b+2a+Δ−5a+b−3| Y |−(a+Δ)+1b+2a+Δ−5. $$\left| {{N}_{G}}\left( Y \right) \right|\ge \frac{\left( a+b-3 \right)n+\frac{b+2a+\Delta -5}{a+b-3}\left| Y \right|-\left( a+\Delta \right)+1}{b+2a+\Delta -5}.$$

Using (8), (10), |X| ≤ n−δ(G) (as X is an independent set), n ≥ |X|+|S|+|T|, and δ(G)>(a+b−3)n+a+b−4b+2a+Δ−5, $\delta \left( G \right)>\frac{\left( a+b-3 \right)n+a+b-4}{b+2a+\Delta -5},$we have

−<!-- − --> 1 ≥<!-- ≥ --> a + Δ<!-- Δ --> −<!-- − --> 2 S + d R −<!-- − --> S T −<!-- − --> b −<!-- − --> Δ<!-- Δ --> T ≥<!-- ≥ --> a + Δ<!-- Δ --> −<!-- − --> 2 S + T −<!-- − --> Y −<!-- − --> b −<!-- − --> Δ<!-- Δ --> T = a + Δ<!-- Δ --> −<!-- − --> 2 S −<!-- − --> b −<!-- − --> Δ<!-- Δ --> −<!-- − --> 1 T | −<!-- − --> | Y ≥<!-- ≥ --> a + Δ<!-- Δ --> −<!-- − --> 2 S −<!-- − --> b −<!-- − --> Δ<!-- Δ --> −<!-- − --> 1 n −<!-- − --> X −<!-- − --> S −<!-- − --> Y = a + b −<!-- − --> 3 S + b −<!-- − --> Δ<!-- Δ --> −<!-- − --> 1 X | −<!-- − --> | Y −<!-- − --> b −<!-- − --> Δ<!-- Δ --> −<!-- − --> 1 n ≥<!-- ≥ --> 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 ≥<!-- ≥ --> 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 a + b −<!-- − --> 3 n + a + b −<!-- − --> 4 b + 2 a + Δ<!-- Δ --> −<!-- − --> 5 −<!-- − --> Y = a + b −<!-- − --> 3 N G Y −<!-- − --> Y −<!-- − --> a + b −<!-- − --> 3 2 n −<!-- − --> a + Δ<!-- Δ --> −<!-- − --> 1 a + b −<!-- − --> 3 b + 2 a + Δ<!-- Δ --> −<!-- − --> 5 −<!-- − --> 1 , $$\begin{align}& -1\ge \left( a+\Delta -2 \right)\left| S \right|+{{d}_{R-S}}\left( T \right)-\left( b-\Delta \right)\left| T \right| \\ & \ge \left( a+\Delta -2 \right)\left| S \right|+\left| T \right|-\left| Y \right|-\left( b-\Delta \right)\left| T \right| \\ & =\left( a+\Delta -2 \right)\left| S \right|-\left( b-\Delta -1 \right)\left| T| -|Y\right| \\ & \ge \left( a+\Delta -2 \right)\left| S \right|-\left( b-\Delta -1 \right)\left( n-\left| X \right|-\left| S \right|-\left| Y \right| \right) \\ & =\left( a+b-3 \right)\left| S \right|+\left( b-\Delta -1 \right)\left| X|-|Y\right|-\left( b-\Delta -1 \right)n \\ & \ge \left( a+b-3 \right)\left( \left| {{N}_{G}}\left( Y \right) \right|-\left| X \right| \right)+\left( b-\Delta -1 \right)\left| X \right|-\left| Y \right|-\left( b-\Delta -1 \right)n \\ & =\left( a+b-3 \right)\left| {{N}_{G}}\left( Y \right) \right|-\left( a+\Delta -2 \right)\left| X \right|-\left| Y \right|-\left( b-\Delta -1 \right)n \\ & \,\,\,\ge \left( a+b-3 \right)\left| {{N}_{G}}\left( Y \right) \right|-\left( a+\Delta -2 \right)\left( n-\delta \left( G \right) \right)-\left| Y \right|-\left( b-\Delta -1 \right)n \\ & \,\,\,=\left( a+b-3 \right)\left| {{N}_{G}}\left( Y \right) \right|+\left( a+\Delta -2 \right)\delta \left( G \right)-\left| Y \right|-\left( a+b-3 \right)n \\ & \,\,\,\,>\left( a+b-3 \right)\left| {{N}_{G}}\left( Y \right) \right|-\left( a+b-3 \right)n+\left( a+\Delta -2 \right)\frac{\left( a+b-3 \right)n+a+b-4}{b+2a+\Delta -5}-\left| Y \right| \\ & \,\,\,\,\,=\left( a+b-3 \right)\left| {{N}_{G}}\left( Y \right) \right|-\left| Y \right|-\frac{{{\left( a+b-3 \right)}^{2}}n-\left( a+\Delta -1 \right)\left( a+b-3 \right)}{b+2a+\Delta -5}-1, \\ \end{align}$$

that is

| NG(Y) |<(a+b−3)n+b+2a+Δ−5a+b−3| Y |−(a+Δ)+1b+2a+Δ−5, $$\left| {{N}_{G}}\left( Y \right) \right|<\frac{\left( a+b-3 \right)n+\frac{b+2a+\Delta -5}{a+b-3}\left| Y \right|-\left( a+\Delta \right)+1}{b+2a+\Delta -5},$$

which contradicts (11). Theorem 2 is proved.