30.5. 30.5 Weak kings in oriented graphs

In the previous section we studied dominance in tournaments and used the terms kings and strong kings to describe the dominant vertices in a tournament. However, in most practical applications the underlying digraph is not a tournament. Rather we are interested in determining dominant vertices in an oriented graph. For instance, in a social network, an arc denotes that actor has some relation with actor . Since most social relations (such as hierarchy relations) are irreflexive and asymmetric, a majority of social networks can be modelled as oriented graphs. Therefore, we would like to generalize the concept of dominance from tournaments to oriented graphs. In Section 30.4, we have already defined kings and -kings in the context of general digraphs. The same definitions are applicable to oriented graphs.

As stated in the beginning of the chapter, oriented graphs can be considered as round-robin competitions in which ties are allowed. Thus the the classical notion of king, that is a vertex that defeats every other vertex either directly or through another vertex, is too strong for oriented graphs. To overcome this difficulty, the study of the so-called “weak kings” was initiated in 2008 by S. Pirzada and N. A. Shah. Here we follow their notation. For any two vertices and in an oriented graph , one of the following possibilities exist.

  1. An arc directed from to , denoted by (i.e., defeats ).

  2. An arc directed from to , denoted by (i.e., defeats ).

  3. There is no arc from to or from to , and is denoted by (i.e., there is a tie).

A triple in an oriented graph is an induced oriented subgraph with three vertices. For any three vertices , and , the triples of the form , , or are said to be intransitive, while the triples of the form , , , , , , , , , , , , , or are said to be transitive. An oriented graph is said to be transitive if all its triples are transitive. The converse of an oriented graph is obtained by reversing each arc of .

Let and be vertices in an oriented graph such that either or or or or for some vertex in . Then is said to be weakly reachable within two steps from . If either , or for some in , then is reachable within two steps from .

A vertex in an oriented graph is called a weak king if every other vertex in is weakly reachable within two steps from . A vertex is called a king if every other vertex in is reachable within two steps from . A vertex in an oriented graph is called a weak serf if is weakly reachable within two steps from every other vertex in , and a vertex in is called a serf if is reachable within two steps from every other vertex in .

Figure 30.13.  Six vertices and six weak kings.

Six vertices and six weak kings.

Figure 30.14.  Six vertices and five weak kings.

Six vertices and five weak kings.

Figure 30.15.  Six vertices and four weak kings.

Six vertices and four weak kings.

Figure 30.16.  Six vertices and three weak kings.

Six vertices and three weak kings.

Figure 30.17.  Six vertices and two weak kings.

Six vertices and two weak kings.


We note that there exist oriented graphs on vertices with exactly kings for all integers , with the exception of . Theorem 30.18 guarantees the existence of complete oriented graphs (tournaments) with vertices and exactly kings for all integers , with the exceptions and . An oriented graph with exactly two kings can be constructed as follows. Let be the vertex set of , with arcs defined as , for ; ; and , for ; and for all other , . The vertices and are the only kings in (Exercise 30.5-1).

There do not exist any complete or incomplete oriented graphs with 4 vertices and exactly 4 kings. Suppose to the contrary that this is the case and let be the incomplete oriented graph with 4 vertices, all of whom are kings. Then can be extended to a tournament on 4 vertices by inserting all the missing arcs with arbitrary orientation. Clearly such a tournament contains 4 kings, which contradicts Theorem 30.18.

The rest of the section is aimed at investigating weak kings in oriented graphs as they present a more suitable notion of dominance in oriented graphs. The score of a vertex in an oriented graph was defined in Section 30.2. Considering Theorem 30.16, it is natural to ask if a vertex of maximum score in an oriented graph is a king. The answer is negative as shown by the following example:

Example 30.3 Consider the oriented graph shown in Figure 30.18. The scores of vertices , , and are respectively 2, 3, 3 and 4. Clearly, is a vertex of maximum score but is not a king as is not reachable within two steps from . However, is a weak king.

Figure 30.18.  Vertex of maximum score is not a king.

Vertex of maximum score is not a king.

Now consider the oriented graph with vertices , , , and , and arcs defined by , , for and for all other . Clearly, , , , , and . Evidently, is a king in whereas the vertex of maximum score is not a king.

However, we do have the following weaker result.

Theorem 30.21 If is a vertex with maximum score in a 2-tournament , then is a weak king.

Proof. Let be a vertex of maximum score in , and let , and be respectively the set of vertices , , and such that , , and . Let , and . Clearly, . If , the result is trivial. So assume that . We claim that each is weakly reachable within two steps from . If not, let be a vertex in not weakly reachable within two steps from . Then for each and each , , and or . In case and for each and each , then which contradicts the choice of . If and for each and each , then , again contradicting the choice of . This establishes the claim, and hence the proof is complete.

We now consider the problem of finding all weak kings in an oriented graph (as kings can be determined by applying Algorithm KingSet1 ). Let and respectively denote the in-degree and out-degree matrix of an oriented graph with vertices. Also let and denote the zero matrix and all-ones matrix respectively.

Weak-Kings( )

  1     2     3     4  
                  FOR
                
                
               
                  TO
                
                and  
               
                  TO
                
                  5    
                  FOR
                
                
               
                  TO
                
                  6       
                  IF
                
                  7             8       
                  ELSE
                
               
                  IF
                
                  9               10    11    12    13    14  
                  RETURN
                
                
            

Algorithm WeakKings returns the set of all weak kings of an oriented graph. Exercise 30.5-3 asks you to prove that the algorithm works correctly and to determine its running time.

Indeed, it is also possible to extend Theorem 30.17 to weak kings in oriented graphs as an oriented graph without transmitters (vertices of in-degree 0) has at least three weak kings. To see this let be a vertex of maximum score in the oriented graph . Clearly, by Theorem 30.21, is a weak king. As has no transmitters, there is at least one vertex such that . Let be the set of these vertices , and let be a vertex of maximum score in . Let , and respectively be the set of vertices , and , other than , with , and . Assume that , , and so that . We note that all vertices of are weakly reachable within two steps from . If this is not the case, let be a vertex which is not weakly reachable within two steps from . Then , and (a) and (b) or for each and each .

If for each in and each in , and , then . This contradicts the choice of . If for each in and each in , and , then , again contradicting the choice of . This establishes the claim, and thus is also a weak king. Now let be set of vertices with and let be the vertex of maximum score in . Then by the same argument as above, every other vertex in is weakly reachable within two steps from , and so is a weak king. Since is asymmetric, and in we have and , therefore , and are necessarily distinct vertices. Hence contains at least three weak kings.

Although, no oriented graph with 4 vertices and exactly 4 kings exists, it is possible to generate an oriented graph on vertices with exactly weak kings, for all integers . The following algorithm constructs such an oriented graph.

-Weak-Kings( )

  1     2     3  
                  IF
                
                  4    
                  FOR
                
                
               
                  TO
                
                  5          6          7          8    
                  FOR
                
                
               
                  DOWNTO
                
                  9         10    
                  FOR
                
                
               
                  DOWNTO
                
                 11         12      13    
                  ELSE
                
               
                  IF
                
                 14       
                  FOR
                
                
               
                  TO
                
                 15            16            17       
                  FOR
                
                
               
                  TO
                
                 18          
                  IF
                
                 19               20         21       
                  ELSE
                
                 22            23          
                  FOR
                
                
               
                  TO
                
                 24               25               26               27            28  
                  RETURN
                
                
            

Algorithm description

When , the algorithm defines the arcs of a 2-tournament with vertex set as

,

and for all ,

for all and , ,

Clearly, is a weak king as and for all . Also is a weak king as and for all . Finally, every is a weak king, since , for all and and . Thus contains exactly weak kings.

If , the algorithm creates one additional arc in . The resulting oriented graph contains exactly weak kings, since now is not weakly reachable within two steps from and so is not a weak king. If then the algorithm creates two additional arcs in . namely and . Thus now contains exactly weak kings, with and not being weak kings.

Continuing in this way, for any , the algorithm creates new arcs in for all . The resulting graph contains exactly weak kings.

If , then is constructed so that , . and for all , and . Thus contains exactly two weak kings and .

Finally, has exactly one weak king if it is constructed such that , , and , and for all .

Due to the nested fOR loops the algorithm runs in time.

Figure 30.13 shows a 6 vertex oriented graph with exactly 6 weak kings, Figure 30.14 shows a 6 vertex oriented graph with exactly 5 weak kings namely , , , and , Figure 30.15 shows a 6 vertex oriented graph with exactly 4 weak kings namely , . and . Figure 30.16 shows a 6 vertex oriented graph with exactly 3 weak kings namely , and and Figure 30.17 shows a 6 vertex oriented graph with exactly 2 weak kings namely and .

The directional dual of a weak king is a weak serf, and thus a vertex is a weak king of an oriented graph if and only if is a weak serf of , the converse of . So by duality, there exists an oriented graph on vertices with exactly weak serfs for all integers . If , then every vertex in any such oriented graph is both a weak king and a weak serf. Also if , the oriented graph described in algorithm WeakKings contains vertices which are both weak kings and weak serfs, and also contains vertices which are weak kings but not weak serfs and vice versa. These ideas give rise to the following problem. For what 4-tuples does there exist an oriented graph with vertices, exactly weak kings, weak serfs and that exactly of the weak kings are also serfs? By analogy with -tournaments, such oriented graphs are called -oriented graphs. Without loss of generality, we assume that . The following results by Pirzada and Shah address this problem.

Theorem 30.22 (Pirzada, Shah, 2008) If , then there exists no -oriented graph.

Theorem 30.23 (Pirzada, Shah, 2008) There exist -oriented graphs, and , .

Proof. Let be the oriented graph with vertex set and , , for all , and for all .

Take the oriented graph with vertex set and arcs defined as in . Let be the oriented graph with vertex set and for all . Let be the oriented graph (see Figure 30.19) with

for

for

for ,

, for

for ,

,

for

,

, for , .

Figure 30.19.  Construction of an Construction of an (n,k,s,b) -oriented graph.-oriented graph.

Construction of an (n,k,s,b) -oriented graph.

Clearly contains exactly weak kings and the weak king set is . contains exactly weak serfs with the weak serf set as . Also from these weak kings, exactly are weak serfs. The weak king-serf set is .

Exercise 30.5-5 asks the reader to derive an algorithm for generating an -oriented graph when the hypothesis of Theorem 30.23 is satisfied.

Exercises

30.5-1 Give an algorithm that generates an oriented graph with vertices and exactly 2 kings. Prove the correctness of your algorithm.

30.5-2 Draw the graph discussed in Example 30.3.

30.5-3 Prove that Weak-Kings2 is correct. Also determine its runtime.

30.5-4 Construct an oriented graph with six vertices and exactly one king.

30.5-5 Derive an algorithm that takes a 4-tuple satisfying the hypothesis of Theorem 30.23 as input and generates an -oriented graph. Analyze the performance of your algorithm.

  PROBLEMS  

30-1 Optimal reconstruction of score sets

In connection with the reconstruction of graphs the basic questions are the existence and the construction of at least one corresponding graph. These basic questions are often solvable in polynomial time. In given sense optimal reconstruction is usually a deeper problem.

a) Analyse Exercise 30.1-1 and try to find a smaller tournament with score set .

b) Write a back-track program which constructs the smallest tournament whose score set is .

c) Write a back-track program which constructs the smallest tournament arbitrary given score set.

d) Estimate the running time of your programmes.

Hint. Read Yao's proof [ 291 ].

30-2 Losing set

We define the losing score of a vertex as the in-degree of the vertex. The loosing score set of a tournament is the set of in-degrees of its vertices.

a) Give an argument to show that any set of nonnegative integers is the loosing score set of some tournament.

b) Given a set of nonnegative integers with , write an algorithm to generate a tournament with loosing score set .

30-3 Imbalance sets and score sets

Compare the existence and construction results of score sets and imbalance sets.

30-4 Unicity of imbalance sets

Find imbalance sets of different types of graphs which determine the corresponding score vector in a unique way.

30-5 Score sequences of bipartite graphs

Find a condition for two -length sequences of nonnegative integers to be the score sequence pair of an -bipartite graph.

  CHAPTER NOTES  

Many classical ans several contemporary graph theory textbooks are available to Readers. Such books are e.g. the books of Dénes Kőnig [ 156 ], Claude Berge [ 27 ] and László Lovász [ 165 ]. However, there is a dearth of books focusing on recent advances in the theory of digraphs. The book due to Bang-Jensen and Gutin [ 17 ] probably comes closest and the Reader can refer to it for a comprehensive treatment of the theoretical and algorithmic aspects of digraphs.

The books by Harary, Norman and Cartwright [ 104 ], and Chartrand, Lesniak and Zhang [ 47 ], [ 48 ], Gross and Yellen [ 97 ] present introductory material on tournaments and score structures. Moon's book on tournaments [ 185 ] is also a good resource but is now out of print.

The books A. Schrijver [ 249 ] and A. Frank [ 85 ] contain reach material on optimization problems connected with directed graphs.

The algorithms discussed in this chapter are not commonly found in literature. In particular the algorithms presented here for constructing tournaments and oriented graphs with special properties are not available in textbooks. Most of these algorithms are based on fairly recent researchs on tournaments and oriented graphs.

Majority of the researches connected with score sequences and score sets were inspired by the work of H. G. Landau, K. B. Reid and J. W. Moon. For classical and recent results in this area we refer to the excellent surveys by Reid [ 233 ], [ 236 ], [ 237 ]. Landau's pioneering work on kings and score structure appeared in 1953 [ 159 ]. Reid stated his famous score set conjecture in [ 233 ]. Partial results were proved by M. Hager [ 99 ]. Yao's proof of Reid's conjecture appeared in English in 1989 [ 291 ]. The comment of Q. Li on Reid's conjecture and Yao's proof was published in 2006 [ 161 ]. The construction of a new special tournament with a prescribed score set is due to Pirzada and Naikoo [ 218 ]. The score structure for 1-tournaments was introduced by H. G. Landau [ 159 ] and extended for -tournaments by J. W. Moon in 1963 [ 184 ]. This result of Moon later was reproved by Avery for [ 12 ] and for arbitrary by Kemnitz and Dolff [ 144 ]. Score sets of oriented graphs were investigated by Pirzada and Naikoo in 2008 [ 221 ].

Authors of a lot of papers investigated the score sets of different generalized tournament, among others Pirzada, Naikoo and Chisthi in 2006 (bipartite graphs), Pirzada and Naikoo in 2006 [ 219 ] (-partite graphs), Pirzada and Naikoo in 2006 [ 220 ] (-partite graphs). Pirzada, Naikoo and Dar analyzed signed degree sets of signed bipartite graphs [ 222 ].

The basic results on kings are due to K. Brooks Reid [ 234 ], [ 235 ], [ 236 ], [ 237 ] and Vojislav Petrovic [ 37 ], [ 207 ], [ 208 ], [ 209 ], [ 210 ].

The problem of the unicity of score sequences was posed and studied by Antal Iványi and Bui Minh Phong [ 133 ]. Another unicity results connected with tournaments was published e.g. by P. Tetali, J. W. Moon and recently by Chen et al. [ 49 ], [ 50 ], [ 186 ], [ 269 ].

The term king in tournaments was first used by Maurer [ 173 ]. Strong kings were introduced by Ho and Chang [ 113 ] and studied later by Chen et al. [ 49 ], [ 50 ], while Pirzada and Shah [ 226 ] introduced weak kings in oriented graphs. The problems connected with 3-kings and 4-kings were discussed by Tan in [ 266 ] and the construction of tournaments with given number of strong kings by Chen et al. in [ 50 ].

The difference of the out-degree and of the in-degree of a given vertex is called the imbalance of the given vertex. The imbalance set of directed multigraphs were studied by Pirzada, Naikoo, Samee and Iványi in [ 224 ], while the imbalance sets of multipartite oriented graphs by Pirzada, Al-Assaf and Kayibi [ 215 ].

An interesting new direction is proposed by L. B. Beasley, D. E. Brown, and. K. B. Reid in [ 23 ]: the problem is the reconstruction of tournaments on the base of the partially given out-degree matrix.

In connection with Problem 1 see Yao's paper [ 291 ] and Chapter Score sets and kings and [ 168 ].

To solve Problem 2 you can find some results on losing scores in the paper Pirzada, Zhou and Iványi [ 231 ].

You can find hints for the solution of Problem 3 and Problem 4 in the recent papers in imbalances [ 215 ], [ 212 ], [ 224 ].

In connection with Problem 5 it is worth to read the paper of Brualdi [ 39 ], Gale [ 89 ], Krause [ 157 ], Ryser [ 244 ] and Sótér, Iványi, and Lucz [ 260 ].

The European Union and the European Social Fund under the grant agreement no. TÁMOP 4.2.1/B-09/1/KMR-2010-0003.