[Information Index] [Generation Index] [COS homepage]

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 A004251(M1250) in Neil J. Sloane's database of integer sequences.

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 A007721 in Neil J. Sloane's database of integer sequences.

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 A007722 in Neil J. Sloane's database of integer sequences.

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:
[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 30-Aug-2006 17:45:10 PDT.
[Error Opening Counter File -- Click for more info]
©Frank Ruskey, 1995-2003.