×

Score sets in multitournaments. I. Mathematical results. (English) Zbl 1289.68059

Summary: Let \(a\), \(b\), \(m\), and \(n\) be integers \((0 \leq a \leq b,\;1 \leq m \leq n)\). An \((a, b, n)\)-tournament [A. Iványi, Acta Univ. Sapientiae, Inform. 1, 71–88 (2009; Zbl 1178.68643)] is a directed loopless multigraph \(T = (V,A)\), where \(V = \{V_1,\dots, 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 non-decreasing sequence of its outdegrees and the score set \(D = \{d_1,\dots , d_m\}\) 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 M. Hager [Discrete Math. 58, 25–34 (1986; Zbl 0583.05029)]; 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 [K. B. Reid, Proc. 9th southeast. conference on combinatorics, graph theory, and computing, Boca Raton, 607–618 (1978; Zbl 0414.05022); T. X. Yao, Chin. Sci. Bull. 34, 804–808 (1989; Zbl 0687.05024)].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments