Score certificate numbers of upset tournaments
type: Item
instance of: scholarly article
title: Score certificate numbers of upset tournaments
zbMATH Open document ID: 0961.05029
DOI: 10.1016/S0166-218X(99)00243-7
author: Jeffrey L. Poet
author: Bryan L. Shader
published in: Discrete Applied Mathematics
publication date: 2001-05-28T00:00:00Z
review text: 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.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1474735
zbMATH Keywords: digraph
zbMATH Keywords: tournament
zbMATH Keywords: score-list
zbMATH Keywords: score certificate
MaRDI profile type: Publication
cites work: Short certificates for tournaments
cites work: Upsets in round robin tournaments
cites work: Score certificates for tournaments
cites work: Short score certificates for upset tournaments
cites work: Why Are Certain Properties of Binary Relations Relatively More Common in Natural Language?
full work available at URL: s0166-218x(99)00243-7
OpenAlex ID: W2151287422
description: scientific article; zbMATH DE number 1474735