## 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 [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [] the multigraphic sequences, while in the papers [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [] the dimultigraphic sequences have been discussed.

Even in the last two years many authors investigated the conditions when is multigraphical (e.g. [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []) or dimultigraphical (e.g. [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []).

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

In this chapter we deal first of all with directed graphs and usually follow the terminology used by K. B. Reid [], []. 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 [], [], Kapoor, Polimeni, and Wall [], and Tripathi et al. [], [] investigated the construction problem of a minimal size graph having a prescribed degree set [], []. In a similar way we follow a mini-max approach formulating the following questions: given a sequence of nonnegative integers,

• How to compute and how to construct a tournament characterized by ? In Subsection 25.5.3 a formula to compute , and in 25.5.4 an algorithm to construct a corresponding tournament is presented.

• How to compute and ? In Subsection 25.5.4 we characterize and , and in Subsection 25.5.5 an algorithm to compute and is described, while in Subsection 25.5.8 we compute and in linear time.

• How to construct a tournament characterized by and ? In Subsection 25.5.10 an algorithm to construct a corresponding tournament is presented and analyzed.

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