TOPICS
Search

Graphical Partition

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

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

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

GraphicalPartitions22211

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

GraphicalPartitions

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

Erdős and Richmond (1989) showed that

lim inf_(n->infty)sqrt(n)p_g(n)>=pi/(sqrt(6))

and

lim sup_(n)p_g(n)<=0.4258.

See also

Cut, Degree Sequence, Isolated Point, Spectral Graph Partitioning

Explore with Wolfram|Alpha

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

Subject classifications