Graphical Partitions

[Eric W. Weisstein]

On Tue, 30 May 2006, franktaw at netscape.net wrote:

> Sequences A000569 and A004250 are both described as "Number of graphical 
> partitions of 2n."  However, they are different.
> Likewise, from their descriptions A004251 and A095268 both appear to be the 
> number of distinct graphical partitions for a graph with n nodes; but again 
> they are different.

http://www.research.att.com/~njas/sequences/A004250 is the number of 
n-node graphical partitions (=simple graphs with no isolated points):

<< MathWorld`Graphs`
Length /@ (gp = Select[#, GraphicalPartitionQ] & /@
               Graphs /@ Range[9]) // Timing
{150.65 Second, {0, 1, 2, 7, 23, 122, 888, 11302, 262322}}

http://www.research.att.com/~njas/sequences/A095268 is the number of 
distinct degree sequences among the n-node graphical partitions:

Length/@Union/@Map[DegreeSequence,gp,{2}]
{0,1,2,7,20,71,240,871,3148}

> Which of these pairs is really what it claims to be; and what are the other 
> two?

http://www.research.att.com/~njas/sequences/A000569 is the number 
of graphical partitions on n edges:

Table[Count[RealizeDegreeSequence /@ Partitions[n], _Graph], {n, 2, 20, 
2}]
{1, 2, 5, 9, 17, 31, 54, 90, 151, 244}

See http://mathworld.wolfram.com/GraphicalPartition.html

Cheers,
-Eric