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