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 s1 < s2 < ... < sn of integers is a score sequence of a tournament if and only if
i = 1
si    >   ( k
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 Anum=A000571"> A000571(M1189) in

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:

It was last updated .