Score certificate numbers of upset tournaments. (English) Zbl 0961.05029
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.
Reviewer: Wai-Kai Chen (Chicago)
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
References:
| [1] | Alon, N.; Ruszinkó, M., Short certificates for tournaments, Electron. J. Combin., 4, 12 (1997) · Zbl 0885.05067 |
| [2] | Brualdi, R.; Li, Q., Upsets in round robin tournaments, J. Combin. Theory B, 35, 62-77 (1983) · Zbl 0519.05033 |
| [3] | P. Fishburn, J.H. Kim, P. Tetali, Tournament certificates, Technical Memorandum, ATT Bell Laboratories, DIMACS Technical Report No. 94-05, 1994.; P. Fishburn, J.H. Kim, P. Tetali, Tournament certificates, Technical Memorandum, ATT Bell Laboratories, DIMACS Technical Report No. 94-05, 1994. |
| [4] | Kim, J. H.; Tetali, P.; Fishburn, P., Score certificates for tournaments, J. Graph Theory, 24, 117-138 (1997) · Zbl 0865.05044 |
| [5] | J.L. Poet, Score certificates for upset tournaments, Ph.D. Dissertation, University of Wyoming, 1998.; J.L. Poet, Score certificates for upset tournaments, Ph.D. Dissertation, University of Wyoming, 1998. · Zbl 0895.05026 |
| [6] | Poet, J. L.; Shader, B. L., Score certificates for upset tournaments, Electron. J. Combin., 5, 24 (1998) · Zbl 0895.05026 |
| [7] | Rubinstein, A., Why are certain properties of binary relations relatively more common in natural language?, Econometrica, 64, 353-355 (1996) · Zbl 0859.90010 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
