A recurrence for counting graphical partitions (Q1890828)

Summary: We give a recurrence to enumerate the set \(G(n)\) of partitions of a positive even integer \(n\) which are the degree sequences of simple graphs. The recurrence gives rise to an algorithm to compute the number of elements of \(G(n)\) in time \(O(n^ 4)\) using space \(O(n^ 3)\). This appears to be the first method for computing \(| G(n)|\) in time bounded by a polynomial in \(n\), and it has enabled us to tabulate \(| G(n)|\) for even \(n\leq 220\).