Score certificates for tournaments

✍ Scribed by Kim, Jeong Han; Tetali, Prasad; Fishburn, Peter

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 170 KB
• Volume: 24
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199702)24:2<117::aid-jgt1>3.0.co;2-t

✦ Synopsis

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.