Information on Graphical Partitions


A graphical partition of order n is the degree sequence of a graph with n/2 edges and no isolated vertices. For example, when n = 6 there are five graphical partitions: 111111, 21111, 2211, 222, 3111. In this case, the five partitions correspond to the five non-isomorphic graphs on 3 edges (isolated vertices forbidden), but in general different graphs could have the same graphical partition.

For n=2,4,6,...,30 the number of graphical partitions is 1, 2, 5, 9, 17, 31, 54, 90, 151, 244, 387, 607, 933, 1420, 2136. This is sequence Anum=A000569"> A000569 in

The program that produces this output is derived from one kindly supplied to us by Carla Savage. Her program is based on an algorithm described in the paper: T.M. Barnes and C.D. Savage, Efficient Generation of Graphical Partitions, submitted manuscript, 1995. See also the paper: T.M. Barnes and C.D. Savage, A recurrence for counting graphical partitions, Electronic Journal of Combinatorics, 2, 1995, #R11.

Further information can be obtained from Eric Weinstein's World of Mathematics.


Programs available:


It was last updated .