Havel–Hakimi residues of unigraphs

The residue r(G)r(G) of a graph G is the number of zeros left after fully reducing the degree sequence of G via the Havel–Hakimi algorithm. The residue is one of the best known lower bounds on the independence number of a graph in terms of the degree sequence. Though this bound may be arbitrarily weak for graphs in general, we show that if G is the unique realization of its degree sequence, then the independence number of G   is either r(G)r(G) or r(G)+1r(G)+1, and we characterize the unigraphs corresponding to each value.

► We compare Havel–Hakimi residues and independence numbers for unigraphs. ► We show how the residue behaves in relation to the canonical decomposition of a graph. ► The independence number of a unigraph is either equal to or 1 more than its residue.