Efficient Generation of Graphical Partitions

Given a positive even integer n, we show how to generate the set G(n) of graphical partitions of n, that is, those partitions of n which correspond to the degree sequences of simple, undirected graphs. The algorithm is based on a recurrence for G(n), and the total time used by the algorithm, independent of output, is O(jG(n)j), which is constant average time per graphical partition. This is the first algorithm shown to achieve such efficiency for generating G(n) and the direct approach differs from earlier "generate and reject" schemes and the "interval/gap" approach. 1 Introduction A partition of a positive integer n is a sequence = ( 1 ; 2 ; : : : ; l ) of positive integers satisfying 1 2 : : : l and 1 + 2 + : : :+ l = n. A partition of an even integer n is called graphical if it is the degree sequence of some simple undirected graph. For example, = (5; 4; 4; 3; 3; 1) is graphical, whereas = (5; 4; 4; 2; 2; 1) is not. We let G(n) denote the set of graphical part..