Graphic deviation

Given a sequence of nn nonnegative integers how can we find the graphs which achieve the minimal deviation from that sequence? This extends the classical problem regarding what sequences are “graphic”, that is, can be the degrees of a simple graph, to issues regarding arbitrary sequences. In this context, we investigate properties of the “minimal graphs”. We shall demonstrate how a variation on the Havel–Hakimi algorithm can supply the value of the minimal possible deviation, and how consideration of the Ruch–Gutman condition and the Ferrer diagram can yield the complete set of graphs achieving this minimum. An application of this analysis is to a population of individuals represented by vertices, interactions between pairs by edges and in which each individual has a preferred range for their number of links to other individuals. Individuals adjust their links according to their preferred range and the graph evolves towards some set of graphs which achieve the minimal possible deviation. This Markov chain is defined but detailed analysis is omitted.