Score sets in multitournaments I. Mathematical results
Antal Iványi, Loránd Lucz, Tamás Matuszka, Gergő Gombos · Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae Sectio computatorica · 2013
Let a, b, m, and n be integers (0An (a, b, n)-tournament [9] is a directed loopless multigraph T = (V, A), where V = {V1, . . ., Vn} and if 1 ≤ i < j ≤ n, then Vi and Vj are connected with at least a and at most b arcs.The score sequence of T is the nondecreasing sequence of its outdegrees and the score set D = {d1, . . ., dm} of T is the increasingly ordered set of its outdegrees.We propose four algorithms generating score sequences corresponding to any D: Balancing reconstructs the majority of the score sets; Shortening reconstructs all score sets containing at most seven elements and so improves the theorem of Hager [7]; Sequencing finds a shortest score sequence corresponding to D, while Diophantine generates all score sequences corresponding to D. The algorithms are based on a new, extended version of the Reid-Yao theorem [25,34].