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
The numbers of distinct graphical partitions corresponding to graphs on , 2, ... nodes are 0, 1, 2, 7, 20, 71, 240, 871, 3148, ...
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
, Degree Sequence
, Isolated Point
Explore with Wolfram|Alpha
ReferencesBarnes, 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,
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|AlphaGraphical Partition
Cite this as:
Weisstein, Eric W. "Graphical Partition."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphicalPartition.html