Score certificate numbers of upset tournaments
A tournament \(T\) is a directed graph on a finite vertex set. The score-list of \(T\) is the multiset of the outdegrees of its vertices. The score certificate of \(T\) is a collection of arcs of \(T\), which can be uniquely completed to a tournament with the same score-list as \(T\)'s. The score certificate number of \(T\) is the least number of arcs in a score certificate of \(T\). The paper establishes the lower and upper bounds for the score certificate numbers of the class of upset tournaments. Notice that the lower and upper bounds differ by at most 2.
scientific article; zbMATH DE number 1474735