Score certificate numbers of upset tournaments (Q1570835)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Score certificate numbers of upset tournaments |
scientific article |
Statements
Score certificate numbers of upset tournaments (English)
0 references
28 May 2001
0 references
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.
0 references
digraph
0 references
tournament
0 references
score-list
0 references
score certificate
0 references