Wu Jianzhang

(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China)

Abstract In the resource scheduling network,the availability of resource scheduling is equivalent to the existence of the fractional factor in the corresponding network graph. The study on the existence of fractional factors in specific graph structure can help engineers design and construct the network with efficient use of resources. A graph G is called an all fractional(g,f,n′,m)-critical deleted graph if after removing any n′ vertices from G the remaining graph is still an all fractional(g,f,m)-deleted graph. In this paper,we present two binding number conditions for a graph to be an all fractional(g,f,n′,m)-critical deleted graph,and illustrate the results are sharp with examples.

Key words NFV network Resource scheduling All fractional factor All fractional(g,f,n′,m)-critical deleted graph

1 Introduction

Network function virtualization (NFV), introduced from the field of industry, aims to solve the inconveniences,and avoids the hardware constant proliferation in the engineering applications. This trick improves the revolution in the network in terms of leveraging virtualization technology to provide a new method in network designing. There was a piece of breaking news in 2012 that seven leading telecom network operators in the world choose the ETSI(European Telecom Standards Institute)as the home of the industry specification group of network function virtualization. With the pattern of NFV, traditional middleboxes acted as a special VNF (Virtual Network Function) which works as single modules in software. It enables each function to be modularity and isolation,and thus can be dealt with independently.Furthermore,servers are easy to install and deploy the VNFs by means of related technologies,and thus it allows VNFs dynamic migration from one server to another.

As an envisioned framework, NFV can solve most of the current network problems in light of widely using the particular hardware appliances. Moreover,it offers chances in cost decline and network optimization,and helps to configure hybrid scenarios. The availability of resource scheduling in the NFV network is equivalent to the existence of the fractional factor in the corresponding NFV network graph.It inspires us to consider the problem of resource scheduling from a theoretical point of view. In what follows,we transform it into the mathematical context.

LetG= (V(G),E(G))be a graph(represent a special NFV network)with vertex setV(G)(set of sites)and edge setE(G)(set of channels). LetdG(x)andNG(x)be the degree and the open neighborhood ofx ∈V(G), respectively. SetNG[x] =NG(x)∪{x}, and letG[S] denote the subgraph induced byS ?V(G). For anyS ?V(G),denoteG-S=G[V(G)S]. SeteG(S,T)=|{e=xy|x ∈S,y ∈T}|for any two subsetsS,T ?V(G)withS ∩T=?. The degree ofGis denoted byδ(G) = min{dG(x) :x ∈V(G)}. In short,d(x)is used to expressdG(x)for anyx ∈V(G). Readers can refer to Bondy and Mutry[1]for more terminologies and notations used but undefined here.

The binding numberbind(G)of a graphGis defined as follows:

Specifically, data need to be divided into several small data packets during transmission, and these small data packets are transmitted through multiple channels,and finally the data is assembled at the target vertex. The fractional factor characterizes the feasibility of a certain size of data packet transmission at the same time.

We say thatGhas all fractional(g,f)-factors ifGhas a fractionalp-factor for eachp:V(G)→N satisfyingg(x)≤p(x)≤f(x)for any vertexx. Ifg(x) =a,f(x) =bfor each vertexxandGhas all fractional(g,f)-factors,then we say thatGhas all fractional[a,b]-factors.

Lu[2]presented the sufficient and necessary condition for a graph with all fractional(g,f)-factors.Zhou and Sun [4] introduced the concept of all fractional (a,b,n′)-critical graph, which is a graph that after deleting anyn′vertices of it the remaining graph has all fractional[a,b]-factors. Also,the necessary and sufficient condition for a graph to be all fractional(a,b,n′)-critical is determined. More results on the topic with fractional factor,fractional deleted graphs,fractional critical and other network applications can refer to Gao and Gao[3],Gao and Wang[5-8],and Gao et al. [9-14].

A graphGis called an all fractional(g,f,n′,m)-critical deleted graph if after deleting anyn′vertices ofGthe remaining graph ofGis an all fractional (g,f,m)-deleted graph. Ifg(x) =a,f(x) =bfor eachx ∈V(G), then the all fractional (g,f,n′,m)-critical deleted graph becomes an all fractional(a,b,n′,m)-critical deleted graph,which means,after deleting anyn′vertices ofGthe remaining graph ofGis an all fractional(a,b,m)-deleted graph.

The concept of all fractional (g,f,n′,m)-critical deleted graphs reflects the feasibility of effective use of resources in NFV networks.

Our two main results in this paper are listed as follows.

Obviously, Theorem 1.2 is stronger than Theorem 1.1 under certain special conditions. We will explain that Theorem 1.1 is the best possible for certain combinations of (a,b,n′,m). Furthermore,Theorem 1.1 and Theorem 1.2 reflect the binding number condition for the available of resource scheduling in the NFV network.

Setm=0 in Theorems 1.1 and 1.2,we infer two sufficient binding number conditions on all fractional(g,f,n′)-critical graphs,respectively.

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

Lemma 1.1 ([15] ) Leta,b,mandn′be non-negative integers with 1≤a ≤b, and letGbe a graph of ordernwithn ≥b+n′+m+1. Letg,f:V(G)→Z+be two integer-valued functions witha ≤g(x)≤f(x)≤bfor eachx ∈V(G),andHbe a subgraph ofGwithmedges. ThenGis all fractional(g,f,n′,m)-critical deleted if and only if for anyS ?V(G)with|S|≥n′,

The relationship between the binding number and all kinds of the fractional factors (including the fractionalk-factor, fractional [a,b]-factor and the fractional (g,f)-factor) has been discussed in the published papers in last 10 years. The fractional critical deletion graph is an extended concept of the fractional deletion graph and fractional criticality graph,and the existence of fractional factors in special cases has not been discussed. In this paper we investigate that under what conditions the fractional factor of a network graph exists in a particular framework.

2 Proof of Theorem 1.1

In this section,we present the proof of Theorem 1.1.

We selectSandTsuch that|T|is minimum. If there existsx ∈TsatisfyingdG-S(x)≥g(x),then the subsetsSandT {x}satisfy(2.1)as well. This contradicts the selection rule ofSandT. It implies thatdG-S(x)≤g(x)-1≤b-1 for anyx ∈T.

3 Proof of Theorem 1.2

This contradicts the condition of Theorem 1.2.

Now Theorem 1.2 follows from(3.12),(3.14)and Lemma 3.1. The proof is completed.

4 Conclusion

In this paper, we investigated the relationship between the binding number and all fractional(g,f,n′,m)-critical deleted graphs, and gave two sufficient conditions on the binding number for a graph to be all fractional(g,f,n′,m)-critical deleted. The tricks to prove our main results are based on contrapositive. Several examples are presented to reveal that the binding number bound stated in the theory are best in some sense. The results achieved in our paper illustrate the promising application prospects on resource scheduling in the NFV network.