Some remarks about factors of graphs

Abstract

A (g, f)-factor of a graph is a subset F of E such that for all v is an element of V, g(v) <= deg(F)(V) <= f(v). Lovasz gave a necessary and sufficient condition for the existence of a (g, f)-factor. We extend, to the case of edge-weighted graphs, a result of Kano and Saito who showed that if g(v) < lambda deg(E)(V) < f(v) for any lambda is an element of [0, 1], then a (g, f)-factor always exist. In addition, we use results of Anstee to provide new necessary and sufficient conditions for the existence of a (g, f)-factor.