Oriented graphs are generalizations of tournaments. Formally, an **oriented graph**
with vertex set and arc set is a digraph with no symmetric pairs of directed arcs and without loops. In other words oriented graph is a directed graph in which every pair of different vertices is connected with at most one arc, or oriented graphs are -*tournaments*. Figure 30.9 shows an oriented graph with score sequence and the coressponding score set .

Thus tournaments are complete oriented graphs, in the sense that any pair of vertices in a tournament is joined exactly by one arc. Several concepts defined for tournaments can be extended in a meaningful way to oriented graphs. For example score of a player (vertex) in a tournament is defined as its out-degree, as a player either wins (and earns one point) or looses (earning no points) a two-way clash. In 1991, Peter Avery introduced the score structure for oriented graphs based on the intuition that in a round-robin competition with ties allowed, a player may earn two, one or no points in case the player wins, looses or makes a tie respectively.

More precisely, the score of a vertex in a -tournament with vertices is defined as

where and are the out-degree and in-degree, respectively, of . The score sequence of an oriented graph is formed by listing the vertex scores in non-decreasing order. If we denote the number of non-arcs in containing the vertex as , then

With this score structure, an oriented graph can be interpreted as the result of a round-robin competition in which ties (draws) are allowed, that is, the players play each other once, with an arc from player to if and only if defeats . A player receives two points for each win, and one point for each tie.

It is worth to remark that this is a sophisticated score structure comparing with the simple and natural structure of 2-tournaments.

Avery gave a complete characterization of score sequences of oriented graphs similar to Landau's theorem.

**Theorem 30.3 **(Avery, 1991) *A nondecreasing sequence of nonnegative integers is the score sequence of an oriented graph if and only if*

*for with equality when .*

**Proof. **This theorem is a special case of the theorem proved by Moon in 1963 or the theorem proved by Kemnitz and Dulff in 1997 (see the theorem and its proof in chapter *Comparison Based Ranking* of this book).

Just as in the case of 1-tournaments, the **score set of an oriented graph** is defined as the set of scores of its vertices. It is worth noting that a -tournament has different score sets under Avery's and Landau's score structures. In fact, the score of a vertex under Avery's score structure is twice the score of under Landau's score structure. This is obviously due to Avery's assumption that a win contributes 2 points to the score.

The score set of an oriented graph can be determined by adapting *
Quick-Set2
* as follows:

*
Quick-Set2(
)
*

1 2`FOR`

3 4`TO`

`FOR`

5 6`TO`

and 7`IF`

score sequence is computed 8 9 10`//`

`FOR`

11`TO`

`IF`

is the found score new? 12 13 14`//`

`RETURN`

The running time of *
Quick-Set2
* is since the nested loop in lines 02–07 requires the remaining lines require time.

In Section 30.2 we discussed score sets of tournaments and noted that every non-empty set of nonnegative integers is the score set of some tournament. In this section we study the corresponding question for oriented graphs, i.e., which sets of nonnegative integers can arise as score sets of oriented graphs. Pirzada and Naikoo investigated this question and gave two sufficient conditions for a set of nonnegative integers to be the score set of some oriented graph.

**Theorem 30.4 **(Pirzada, Naikoo, 2008) *Let nonnegative integers, and , with or and . Then there exists an oriented graph with score set except for and for .*

**Theorem 30.5 **(Pirzada, Naikoo, 2008) *If is a positive integer and are nonnegative integers with , then there exists an oriented graph with vertices and with score set , where*

Thus any set of positive integers whose elements form a geometric progression is the score set of some oriented graph with few exceptions and any set of nonnegative integers whose elements are of the form (30.5) is also a score set. It follows that every singleton set of nonnegative integers is the score set of some oriented graph. On the other hand, for any positive integer , the sets and cannot be the score sets of an oriented graph. Therefore, unlike in the case of tournaments, not all sets of nonnegative integers are score sets of oriented graphs. So far no complete characterization of score sets of oriented graphs is known.

The proof of Theorem 30.4 depends on the following auxiliary assertion.

**Lemma 30.6 **(Naikoo, Pirzada, 2008) *The number of vertices in an oriented graph with at least two distinct scores does not exceed its largest score.*

**Proof. **This assertion is the special case of Lemma 30.10 due to Iványi and Phong.

Here we omit formal proofs of Theorems 30.4 and 30.5 since they can be found on the internet and since we will implicitly prove these theorems when we check the correctness of *
Geometric-Construction2
* and

`Adding-Construction2`

We first present a recursive algorithm that takes positive integers , , and , satisfying the condition of Theorem 30.4, as input and generates a 2-tournament with score set . Let denote the null digraph on vertices, i.e., the digraph with vertices and no arcs.

*
Geometric-Construction2(
)
*

12 3`IF`

4`RETURN`

5`IF`

and 6 7 8 9 add arcs to such 10 dominates 11`IF`

12`RETURN`

and 13 with vertex set 14 with vertex set 15 with vertex set 16 17 add arcs to such that 18 for 19 for 20 21 22 for 23`IF`

and 24 25 26 27 add arcs to such 28 dominates 29`IF`

`RETURN`

If , then the algorithm returns the null digraph . Note that is well-defined as . Each vertex of has score . Therefore the score set of is . Thus the algorithm is correct for .

If , then four cases arise.

Case i). If and , then and . Construct an oriented graph with vertex set , where , , and . Then has vertices and the different scores are and .

Case ii). If and . Construct an oriented graph with vertex set and and arc set . The score set of is .

case iii). If and , then with vertex set , where , , and . Then the scores are for all and for all .

Now we prove the correctness of *
Geometric
* by induction. That is, we show that if the algorithm is valid for for some integer then it is also valid for . Let and be positive integers with and such that for , . By the induction hypothesis the algorithm can construct an oriented graph with score set and are the distinct scores of the vertices of . Let be the vertex set of .

There are three possibilities:

and ,

and or

and .

Obviously, for in all the above cases we have . Also the score set of , namely , has at least two distinct scores for . Therefore, by Lemma 30.6 we have . Hence so that .

Let be the null digraph with vertex set . The algorithm now generates the vertex and arc disjoint union and adds an arc directed from each vertex in to every vertex of . The output of *
Geometric-Construction2
*, therefore, has vertices. Moreover, , . are the distinct scores of the vertices in , while for all vertices .

Therefore the score set of is which shows that the algorithm works for . Hence the algorithm is valid for all , and satisfying the hypothesis of Theorem 30.4.

The recursive procedure *
Geometric
* runs times and during its run the procedure adds arcs to the oriented graph . The overall complexity of the algorithm is therefore .

As noted in Theorem 30.4, there exists no 1-tournament when either or . It is quite interesting to investigate these exceptional cases as it provides more insight into the problem.

Let us assume that is a score set of some oriented graph for . Then there exist positive integers, say such that

is the score sequence of . Therefore, by relations (30.4) of score sequences of 1-tournaments, we have

which implies that is even. However, is a positive integer, therefore . Let the scores be , and . By inequalities (30.4) , or in other words, . This implies that , a contradiction.

The proof of the other exceptional case () is left as an exercise (Exercise 30.2-1).

Let for . The next algorithm takes the set consisting of nonnegative integers as input and recursively constructs an oriented graph with the score set where the scores are of the form 30.5.

*
Adding-Construction2(
)
*

12 3`IF`

4`RETURN`

`ELSE`

5 6 add arcs to such that dominates 7`Adding-Construction2(`

`)`

`RETURN`

If , the algorithm returns the null digraph . Each vertex of has the score . Therefore the score set of is as required.

We prove the correctness of *
Adding-Construction2
* in general by induction on . Assume that the algorithm is valid for , for some integer . We show that the algorithm is also valid for . Let be nonnegative integers with . Since , by the induction hypothesis, the algorithm returns an oriented graph on vertices with score set , where is given by equations (30.5). That is, score set of is . So , , are the distinct scores of the vertices of . Let be the vertex set of so that . Since , , the algorithm constructs a new oriented graph with vertex set , where is the vertex set of and . Arcs are added to such that there is an arc directed from each vertex in to every vertex in . Thus has vertices. The distinct score of vertices in are , while for all .

Therefore the score set of is which proves the validity of algorithm for . Hence by induction, *
Adding-Construction2
* is valid for all .

The analysis of computational complexity of *
Adding-Construction2
* is left as an exercise (Exercise 30.2-3).

Substituting , and into 30.9 we get , that is there is not oriented graph with a score set , therefore the following natural extension of the asertion due to Reid on the arithmetic progressions and score sets of tournaments is not true: “Every arithmetical progression is a the score set of some oriented graph.” But we formulate a bit weaker assertion.

**Theorem 30.7 **(Iványi, 2011) *If and are positive integers, is a nonnegative integer, further either or , then is a score set of some oriented graph.*

The proof is left as an exercise (see Exercise 30.2-10), but we present the construction algorithm *
Arithmetic-Construction
* based on this theorem. The input data are , and , satisfying the conditions of Theorem 30.7.

*
Arithmetic-Construction2(
)
*

12`IF`

3 4`IF`

5`RETURN`

6`ELSE`

7 8 add arcs to such that dominates 9`Arithmetic-Construction2(`

`)`

10`RETURN`

and 11`IF`

is odd 12 13 choose two vertices and change the direction of the arc between them 14`IF`

15`RETURN`

16 17 18 add arcs to such that dominates 19`ELSE`

`RETURN`

**Exercises**

30.2-1 Prove that there exists no oriented graph with score set for any .

30.2-2 Prove that if and , then .

30.2-3 *
Adding-Construction2
* is a recursive algorithm. Analyse its running time and compare its performance with the performance of

`Geometric-Construction`

30.2-4 Implement *
Adding-Construction2
* in a suitable programming language and use it to construct an oriented graph with score set . Write the score sequence of your oriented graph.

30.2-5 Implement *
Adding-Construction2
* in a suitable programming language and use it to construct an oriented graph with score set . Write the score sequence of your oriented graph.

30.2-6 Give a proof of Lemma 30.6.

30.2-7 For any nonnegative integer , what is the score set of the regular tournament when considered as an oriented graph.

30.2-8 Determine the score set of the oriented graph , where dominates , i.e., there is an arc directed from every vertex of to every vertex of .

30.2-9 Write an algorithm to determine the score set of directed cycles (i.e., cycles with directed edges). How can we make this algorithm work for directed wheels (note that a *wheel* is a cycle with an additional vertex joined to all the vertices on the cycle).

30.2-10 According to Theorem 30.7 the majority of arithmetic progression is the score set of some oriented graph. Prove this theorem.