Score certificates for tournaments
Jeong Han Kim, Prasad Tetali, Peter C. Fishburn · Journal of Graph Theory · 1997
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 sizes of score certificates. 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 score certificate for T. This is best possible since every transitive tournament on n vertices has a score certificate with exactly n−1 arcs. © 1997 John Wiley & Sons, Inc.