Graphical Partition

A partition  is called graphical if there exists a graph  having degree sequence . The number of graphical partitions of length  is equal to the number of -node graphs that have no isolated points.

The numbers of distinct graphical partitions corresponding to graphs on , 2, ... nodes are 0, 1, 2, 7, 20, 71, 240, 871, 3148, ... (OEIS A095268).

A graphical partition of order  is one for which the sum of degrees is . A -graphical partition only exists for even .

It is possible for two topologically distinct graphs to have the same degree sequence, an example of which is illustrated above.

The numbers of graphical partitions  on , 4, 6, ... edges are 1, 2, 5, 9, 17, 31, 54, 90, 151, 244, ... (OEIS A000569).

Erdős and Richmond (1989) showed that

and

REFERENCES

Barnes, T. M. and Savage, C. D. "A Recurrence for Counting Graphical Partitions." Electronic J. Combinatorics 2, No. 1, R11, 1-10, 1995. http://www.combinatorics.org/Volume_2/Abstracts/v2i1r11.html.

Barnes, T. M. and Savage, C. D. "Efficient Generation of Graphical Partitions." Disc. Appl. Math. 78, 17-26, 1997.

Erdős, P. and Richmond, L. B. "On Graphical Partitions." Combinatorics and Optimization Research Report COPR 89-42.

Waterloo, Ontario: University of Waterloo, pp. 1-13, 1989.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 57, 1994.

Ruskey, F. "Information on Graphical Partitions." http://www.theory.csc.uvic.ca/~cos/inf/nump/GraphicalPartition.html.

Sloane, N. J. A. Sequences A000569, A002494/M1762, and A095268 in "The On-Line Encyclopedia of Integer Sequences."Wilf, H. "On Crossing Numbers, and Some Unsolved Problems." In Combinatorics, Geometry, and Probability: A Tribute to Paul Erdős. Papers from the Conference in Honor of Erdős' 80th Birthday Held at Trinity College, Cambridge, March 1993 (Ed. B. Bollobás and A. Thomason). Cambridge, England: Cambridge University Press, pp. 557-562, 1997.