30.2. 30.2 Score sets in oriented graphs

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 .

Figure 30.9.  An oriented graph with score sequence An oriented graph with score sequence [1,3,3,5] and score set \{1,3,5\} . and score set An oriented graph with score sequence [1,3,3,5] and score set \{1,3,5\} ..

An oriented graph with score sequence [1,3,3,5] and score set \{1,3,5\} .


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
                
                
               
                  TO
                
                  3       4    
                  FOR
                
                
               
                  TO
                
                  5          6       
                  IF
                
                and    7                
               
                  //
                score sequence is computed   8     9    10  
                  FOR
                
                
               
                  TO
                
                 11    
                  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.

30.2.1. 30.2.1 Oriented graphs with prescribed scoresets

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 , respectively.

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( )

  1  
                     IF
                   
                     2       3    
                     RETURN
                   
                     4  
                     IF
                   
                     5    
                     IF
                   
                   and    6          7          8          9       add arcs to  such  10        dominates   11       
                     RETURN
                   
                    12    
                     IF
                   
                   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       
                     RETURN
                   
                   
               

30.2.1.1.  Algorithm description

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( )

  1  
                        IF
                      
                        2       3    
                        RETURN
                      
                        4  
                        ELSE
                      
                     
                     
                        Adding-Construction2(
                        
                        )
                        5       6    add arcs to  such that  dominates    7  
                        RETURN
                      
                      
                  

30.2.1.2.  Algorithm description

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( )

  1  
                        IF
                      
                        2    
                        IF
                      
                        3          4       
                        RETURN
                        5    
                        ELSE
                      
                        6       
                     
                        Arithmetic-Construction2(
                        
                        )
                        7          8       add arcs to  such that  dominates    9       
                        RETURN
                       10  
                        IF
                      
                      and   11    
                        IF
                      
                      is odd  12         13       choose two vertices and change the direction of the arc between them  14       
                        RETURN
                      
                       15    
                        ELSE
                      
                       16         17         18       add arcs to  such that  dominates   19       
                        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.