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.
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
//score sequence is computed 8 9 10
//is the found score new? 12 13 14
The running time of
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.
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.
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
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.
IFand 6 7 8 9 add arcs to such 10 dominates 11
IFand 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
IFand 24 25 26 27 add arcs to such 28 dominates 29
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
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:
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
, 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
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.
)5 6 add arcs to such that dominates 7
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
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,
is valid for all .
The analysis of computational complexity of
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.
The proof is left as an exercise (see Exercise 30.2-10), but we present the construction algorithm
based on this theorem. The input data are , and , satisfying the conditions of Theorem 30.7.
)7 8 add arcs to such that dominates 9
IFis odd 12 13 choose two vertices and change the direction of the arc between them 14
ELSE16 17 18 add arcs to such that dominates 19
30.2-6 Give a proof of Lemma 30.6.
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.