Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d1,d2,…,dn〉〈d1,d2,…,dn〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph GG on nn vertices whose iith vertex has degree didi, for 1≤i≤n1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E)H=(V,E) is a graph and gg and ff are integer-valued functions on the vertex set VV, then a (g,f)(g,f)-factor of HH is a subgraph G=(V,F)G=(V,F) of HH whose degree at each vertex v∈Vv∈V lies in the interval [g(v),f(v)][g(v),f(v)]. Thus, a (0,1)(0,1)-factor is just a matching of HH and a (1, 1)-factor is a perfect matching of HH. If HH is complete then a (g,f)(g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v1),f(v1)],[g(v2),f(v2)],…,[g(vn),f(vn)]〉〈[g(v1),f(v1)],[g(v2),f(v2)],…,[g(vn),f(vn)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)(g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)(g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)(f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös–Gallai characterization of (f,f)(f,f)-factors in complete graphs) at no additional cost.