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