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.
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 dG (x) and NG (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 eG (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:
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 for each x ∈ V (G), where 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 . 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 . Ifthen 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 , then G is fractional ID-k-factor-critical.
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 . If , 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 . If , 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 . If , 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 . If , 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 (if a ≠ 2) and , 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 . 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
for every non-empty independent subset X of V (G), and
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
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 .
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) - dG-S (T) ≤ f (S),where T = {x ∈ V (G) ∖ S | dG-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 iffor all disjoint subsets S, T of V (G).
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∈TdH (x) - eH (T, S) ≤2m, there exists certain disjointed subsets S, T of V (H) satisfying
We denote that bind (G) = λ. In terms of Lemma 2 and the assumption in Theorem 3, we infer
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 {dH-S (x) : x ∈ T}. We now determine the following claims.
Claim 1. |S| ≥ δ (G) - |X| - d.
Proof. We select x1 ∈ T such that dH-S (x1) = d. Then, we deduce
which reveals
Therefore, Claim 1 is established. □
Claim 2. |X| ≤ n - δ (G).
Proof. It is not hard to check that dG (x) ≥ δ (G) for any x ∈ V (G). Thus, dG (x) ≥ δ (G) for any x ∈ X. Since X is an independent set of G, we get
for each x ∈ X, and thus
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
The last step is established since
Set
We deduce that
Thus,
Combining this with (2), n ≥ |X| + |S| + |T|, Claim 1, and Claim 2, we deduce
a contradiction. Hence, the Claim 3 holds. □
Let Y = {x : x ∈ T, dH-S (x) =0}. Since Y≠ ∅, NG (V (G)\ (X ∪ S)) ∩ Y = ∅ and |NG (V (G) \ (X ∪ S)) | ≤ n - |Y|, we have,
i.e.,
In terms of (2), (3), (5), Claim 2, Claim 3 and |X| + |S| + |T| ≤ n, we get
which implies
which contradicts the assumption of Theorem 3.
Case 2.d ≥ 1.
Using (2), Claim 1, Claim 2 and n ≥ |S| + |T| + |X|, we infer
It implies that
If d = 1 in (6), then we have
It contradicts (3). Let . According to , we get F′ (h) <0, and so F (h) attains its maximum value at d = 2. Thus, we have
By , we obtain
which contradicts (3). This completes the proof of Theorem 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
where T = {x : x ∈ V (H) - S, dH-S (x) ≤ b - 3}.
Note that H = R - E (C). Thus, we have
for each x ∈ T. In light of (8) and (9), we obtain
and it follows from (8) and the definition of T that
If T =∅, then by (10) we obtain -1 ≥ (a - 2) |S|≥0, which is contradiction. Hence, T≠ ∅. Also, we define h = min {dR-S (x) : x ∈ T}. According to (11), we have 0 ≤ h ≤ b - 1.
By considering a vertex x1 of T with dR-S (x1) = 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,
According to (10), (12), |X| ≤ n - δ (G) (as X is an independent set), and n ≥ |X| + |S| + |T|, we obtain
i.e.,
If h = 0, then by (13) we have -1 ≥0, a contradiction. If h = 1, then (13) implies
which contradicts that .
In the following, we consider 2 ≤ h ≤ b - 1. Combining this with (13) and , we obtain
which is a contradiction. This completes the proof of Theorem 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
where T = {x : x ∈ V (H) - S, dH-S (x) ≤ b - 3}.
In terms of H = R - E (C), we obtain dH-S (x) ≥ dR-S (x) -2 for any x ∈ T. Combining this with (14), we have
and
It follows from (15) that T≠ ∅. In the following, we define h = min {dR-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, dR-S (x) =0}. It is obvious that Y≠ ∅ and Y is an independent set of G. Thus, we have
and
Using (15), (80), |X| ≤ n - δ (G) (as X is an independent set), n ≥ |X| + |S| + |T|, and , we have
that is
which contradicts (81). Theorem 5 is proved. □
Conclusion and discussion
Finally, we present the following problem for our further studies.
Problem 1. Is it possible to weaken the binding number condition for the existence of fractional ID-(a, b, m)-deleted graphs in Theorem 3?
Problem 2. Let G be a graph of order , 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 ɛ,
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 . 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 η,
for every non-empty independent subset X of V (G), and
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
1.
ZhouS., A sufficient condition for graphs to be fractional(k, m)-deleted graphs, Appl Math Lett24 (2011), 1533–1538.
2.
ZhouS., Binding numbers for fractional ID-k-factor-critical graphs, Acta Math Sin (Engl Ser)30(1) (2014), 181–186.
3.
GaoW., GuoY. and WangK.Y., Ontology algorithm using singular value decomposition and applied in multidisciplinary, Cluster Comput19(4) (2016), 2201–2210.
