A Sufficient Condition for the Existence of Restricted Fractional (g, f)-Factors in Graphs

摘要

In an NFV network, the availability of resource scheduling can be transformed to the existence of the fractional factor in the corresponding NFV network graph. Researching on the existence of special fractional factors in network structure can help to construct the NFV network with efficient application of resources. Let h: E(G) - [0, 1] be a function. We write d(G)(h)(x) = Sigma(e is an element of x)h(e). We call a graph F-h with vertex set V(G) and edge set E-h a fractional (g, f)-factor of G with indicator function h if g(x) = d(G)(h)(x) = f(x) holds for any x is an element of V(G), where E-h = {e : e is an element of E(G), h(e) 0}. We say that G has property E(m, n) with respect to a fractional (g, f)-factor if for any two sets of independent edges M and N with divide M divide = m, divide N divide = n, and M boolean AND N = circle divide, G admits a fractional (g, f)-factor F-h with h(e) = 1 for any e is an element of M and h(e) = 0 for any e is an element of N. The concept of property E(m, n) with respect to a fractional (g, f)-factor corresponds to the structure of an NFV network where certain channels are occupied or damaged in some period of time. In this paper, we consider the resource scheduling problem in NFV networks using graph theory, and show a neighborhood union condition for a graph to have property E(1, n) with respect to a fractional (g, f)-factor. Furthermore, it is shown that the lower bound on the neighborhood union condition in the main result is the best possible in some sense.