Small-scale operations on graphic sequences
For graph theory researchers, this provides a new tool for analyzing graphic sequences, but the results are primarily theoretical and incremental.
The paper introduces the 2-reduction operation on graphic sequences, showing that it preserves graphicness and enables simple generation of all realizations, proof of existing characterizations, and new characterizations linking mathematical and algorithmic aspects.
A sequence D=(d1, d2, ..., dn) of positive integers is graphic if it is the degree sequence of a simple graph, called in this case a {\em realization} of D. In this paper, we introduce the operation of 2-reduction, that subtracts 1 from two integers of D such that the resulting sequence D' is graphic if and only if D is graphic. We show that 2-reductions allow us to simply generate all the realizations of D, to prove existing characterizations of graphic sequences, as well as to propose new characterizations that highlight connections between mathematical and algorithmic aspects of graphic sequences.