Degree Sequence

Given an undirected Graph, a degree sequence is a monotonic nonincreasing sequence of the degrees of its Vertices. A degree sequence is said to be $k$-connected if there exists some $k$-Connected Graph corresponding to the degree sequence. For example, while the degree sequence $\{1, 2, 1\}$ is 1- but not 2-connected, $\{2, 2, 2\}$ is 2-connected. The number of degree sequences for $n=1$, 2, ... is given by 1, 2, 4, 11, 31, 102, ... (Sloane's A004251).

See also Graphical Partition

References

Ruskey, F. ``Information on Degree Sequences.'' http://sue.csc.uvic.ca/~cos/inf/nump/DegreeSequences.html.

Ruskey, F.; Cohen, R.; Eades, P.; and Scott, A. ``Alley CATs in Search of Good Homes.'' Congres. Numer. 102, 97-110, 1994.

Sloane, N. J. A. Sequence A004251/M1250 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.