25.2. 25.2 Introduction to -tournaments

Let and be nonnegative integers and let be the set of such generalized tournaments, in which every pair of distinct players is connected by at least , and at most arcs. The elements of are called -tournaments. The vector of the outdegrees of is called the score vector of . If the elements of are in nondecreasing order, then is called the score sequence of .

An arbitrary vector of nonnegative integers is called multigraphic vector, (or degree vector) if there exists a loopless multigraph whose degree vector is , and is called dimultigraphic vector (or score vector) iff there exists a loopless directed multigraph whose outdegree vector is .

A nondecreasingly ordered multigraphic vector is called multigraphic sequence, and a nondecreasingly ordered dimultigraphic vector is called dimultigraphic sequence (or score sequence).

In there exists a simple graph, resp. a simple digraph with degree/out-degree sequence , then is called simply graphic, resp. digraphic.

The number of arcs of going from player to player is denoted by , and the matrix is called the point matrix or tournament of the .

In the last sixty years many efforts have been devoted to the study of both types of vectors, resp. sequences. E.g. in the papers [ 27 ], [ 71 ], [ 86 ], [ 96 ], [ 100 ], [ 103 ], [ 101 ], [ 109 ], [ 130 ], [ 131 ], [ 129 ], [ 139 ], [ 204 ], [ 250 ], [ 253 ], [ 260 ], [ 262 ], [ 276 ], [ 285 ] the multigraphic sequences, while in the papers [ 1 ], [ 12 ], [ 16 ], [ 27 ], [ 41 ], [ 78 ], [ 90 ], [ 91 ], [ 95 ], [ 98 ], [ 103 ], [ 111 ], [ 148 ], [ 149 ], [ 159 ], [ 171 ], [ 183 ], [ 184 ], [ 185 ], [ 189 ], [ 190 ], [ 197 ], [ 198 ], [ 199 ], [ 211 ], [ 236 ], [ 239 ], [ 243 ], [ 279 ], [ 284 ], [ 289 ] the dimultigraphic sequences have been discussed.

Even in the last two years many authors investigated the conditions when is multigraphical (e.g. [ 21 ], [ 31 ], [ 40 ], [ 54 ], [ 82 ], [ 83 ], [ 87 ], [ 84 ], [ 116 ], [ 121 ], [ 136 ], [ 147 ], [ 150 ], [ 151 ], [ 174 ], [ 178 ], [ 213 ], [ 216 ], [ 241 ], [ 274 ], [ 280 ], [ 282 ], [ 286 ], [ 287 ], [ 292 ]) or dimultigraphical (e.g. [ 23 ], [ 105 ], [ 127 ], [ 144 ], [ 152 ], [ 166 ], [ 188 ], [ 206 ], [ 228 ], [ 227 ], [ 229 ], [ 230 ], [ 245 ], [ 247 ], [ 270 ], [ 294 ]).

It is worth to mention another interesting direction of the study of different kinds of tournament, the score sets [ 217 ].

In this chapter we deal first of all with directed graphs and usually follow the terminology used by K. B. Reid [ 237 ], [ 239 ]. If in the given context and are fixed or non important, then we speak simply on tournaments instead of generalized or -tournaments.

The first question is: how one can characterize the set of the score sequences of the -tournaments? Or, with other words, for which sequences of nonnegative integers does exist an -tournament whose outdegree sequence is . The answer is given in Section 25.5.

If is an -tournament with point matrix , then let and be defined as follows: , , and . Let denote the set of all tournaments having as outdegree sequence, and let and be defined as follows: , , and . In the sequel we use the short notations , and .

Hulett, Will, and Woeginger [ 121 ], [ 288 ], Kapoor, Polimeni, and Wall [ 138 ], and Tripathi et al. [ 277 ], [ 274 ] investigated the construction problem of a minimal size graph having a prescribed degree set [ 233 ], [ 291 ]. In a similar way we follow a mini-max approach formulating the following questions: given a sequence of nonnegative integers,

We describe the proposed algorithms in words, by examples and by the pseudocode used in [ 57 ].