Score sets in multitournaments I. Mathematical results

Abstract. Let \(a\), \(b\), \(m\) and \(n\) be integers \((0 \leq a \leq b, \ 1 \leq m\leq n)\). An \((a,b,n)\)-tournament [9] is a directed loopless multigraph \(T = (V,A)\), where \(V = \{V_1, \ldots, V_n\}\) and if \(1 \leq i < j \leq n\), then \(V_i\) and \(V_j\) 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 = \{d_1,\ldots,d_m\}\) of \(T\) is the increasingly ordered set of its outdegrees. We propose four algorithms generating score sequences corresponding to any \(D:\ {\rm B{\small ALANCING}}\) reconstructs the majority of the score sets; \({\rm S{\small HORTENING}}\) reconstructs all score sets containing at most seven elements and so improves the theorem of Hager [7]; \({\rm S{\small EQUENCING}}\) finds a shortest score sequence corresponding to \(D\), while \({\rm D{\small IOPHANTINE}}\) generates all score sequences corresponding to \(D\). The algorithms are based on a new, extended version of the Reid–Yao theorem [25, 34].