## 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:

**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.