TOPICS

# 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

Cut, Degree Sequence, Isolated Point, Spectral Graph Partitioning

## Explore with Wolfram|Alpha

More things to try:

## 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.

## Referenced on Wolfram|Alpha

Graphical Partition

## Cite this as:

Weisstein, Eric W. "Graphical Partition." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphicalPartition.html