Information on Degree Sequences

A degree sequence of an undirected graph graph is a monotonically non-increasing sequence of the degrees of its vertices. For the graph shown here the Degree Sequence is 4 4 3 3 2 2.

A degree sequence has connectivity k if there is some k-connected graph with that degree sequence. For example, 0 0 0 is not 1-connected, 1 2 1 is 1-connected but not 2-connected, and 2 2 2 is 2-connected. Characterizations of degree sequences may be found in the paper Alley CATs in search of good homes, Section 3, and of k-connected degree sequences in the paper Alley CATs in search of good homes, Section 3.1.

The number of degree sequences for n = 1,2,...,15, is 1, 2, 4, 11, 31, 102, 342, 1213, 4361, 16016, 59348, 222117, 836315, 3166852, 12042620. This is sequence Anum=A004251"> A004251(M1250) in

The number of degree sequences of connected graphs for n = 2,3,...,15, is 1, 2, 6, 19, 68, 236, 863, 3137, 11636, 43306, 162728, 614142, 2330454 This is sequence Anum=A007721"> A007721 in

The number of degree sequences of biconnected graphs for n = 3,4,...,15, is 1, 3, 9, 34, 125, 473, 1779, 6732, 25492, 96927, 369463, 1412700. This is sequence Anum=A007722"> A007722 in

The algorithm used is from the paper: F. Ruskey, R. Cohen, P. Eades, and A. Scott, Alley CATs in search of good homes, Congressus Numerantium, 102, pp. 97-110.


Programs available:


It was last updated .