## DIMACS TR: 94-30

## Score Certificates for Tournaments

### Authors: Jeong Han Kim, Prasad Tetali and Peter Fishburn

**
ABSTRACT
**

The score of a vertex in a tournament is its out-degree. A score certificate
for a labeled tournament T is a labeled subdigraph D of T which together
with the score sequence of T allows errorless reconstruction of T. In
this paper we prove a general lower bound on the size of any (minimum) score
certificate. Our main theorem can be stated as follows: Except for the
regular tournaments on 3 and 5 vertices, every tournament T on n vertices
requires at least n - 1 arcs in a (minimum) score certificate for T. This
is best possible since every transitive tournament on n vertices has a score
certificate with exactly n - 1 arcs.

Paper only.

DIMACS Home Page