Characterizations of maximum fractional (g,f)-factors of graphs

AbstractIn this paper a characterization of maximum fractional (g,f)-factors of a graph is presented. The properties of the maximum fractional (g,f)-factors and fractional (g,f)-factors with the minimum of edges are also given, generalizing the results given in [William Y.C. Chen, Maximum (g,f)-factors of a general graph, Discrete Math. 91 (1991) 1–7] and [Edward R. Scheinerman, Daniel H. Ullman, Fractional Graph Theory, John Wiley and Sonc, Inc., New York, 1997]. Furthermore, some new results on fractional factors are obtained which may be used in the design of networks. A polynomial time algorithm can be obtained for actually finding such maximum fractional (g,f)-factors in a graph from the proof