Premium
Score certificates for tournaments
Author(s) -
Kim Jeong Han,
Tetali Prasad,
Fishburn Peter
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199702)24:2<117::aid-jgt1>3.0.co;2-t
Subject(s) - tournament , combinatorics , mathematics , certificate , vertex (graph theory) , transitive relation , discrete mathematics , algorithm , graph
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.