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

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
 
  k  
\
/   
i = 1
         
si    >   ( k
2
)
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:
[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, 10-May-2006 10:32:14 PDT.
There have been 3783 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.