## Information on Score Sequences

A *tournament* is a complete graph in which every edge has a orientation.
On the left we show a tournament on 5 vertices. Each vertex
is labeled with its corresponding out-degree.
A *score sequence* of a tournament is a monotonically non-decreasing
sequence of the out-degrees of its vertices.
For the tournamant shown here the score sequence is
1 1 2 2 4.

Score sequences do not characterize tournaments; there are non-isomorphic
tournaments with the same score sequence.
There is an elegent characterization of score sequences due to
H. G. Landau (*On dominance relations and the
structure of animal societies, III. The condition for a score
structure.*, Bulletin for Mathematical Biophysics, 15 (1953)
143-148.), namely that a sequence
*s*_{1} __<__ *s*_{2} __<__ ...
__<__
*s*_{n}
of integers is a score sequence of a tournament if and only if

for *k* = 1,2,...,*n*, with equality holding for *k* =
*n*.
The number of score sequences for *n* = 1,2,...,15, is
1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805,
158808, 531469.
This is sequence
**A000571**(M1189) in
Neil J. Sloane's
database
of integer sequences.

The algorithm used for generating score sequences 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.
The paper can be downloaded from Frank Ruskey's
publications page.

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, 10-May-2006 10:32:14 PDT.

There have been 3783 visitors to this page since May 16, 2000
.

©Frank Ruskey, 1995-2003.