Information on Graphical Partitions

[Information Index] [Generation Index] [COS homepage]
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 A000569 in Neil J. Sloane's database of integer sequences.

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:
[Information Index] [Generation Index] [COS homepage]
Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 3097 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.