A graphical partition is a partition degree
sequence of a simple graph degree sequences , listed in nonincreasing order,
realizable by vertex simple graphs
with no isolated vertices .
The numbers of distinct graphical partitions corresponding to graphs on A095268 ).
A graphical partition of order even
It is possible for two nonisomorphic graphs to have the same degree sequence , an example of
which is illustrated above.
The numbers A000569 ).
Writing partitions of partition function
P , Erdős and Richmond (1989, 1993) showed that, as even
integers ,
and
In fact, et al. 2021), so the proportion of partitions that are graphical
tends to zero.
See also Cut ,
Degree Sequence ,
Isolated Vertex ,
Spectral
Graph Partitioning
Explore with Wolfram|Alpha
References Barnes, T. M. and Savage, C. D. "A Recurrence for Counting Graphical Partitions." Elec. J. Combin. 2 , R11, 1995.
https://doi.org/10.37236/1205 . 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. Erdős,
P. and Richmond, L. B. "On Graphical Partitions." Combinatorica 13 ,
57-63, 1993. https://doi.org/10.1007/BF01202789 . Harary,
F. Graph
Theory. Melczer,
S.; Michelen, M.; and Mukherjee, S. "Asymptotic Bounds on Graphical Partitions
and Partition Comparability." Int. Math. Res. Not. 2021 , 2842-2860,
2021. https://doi.org/10.1093/imrn/rnaa251 . Ruskey,
F. "Information on Graphical Partitions." https://web.archive.org/web/20081208183914/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. S. "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 https://doi.org/10.1017/CBO9780511662034.049 . Referenced
on Wolfram|Alpha Graphical Partition
Cite this as:
Weisstein, Eric W. "Graphical Partition."
From MathWorld https://mathworld.wolfram.com/GraphicalPartition.html
Subject classifications
of positive integers that is the degree
sequence of a simple graph 
. The number of graphical partitions of length 
is the number of distinct positive degree sequences, listed in nonincreasing order,
realizable by 
-vertex simple graphs
with no isolated vertices.
, 2, ... nodes are 0, 1, 2, 7, 20, 71, 240, 871, 3148,
... (OEIS A095268).
is one for which the sum of degrees is 
. A 
-graphical partition only exists for even 
.
of graphical partitions with total degree 
, 4, 6, ... are 1, 2, 5, 9,
17, 31, 54, 90, 151, 244, ... (OEIS A000569).
for the fraction of partitions of 
that are graphical, where 
is the partition function
P, Erdős and Richmond (1989, 1993) showed that, as 
tends to infinity through even
integers,
(Melczer et al. 2021), so the proportion of partitions that are graphical
tends to zero.
