\documentclass[dvips,10pt,b5paper]{book}

\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[dvips]{graphicx}

\usepackage{epsfig}
\usepackage{graphicx}

\usepackage{multirow}
\usepackage{enumerate}

\usepackage{AlgofInfColor30January2011}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Automata
\usepackage{emlines,emlines2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Compilers
\usepackage[emtex,dvips,all]{xy} 
\usepackage{hhline} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Reliable
\usepackage{enumerate}
\usepackage{amsmath,amssymb}

\addtocounter{part}{0}
\addtocounter{chapter}{29}
\setcounter{page}{1500}
\setcounter{tocdepth}{2}

\topmargin -10mm
\oddsidemargin 0.0in
\evensidemargin 0.0in

\makeindex


\sloppy

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\Zset{\mathbb{Z}}


\begin{document}
\tableofcontents

\chapter{ Score Sets and Kings\label{chapterScoreSets}}

\noindent The idea of comparison-based ranking has been discussed earlier in the chapter 
\textit{Comparison based ranking},\index{comparison based ranking}  
where score sequence was introduced as a way of ranking vertices in a tournament. 
Oriented graphs are generalizations of tournaments. In fact, just like one can think of a tournament 
as expressing the results of a round-robin competition without ties (with vertices representing players 
and arrows pointing to the defeated players), one can think of an oriented graph as a round-robin 
competition with ties allowed (ties are represented by not drawing the corresponding arcs). 
\begin{figure}[!ht]
\centering
\includegraphics[width=10cm,height=3cm]{roundrobin}
\caption{A round-robin competition involving 4 players.\label{figroundrobin}}
\end{figure}
Figure \ref{figroundrobin} shows the results of a round-robin competition involving 4 players $a, \ b, \ c$ 
and $d,$ with (a) ties not allowed and (b) ties allowed. In the first instance there is always a winner 
and a loser whenever two players square off, while in the latter case player $a$ ties with player $d$ 
and player $b$ ties with player $c.$    

In 2009 Antal Iványi\nevindex{Iványi, Antal Miklós} studied directed graphs, in which every pair 
of different vertices is connected with at least $a$ and at most $b$ arcs. He named them 
$(a,b,n)$-tournaments or simply $(a,b)$-tournament.\index{directed graph}
\index{abtournament@$(a,b)$-tournament}\index{abntournament@$(a,b,n)$-tournament}

If $a = b = k,$ then the $(a,b)$-tournaments are called $k$-tournaments.\index{ktournament@$k$-tournament}  
In this chapter we deal first of all with $1$-tournaments and $(0,1)$-tournaments. 
$(0,1)$-tournaments are in some sense equivalent with $(2,2)$-tournaments. We use the simple notations 
1-tournament $T^1_n,$\index{onetournament@1-tournament} 2-tournament $T^2_n,$\index{twotournament@2-tournament} 
\ldots, $k$-tournament $T^k_n,$ \ldots .\index{ktournament@$k$-tournament}
It is worth mentioning that $T^1_n$ is a classical tournament, while oriented graphs are   
$(0,1)$-tournaments. If we allow loops then every directed graph is some $(a,b,n)$-tournament 
(see the Chapter \ref{chapterRanking} (\textit{Comparison Based Ranking}) of this book). 

We discuss two concepts related with $(a,b)$-tournaments,  
namely score sets and kings. A \textit{score set}\index{score set} is just the set of different scores 
(out-degrees) of vertices, while a \textit{king}\index{king} is a dominant vertex.  
We shall study both concepts for 1-tournaments first and then extend these to the more general setting 
of oriented graphs. 

Although we present algorithms for finding score sets and kings in $1$-tournaments and $(0,1)$-tournaments, 
much of the focus is on constructing tournaments with special 
properties such as having a prescribed score set or a fixed number of kings. Since players in a tournament 
are represented by vertices, we shall use the words player and vertex interchangeably throughout 
this chapter without affecting the meaning. 

We adopt the standard notation $T(V,A)$ to denote 
a tournament with vertex set $V$ and arc set $A.$ We denote the number of vertices by $n,$ and the 
out-degree matrix\index{out-degree matrix} by $\mathcal{M},$ and the 
in-degree matrix\index{in-degree matrix} by $N.$ Furthermore, we use the term $n$-tournament 
and the notation $T^k_n$ to represent a tournament with $n$ vertices and exactly $k$ arcs between the elements 
of any pair of different vertices. In a similar way $R_n^k$ and $N_n$ denote a regular, resp. a null graph. 
When there is no ambiguity we omit one or even both indices shall refer 
to the corresponding tournaments as $T,$ $R.$ and $N.$ 

In Section \ref{sec30Sets1t} the score sets of 1-tournaments are discussed, while Section 
\ref{sec30Sets2t} deals with the sore sets of oriented graphs. 
In Section \ref{sec30Unicity} the conditions of the unique reconstruction of the score sets are considered 
at first for $k$-tournaments, then in more details for 1-tournaments and 2-tournaments.
In Section \ref{sec30Kings1t} and Section \ref{sec30Kings2t} results connected with 
different kings of tournaments are presented.

Some long and accessible proofs are omitted. In these cases the Reader can find the coordinates of the proof 
in \textit{Chapter notes} and \textit{Bibliography}. 
%%%%%%%%%%%%%%%%%
\section{Score sets in 1-tournaments\label{sec30Sets1t}}\index{score sets in 1-tournaments|(}
In a round-robin competition with no ties allowed, what are the sets of nonnegative integers 
that can arise as scores of players? Note that here we are not interested in the scores 
of individual players (the score sequence), rather we are looking for the sets of nonnegative integers 
with each integer being the score of at least one player in the tournament. 
This question motivates the study of \textit{score sets} of tournaments. 

The set of different scores of vertices of a tournament is called the \ki{score set}\inddef{score set} 
of the tournament. In other words, the score set is actually the score sequence of a tournament 
with repetitions removed. For example the tournament given in Figure \ref{fig30scoresetexample} has 
score sequence $[0,2,2,2],$ whereas the score set of this tournament is $\{0,2\}.$ 
Figure \ref{fig30out} shows the out-degree matrix 
of the tournament represented on Figure \ref{fig30scoresetexample}.
\begin{figure}[!t]
\centering
\includegraphics[width=6cm,height=3.2cm]{scoresetexample}
\caption{A tournament with score set $\{0,2\}.$}
\label{fig30scoresetexample}
\end{figure}

\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}  \hline
vertex/vertex &  $a$ & $b$ & $c$ & $d$ &   Score \\ \hline
$a$         & ---    &  $0$  & $0$   & $0$    &  $0$   \\ \hline
$b$         & $1$    &  ---  & $1$   & $0$    &  $2$   \\ \hline
$c$         & $1$    & $0$   &  ---  & $1$    &  $2$   \\ \hline
$d$         & $1$    & $1$   & $0$   &  ---   &  $2$  \\ \hline
\end{tabular} \\
\caption{Out-degree matrix of the tournament represented in Figure \ref{fig30scoresetexample}.\label{fig30out}}
\end{center}
\vspace{-2mm}
\end{figure}

\subsection{Determining the score set\label{subsec30scoresetof1t}}
Determining the score set of a tournament $T(V,A)$ is quite easy. The following algorithm 
\textsc{Set1} takes the data of a tournament $T(V,A)$ as input 
and returns the score set $\mathcal{S}$ of $T.$

The procedures of this chapter are written according to the third edition of the textbook 
\textit{Introduction to Algorithms} published by T. H. Cormen,\nevindex{Cormen, Thomas H.} 
C. E. Leiserson,\nevindex{Leiserson, Charles E.} R. L. Rivest\nevindex{Rivest, Ronald L.} and 
C. Stein\nevindex{Stein, Clifford} in 2009.  

\begin{alg}{Set1$(n,V,A)$\inddef{\textsc{Set1}}\label{set}}
1 \' $\mathcal{S} = \emptyset$ \\
2 \' \key{for} \= all vertex $u \in V$ \\
3 \'              \> $s = 0$ \\
4 \'               \> \key{for} \= all vertex $v \in V$ \\
5 \'              \>              \> \key{if} \= $(u,v) \in A$ \` \key{//} is $(u,v)$ an arc of $T$? \\ 
6 \'               \>              \>             \> $s = s + 1$ \\
7 \'               \> \key{if} \= $s \notin \mathcal{S}$ \` \key{//} is the found score new? \\
8 \'               \>             \> $\mathcal{S} = \mathcal{S} \cup \{s\}$ \\
9 \' \key{return} $\mathcal{S}$
\end{alg}

Since the scores of the vertices depend on $n(n - 1)$ out-degrees, 
any algorithm determining the score set requires $\Omega(n^2)$ time. Due to the embedded loops in lines 02--08 
the running time of \textsc{Set1} is $\Omega(n^2)$ even in the best case. The precise order of the running 
time depends among others on the implementation of the \key{if} instruction in line 07. E.g., if line 07 is 
implemented by the comparison of the actual score with the elements of $S,$ then the running time is 
$\Theta(n^3)$ for a score sequence containing different elements and is $\Theta(n^2)$ for a regular tournament.

Out-degree matrix $\mathcal{M}_{n \times n} = [m_{ij}]_{n \times n}$ is a useful tool in the implementation 
of graph algorithms. The input of the following algorithm \textsc{Quick-Set1} is $n$ and $\mathcal{M},$ 
and the output is the score sequence \textbf{s} as a nonincreasingly ordered sequence and the score set 
$\mathcal{S}$ as an increasingly ordered sequence. \textsc{Quick-Set1} calls the well-known sorting procedure 
\textsc{Insertion-Sort}.\index{\textsc{Insertion-Sort}} 

\begin{algN}{Quick-Set1$(n,\mathcal{M})$\inddef{\textsc{Quick-Set1}}}
1 \' $\mathcal{S} = \emptyset$ \\
2 \' \key{for} \= $i = 1$ \key{to} $n$  \\
3 \'              \> $s_i = 0$ \\
4 \'              \> \key{for} \= $j = 1$ \key{to} $n$ \\
5 \'              \>              \> $s_i = s_i + m_{ij}$ \` \textbf{//} score sequence is computed \\ 
6 \' $S_1 = s_1$ \\
7 \' \textsc{Insertion-Sort}$(\mathbf{s})$ \key{if} \= $s \notin \mathcal{S}$ \` \key{//} sorting of the score vector\\
8 \' \key{for} \= $i = 2$ \key{to} $n$ \\
9 \'              \> \key{if} \= $s_i \neq s_{i-1}$ \\
10 \'             \>             \> $S_k = s_i$ \\
11 \'              \>             \> $k = k +1$ \\
12 \' \key{return} $\mathbf{s}, \ \mathcal{S}$
\end{algN}

Since the embedded loops in lines 02--05 need $\Theta(n^2)$ time, and the remaining part of the code 
requires less, the running time of \textsc{Quick-Set1} is $\Theta(n^2)$ in all cases.   

\subsection{Tournaments with prescribed score set\label{subsec302Constrt1}}
Constructing a tournament with a prescribed score set is more difficult than determining the score set. 
Quite surprisingly, if sufficiently many players participate in a tournament then any finite set 
of nonnegative integers can arise as a score set. This was conjectured by 
K. B. Reid\nevindex{Reid, K. Brooks} in 1978 and turned out to be a relatively challenging problem.  

Reid proved the result when $| \ \mathcal{S} \ | = 1, 2$ or $3$, or if $\mathcal{S}$ contains consecutive terms 
of an arithmetic or geometric progression. That is, Reid showed that any set of one, two or three 
nonnegative integers is a score set of some tournament and additionally, any set of the form 
$\{s, s + d, s + 2d, \ldots, s + pd\}$ for $s > 0, d>1$ or $\{s, sd, sd^{2},\ldots, sd^{p}\}$ 
for $s \geq 0, d > 0,$ is a score set of some tournament. Hager\nevindex{Hager, Michael} settled the cases 
$| \mathcal{S} |  = 4$ and $| \mathcal{S} | = 5$ in 1986 and finally in 1987, T. Yao\nevindex{Yao, Tianxing} 
gave an existence proof of the general Reid's conjecture based on arithmetic analysis. 

\begin{tetel} \emph{(Yao, 1988)} Every finite nonempty set $\mathcal{S}$ of nonnegative integers is 
the score set of some tournament. 
\end{tetel}

Let us try to formulate Reid's conjecture purely as a statement about numbers. 
Let $\mathcal{S} = \{ s_{1}, \ldots, s_{p} \}$ be an increasing sequence of nonnegative integers. 
The conjecture means that there exist positive integers $x_{1}, \ldots, x_{p}$ such that
\begin{equation*}
\mathcal{S} = (s_1^{x_1}, \ldots, s_2^{x_2} \ldots, s_p^{x_p})
\end{equation*}
is the score sequence of some 1-tournament with $\sum_{i=1}^p{x_i} = n$ vertices. 
By Landau's\nevindex{Landau, H. G.} theorem, $\mathbf{a} = (a_1,\ldots,a_n)$, with $a_1 \leq \cdots \leq a_n,$ 
is the score sequence of some $1$-tournament $T_n$ if and only if $\sum_{i=1}^k a_i \geq \textbinom{k}{2},$ 
for $k=1, \ldots, n-1$ and $\sum_{i=1}^n a_i = \textbinom{n}{2}.$ Thus it can be readily seen 
that Reid's conjecture is equivalent to the following statement. 

For every nonempty set of nonnegative integers $S = \{s_1, \ldots, s_p \},$  
where $s_1 < \cdots < s_p,$ there exist positive integers $x_1, \ldots, x_p,$ such that
\begin{eqnarray}
	\sum_{i=1}^k s_i x_i \geq \binom{\sum_{i=1}^k x_i}{2}, \ \ \textnormal{ for } k=1,\ldots,p-1\koz,\\
	\sum_{i=1}^p s_i x_i = \binom{\sum_{i=1}^px_i}{2} \koz. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
\end{eqnarray}

It is this equivalent formulation of Reid's conjecture that led to Yao's\nevindex{Yao, Tianxing} proof. 
The proof is not combinatorial in nature, but uses first of all some results of number theory.  
Commenting on Yao's proof Qiao Li\nevindex{Li, Qiao} wrote in 2006  
in the \textit{Annals of New York Academy of Sciences:}  
\begin{quotation}
	\textit{Yao's proof is the first proof of the conjecture, but I do not think it is the last one. 
	I hope a shorter and simpler new proof will be coming in the near future}.
\end{quotation}

However, the prophecized constructive proof has not been discovered yet. This is in sharp 
contrast with Landau's theorem on score sequences, for which several proofs have emerged 
over the years. Recently, S. Pirzada\nevindex{Pirzada, Shariefuddin} and T. A. Naikoo\nevindex{Naikoo, Tariq A.} 
gave a constructive combinatorial proof of a new special case of Reid's theorem. Their proof 
gives an algorithm for constructing a tournament with the prescribed score set, 
provided the score increments are increasing. 
\begin{tetel}\label{pirzada} 
\emph{(Pirzada and Naikoo, 2008)} If $a_{1}, a_{2}, \ldots, a_{p}$ are nonnegative integers 
with $a_1 < a_2 < \cdots < a_p,$ then there exists a 1-tournament $T$ with score set 
\begin{equation}
S = \left \{s_1 =a_1, s_2 = \sum_{i=1}^2 a_i, \ldots, s_p = \sum_{i=1}^p a_i \right \}\koz.
\label{pirzadaset}
\end{equation}
\end{tetel}
\begin{figure}[t!]
\centering
\includegraphics[width=8cm,height=5cm]{dominance}
\caption{Construction of tournament $T$ with odd number of distinct scores.}
\label{figdominance}
\end{figure}
\begin{figure}[t!]
\centering
\includegraphics[width=8cm,height=5cm]{dominance2}
\caption{Construction of tournament $T$ with even number of distinct scores.}
\label{figdominance2}
\end{figure}

Since any set of nonnegative integers can be written in the form of \ref{pirzadaset}, the above theorem 
is applicable to all sets of nonnegative integers $S = \{s_{1},s_{2},\ldots,s_{p}\}$ 
with increasing increments (i.e., $s_{1}<s_{2}-s_{1}<s_{3}-s_{2}<\cdots<s_{p}-s_{p-1}.$) 
The importance of Pirzada-Naikoo proof of Theorem \ref{pirzada} is augmented 
by the fact that Yao's\nevindex{Yao, Tianxing} original proof is not constructive and is not accessible to 
a broad audience\footnote{Yao's proof originally appeared in Chinese in the journal \textit{Kexue Tongbao.} 
Later in 1989, the proof was published in English in the \textit{Chinese Science Bulletin.}  
Unfortunately neither are accessible through the world wide web, 
although the English version is available to subscribers of the \textit{Chinese Science Bulletin.} 
In Hungary this journal is accessible in the Library of Technical and Economical University of Budapest.}. 

The following recursive algorithm is based on Pirzada and Naikoo's proof of Theorem \ref{pirzada}. 
The algorithm takes the set of increments $I_p=\{a_1 < a_2 < \cdots < a_p \}$ of the score set $S$ 
as input and returns a tournament $T$ whose score set is $S.$ Let $X_t = \{ a_1 < a_2 < \cdots < a_t \}$ for 
$1 \leq t \leq p.$ Let $R_{n}$ denote the regular tournament 
on $n$ vertices and let $T^{(1)}\oplus T^{(2)}$ denote the vertex and arc disjoint union 
of tournaments $T^{(1)}$ and $T^{(2)}.$    

\begin{alg}{Score-Reconstruction1$(p,I_p)$\inddef{\textsc{Score-Reconstruction1}}}
1 \' \key{if} \ \ \ \= $p$ is odd \\ 
2 \'          \> print \textsc{Odd$(p,I_p)$} \\
3 \' \key{else}     \> print \textsc{Even$(p,I_p)$}
\end{alg}

This algorithm calls one of the two following recursive procedures \textsc{ODD} and \textsc{Even} 
according to the parity of $p.$ The input of both algorithm is some prefix $X_t$ of the sequence 
of the increments $a_1, a_2, \ldots, a_t,$ and the output is a tournament having the score set corresponding 
to the given increments.

\begin{algN}{Odd$(t,X_t)$\inddef{\textsc{Odd}}}
1 \' \key{if} \ \ \ \= $t == 1$ \\ 
2 \'                \> \key{return} $R_{2a_1 + 1}$
\algnewpageN
3 \' \key{else}     \> $T_t^{(3)} = R_{(2(a_t - a_{t-1} + a_{t-2} - a_{t-3} + \cdots+ a_3 - a_2 + a_1) + 1)}$ \\
4 \'                \> $T_t^{(2)} = R_{2(a_{t-1} - a_{t-2} + a_{t-3} - a_{t-2} + 
                       \cdots + a_4 - a_3 + a_2 - a_1 - 1) + 1}$ \\
5 \'                \> $t = t - 2$ \\
6 \'                \> $T_t^{(1)}$ = \textsc{Odd}$(t, X_t)$ \\
7 \'                \> $T_t = T_t^{(3)} \oplus T_t^{(2)} \oplus T_t^{(1)}$ \\
8 \'                \> $T_t = T + $ \= arcs such that \\
9 \'                \>           \> $T_t^{(2)}$ dominates $T_t^{(1)}$ \\
10 \'               \>           \> $T_t^{(3)}$ dominates $T_t^{(1)}$ \\
11 \'               \>           \> $T_t^{(3)}$ dominates $T_t^{(2)}$ \\
12 \' \key{return} $T_t$
\end{algN}

We can remark that the tournament constructed by the first execution of line 03 of \textsc{Odd} contains 
the vertices whose score is $a_p,$ while the tournament constructed in line 04 contains the vertices whose score 
is $a_{p - 1}$ in the tournament appearing as output. The vertices having smaller scores appear during 
the later execution of lines 03 and 04 with exception of the vertices having score $a_1$ since those vertices 
will be added to the output in line 02.

\begin{alg}{Even$(t,X_t)$\inddef{\textsc{Even}}}
1 \'                  \> $T_t^{(2)} = R_{2(a_{t} -a_{t-1} + a_{t-2} - a_{t-3} + 
            \cdots + a_4 - a_3 + a_2 - a_1 - 1) + 1}$ \\
2 \'                  \> $t = t - 1$ \\
3 \'                  \> $T_t^{(1)}$ = \textsc{Odd}$(t, X_t)$ \\
4 \'                  \> $T_t = T_t^{(2)} \oplus T_t^{(1)}$ \\
5 \'                  \> $T_t = T + $ \= arcs such that $T_t^{(2)}$ dominates $T_t^{(1)}$ \\
6 \' \key{return} $T_t$  
\end{alg}

Since the algorithm is complicated, let's consider an example.

\begin{pelda} Let $p = 5$ and $I_5 = \{0,1,2,3,4\}.$ Since $p$ is odd, \textsc{Score-Reconstruction1} 
calls \textsc{Odd} in line 02 with parameters $5$ and $I_5.$

The first step of \textsc{Odd} is the construction of $T_5^{(3)} = T_{2(4 - 3 + 2 - 1 + 0) + 1} = T_5$ in line 03. 
Denoting the vertices of this regular 5-tournament by $v_1, \ v_2, \ v_3, \ v_4, \ v_5$ and using the result of 
Exercise \ref{regular} we get the out-degree matrix shown in Figure \ref{table302}.
\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}  \hline
vertex/vertex &  $v_1$ & $v_2$ & $v_3$ & $v_4 $ & $v_5$ &  Score \\ \hline
$v_1$         & ---    &  $1$  & $1$   & $0$    &  $0$  &   2 \\ \hline
$v_2$         & $0$    &  ---  & $1$   & $1$    &  $0$  &   2 \\ \hline
$v_3$         & $0$    & $0$   &  ---  & $1$    &  $1$  &   2   \\ \hline
$v_4$         & $1$    & $0$   & $0$   &  ---   &  $1$  &   2   \\ \hline
$v_5$         & $1$    & $1$   & $0$   &  ---   &  $0$  &   2\\ \hline
\end{tabular} \\
\caption{Out-degree matrix of the tournament $T_5^{(3)}$.\label{table302}}
\end{center}
\vspace{-2mm}
\end{figure}

The second step of \textsc{Odd}\pelindex{\textsc{Odd}} is the construction of 
$T_5^{(2)} = T_{2(3 - 2 + 1 - 0 - 1) + 1} = T_3.$ Let 
$v_6, \ v_7$ and $v_8$ be the vertices of this tournament.

The third step  of \textsc{Odd} is the recursive call with parameters $p = 3$ and $X_3 = \{2, \ 1, \ 0 \}.$ 
The fourth action of \textsc{Odd} is the construction of $T_3^{(3)} = T_{2(2 - 1 + 0) + 1} = T_3.$ 
Let $v_9, \ v_{10}$ and $v_{11}$ be the vertices of this tournament.
The fifth step is the construction of $T_3^{(2)} = T_{2(2 - 1 + 0 - 1)+ 1} = T_1.$ Let $v_{12}$ be the only 
vertex of this graph. The sixth action is the call of \textsc{Odd} with parameters $t = 1$ and $X_1 = \{ 0 \}.$  
Now the number of increments equals to 1, therefore the algorithm constructs $T_1^{(1)} = T_1$ in line 02. 

The seventh step is the construction of $T$ in line 07, then the eighth step is adding new arcs (according to 
lines 08--11) to the actual $T$ constructed in line 07 and consisting from 3 regular tournaments having 
altogether 5 vertices $(v_{13}, \ v_{12}, \ v_{11}, \ v_{10}, \ v_9)$. The result is shown in Figure \ref{table303}. 
\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}  \hline
vertex/vertex &  $v_9$ & $v_{10}$ & $v_{11}$ & $v_{12} $ & $v_{13}$ &  Score \\ \hline
$v_9$         & ---    &  $1$     & $0$      & $1$       &  $1$     &   3 \\ \hline
$v_{10}$      & $0$    &  ---     & $1$      & $1$       &  $1$     &   3 \\ \hline
$v_{11}$      & $1$    & $0$      &  ---     & $1$       &  $1$     &   3   \\ \hline
$v_{12}$      & $0$    & $0$      & $0$      &  ---      &  $1$     &   1   \\ \hline
$v_{13}$      & $0$    & $0$      & $0$      &  $0$      &  ---     &   0\\ \hline
\end{tabular} \\
\caption{Out-degree matrix of the tournament $T_5^{(3)}$.\label{table303}}
\end{center}
\vspace{-2mm}
\end{figure}
  
Ninth step of \textsc{Odd} is joining the tournaments $T_5$ and $T_3$ to $T$ and the final step 
is adding of the domination arcs. The out-degree matrix of the output $T_5$ of \textsc{Odd} 
is shown in Figure \ref{table304}.  
\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}  \hline
v/v     &$v_1$&$v_2$&$v_3$&$v_4$&$v_5$&$v_6$&$v_7$&$v_8$&$v_9$&$v_{10}$&$v_{11}$&$v_{12}$&$v_{13}$&  Score \\ \hline
$v_1$   & --- & $0$ & $0 $& $0$ & $0$ & $0$ & $0$ & $0$ & $0 $& $0$    & $0$    & $0$    & $0$    &   0 \\ \hline
$v_2$   & $1$ & --- & $0$ & $0$ & $0$ & $0$ & $0$ & $0$ & $0 $& $0$    & $0$    & $0$    & $0$    &   1 \\ \hline
$v_3$   & $1$ & $1$ & --- & $1$ & $0$ & $0$ & $0$ & $0$ & $0 $& $0$    & $0$    & $0$    & $0$    &   3 \\ \hline
$v_4$   & $1$ & $1$ & $0$ & --- & $1$ & $0$ & $0$ & $0$ & $0 $& $0$    & $0$    & $0$    & $0$    &   3 \\ \hline
$v_5$   & $1$ & $1$ & $1$ & $0$ & --- & $0$ & $0$ & $0$ & $0 $& $0$    & $0$    & $0$    & $0$    &   3 \\ \hline
$v_6$   & $1$ & $1$ & $1$ & $1$ & $1$ & --- & $1$ & $0$ & $0 $& $0$    & $0$    & $0$    & $0$    &   6 \\ \hline
$v_7$   & $1$ & $1$ & $1$ & $1$ & $1$ & $0$ & --- & $1$ & $0 $& $0$    & $0$    & $0$    & $0$    &   6 \\ \hline
$v_8$   & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $0$ & --- & $0 $& $0$    & $0$    & $0$    & $0$    &   6 \\ \hline
$v_9$   & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & --- & $1$    & $0$    & $1$    & $1$    &   10 \\ \hline
$v_{10}$& $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $0$ & ---    & $1$    & $1$    & $0$    &   10 \\ \hline
$v_{11}$& $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $0$ & $0$    &  ---   & $1$    & $1$    &   10   \\ \hline
$v_{12}$& $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $0$    & $0$    &  ---   & $1$    &   10   \\ \hline
$v_{13}$& $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$    & $0$    &  $0$   &  ---   &   10\\ \hline
\end{tabular} \\
\caption{Out-degree matrix of the tournament $T_5$.\label{table304}}
\end{center}
\vspace{-2mm}
\end{figure}
\end{pelda}  

\subsubsection{Correctness of the algorithm} Let $I = \{a_1, a_2, \ldots, a_p\}$ be a set of $p$ 
nonnegative integers with $a_1 < a_2 < \cdots < a_p.$ 
\textsc{Score-Reconstruction1} performs two types of recursions: first if $p$ 
is odd and the second if $p$ is even. Assume $p$ to be odd. For $p = 1,$ the set $I$ 
contains one nonnegative integer $a_1$ and the algorithm returns the regular tournament $T_{2a_{1}+1}$ as output. 
Note that each vertex of $T_{2a_{1}+1}$ has score $\textbinom{2a_{1}+1-1}{2} = a_1,$ so that score set 
of $T_{2a_{1}+1}$ is $S = \{s_1 = a_1\}.$ This shows that the algorithm is correct for $p = 1$. 

If $p = 3,$ then the set of increments $I$ consists of three nonnegative integers 
$\{a_1, a_2, a_3\}$ with $a_1 < a_2 < a_3.$ Now $a_3 > a_2,$ therefore $a_3 - a_2 > 0,$ 
so that $a_3 - a_2 + a_1 > 0$ as $a_1 \geq 0.$ Let $T^{(3)}$ be a regular tournament having 
$2(a_{3} - a_{2} + a_{1}) + 1$ vertices. Then each vertex of $T^{(3)}$ has score 
$\textbinom{2(a_3 - a_2 + a_1) + 1 - 1}{2} = a_3 - a_2 + a_1.$

Again, since $a_2 > a_1,$ therefore $a_2 - a_1 > 0,$ so that $a_2 - a_1 - 1 \geq 0.$ Let $T^{(2)}$ 
be a regular tournament having $2(a_2 - a_1 - 1) + 1$ vertices. Then each vertex of 
$T^{(2)}$ has score $\textbinom{2(a_2 - a_1 - 1) + 1 - 1}{2} = a_2 - a_1 - 1.$ 
Also since $a_{1} \geq 0,$ let $T^{(1)}$ be a regular tournament having $2a_1 + 1$ vertices. 
Then each vertex of $T_1$ has score $\textbinom{2a_1 + 1 - 1}{2} = a_1.$

If $p = 3,$ \textsc{Score-Reconstruction1}\index{Score-Reconstruction1} outputs a tournament $T$ whose 
vertex set is the disjoint union of vertex sets of $T^{(1)},$ $T^{(2)}$ and $T^{(3)}$ and whose arc set contains 
all the arcs of $T^{(1)},$ $T^{(2)}$ and $T^{(3)}$ such that every vertex of $T^{(2)}$ 
dominates each vertex of $T^{(1)},$ and every vertex of $T^{(3)}$ dominates each vertex of $T^{(1)}$ 
and $T^{(2)}.$ Thus $T$ has $2a_1 + 1 + 2(a_2 - a_1 - 1) + 1 + 2(a_3 - a_2 + a_1) + 1 = 2(a_1 + a_3) + 1$ 
vertices with score set
\begin{eqnarray*}
S = \{a_1, a_2 - a_1 - 1 + 2a_1 + 1, a_3 - a_2 + a_1 + 2(a_2 - a_1 - 1) + 1 + 2a_1 + 1\}\\
= \left \{a_1, \sum_{i=1}^2 a_i, \sum_{i=1}^3 a_i \right \} \koz. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  
\end{eqnarray*}

This shows that the algorithm is correct for $p = 3$ too. When the set $I$ of increments consists 
of an odd number of nonnegative integers, the algorithm recursively builds the required tournament 
by using the procedure \textsc{Odd}. To see this, assume that the algorithm works for all odd numbers 
upto $p.$ That is, if $a_1, a_2,\ldots, a_p$ are $p$ nonnegative integers with $a_1 < a_2 < \cdots < a_p,$ 
then the algorithm outputs a tournament having $2(a_1 + a_3 +\ldots + a_p) + 1$ vertices with score set 
$\{ a_1,\sum_{i=1}^2 a_i, \ldots, \sum_{i=1}^p a_i\}.$ Let us call this tournament $T^{(1)}.$ 

We now show how the algorithm constructs a tournament with $p + 2$ vertices with score set 
$\{a_1, \sum_{i=1}^2 a_i, \ldots, \sum_{i=1}^{p+2} a_i\},$ where $a_1, a_2,\ldots, a_{p+2}$ are 
$p+2$ nonnegative integers with $a_1 < a_2 < \cdots < a_{p+2}.$ 

Since $a_2 > a_1, a_4 > a_3,\ldots, a_{p-1} > a_{p-2}, a_{p+1} > a_p.$ therefore $a_2 - a_1 > 0,$ $a_4- a_3 > 0,$ 
$\ldots, a_{p-1} - a_{p-2} > 0,$ $a_{p+1}-a_p > 0,$ so that $a_{p+1} -a_p + a_{p-1} - a_{p-2} + \ldots + 
a_4- a_3 + a_2 - a_1 > 0,$ that is, $a_{p+1}-a_p + a_p - 1 - a_{p-2} + \ldots + a_4 - a_3 + a_2 - a_1 - 1 \geq 0.$ 

The procedure \textsc{Odd}\index{\textsc{Odd}} constructs $T^{(2)}$ as a regular tournament having 
$2(a_{p+1} - a_p + a_{p-1} - a_{p-2} + \cdots + a_4 - a_3 + a_2 - a_1 - 1) + 1$ vertices. Each vertex of $T^{(2)}$ 
has score 
\begin{eqnarray*}
\frac{2(a_{p+1} - a_p + a_{p-1} - a_{p-2} + \ldots + a_4 - a_3 + a_2 - a_1 - 1) + 1 - 1}{2}\\
= a_{p+1} - a_p + a_{p-1} - a_{p-2} + \cdots + a_4 - a_3 + a_2 - a_1 - 1 \koz . \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
\end{eqnarray*}

Again, $a_3 > a_2, \ldots, a_p > a_{p-1}, a_{p+2} > a_{p+1},$ therefore $a_{3}-a_2 > 0, \ldots, 
a_{p} - a_{p-1} > 0, a_{p+2} - a_{p+1} > 0,$ so that $a_{p+2} - a_{p+1} + a_p - a_{p-1} + \cdots + 
a_3 - a_2 + a_1 > 0$ as $a_1 \geq 0.$

The procedure \textsc{Odd}\index{\textsc{Odd}} constructs $T^{(3)}$ as a regular tournament having 
$2(a_{p+2} - a_{p+1} + a_p - a_{p-1} + \cdots+ a_3 - a_2 + a_1) + 1$ vertices. Each vertex of $T^{(3)}$ has score
\begin{eqnarray*}
\frac{2(a_{p+2} - a_{p+1} + a_p - a_{p-1} + \cdots + a_{3} - a_2 + a_1) + 1 - 1}{2} \\
= a_{p+2} - a_{p+1} + a_p - a_{p-1} + \cdots + a_3 - a_2 + a_1 \koz . \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
\end{eqnarray*}

Now \textsc{Score-Reconstruction1} sets $T=T^{(1)}\oplus T^{(2)}\oplus T^{(3)}$ 
and adds additional arcs in such a way that every vertex of $T^{(2)}$ dominates each vertex of $T^{(1)},$ 
and every vertex of $T^{(3)}$ dominates each vertex of $T^{(1)}$ and $T^{(2)}$.  Therefore $T$ is 
a tournament having 
\begin{eqnarray*}
2(a_1 + a_3 + \cdots + a_p) + 1 + 2(a_{p+1}a_p + a_{p1}a_{p2} + \cdots + a_4a_3 + a_2a_1) + 1 \ \ \\ 
+2(a_{p+2}a_{p+1}+ a_pa_{p-1} + \cdots +a_3a_2 + a_1) + 1 \\
= 2(a_1 + a_3 + \cdots + a_{p+2}) + 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
\end{eqnarray*}

\noindent vertices with score set
\begin{equation*}
S = \left \{a_1, \sum_{i=1}^2 a_i,\ldots, \sum_{i=1}^p a_i, \sum_{i=1}^{p+1} a_i, \sum_{i=1}^{p+2}a_i \right \} \koz.
\end{equation*}

Hence by induction, the algorithm is correct for all odd $p.$ 

To prove the correctness for even case, note that if $p$ is odd, then $p + 1$ is even. Let 
$a_1, a_2, \ldots, a_{p+1}$ be $p+1$ nonnegative integers with $a_1 < a_2 < \cdots < a_{p+1}.$. 
Therefore $a_1 < a_2 < \cdots < a_p,$ where $p$ is odd. The procedure \textsc{Even} uses 
the procedure \textsc{Odd} to generate a tournament $T^{(1)}$ having $2(a_1 + a_3 + \cdots + a_p ) + 1$ 
vertices with score set $S = \{a_1, \sum_{i=1}^2 a_i,\ldots, \ \sum_{i=1}^p a_i\}.$  

Also, since $a_2 > a_1,$ $a_4 > a_3, \ldots, a_{p-1} > a_{p-2}, a_{p+1} > a_p,$ 
the procedure \textsc{Even} generates a regular tournament $T^{(2)}$ having $2(a_{p+1} - a_p + a_{p-1} - 
a_{p-2} + \cdots +a_4 -a_3 +a_2 - a_1 - 1) + 1$ vertices such that the score for each vertex is 
$a_{p+1} - a_p + a_{p-1} - a_{p-2} + \cdots + a_4 - a_3 + a_2 - a_1 - 1.$ 

Finally the algorithm generates the tournament $T^{(1)}\oplus T^{(2)}$ and adds additional arcs so 
that every vertex of $T^{(2)}$ dominates each vertex of $T^{(1)}.$ 
The resulting tournament $T$ consists of 
\begin{eqnarray*}
2(a_1 + a_3 + \cdots + a_{p-2} + a_p ) + 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
+ 2(a_{p+1} - a_p + a_{p-1} - a_{p-2}+ \cdots + a_4 - a_3 + a_2 - a_1 - 1) + 1 \\
= 2(a_2 + a_4 + \cdots + a_{p+1}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
\end{eqnarray*}
vertices and has score set 

\begin{eqnarray*}
S = \{a_1,\sum_{i=1}^2 a_i,\ldots ,\sum_{i=1}^p a_i, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
a_{p+1} - a_p + a_{p-1} - a_{p-2} + \cdots + a_4 - a_3 + a_2 - a_1 - 1 \\
+ 2(a_1 + a_3 + \cdots + a_{p-2} + a_p) + 1 \} \\
= \{a_1,\sum_{i=1}^2 a_i,\ldots, \ \sum_{i=1}^{p+1} a_i\}\koz.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
\end{eqnarray*}

This shows that the algorithm is correct for even $p$ as well.



\subsubsection{Computational complexity} 
The running time of \textsc{Score-Reconstruction1}\index{Score-Reconstruction1} depends 
on the size of the score set $\vert S \vert$ as well as the largest increment $a_p = s_p - s_{p-1}.$  
The details are left as a problem for the Reader (see Exercise \ref{regular}). 

\begin{gyak}
\ujgyak\label{regular}
The out-degree matrix $\mathcal{M}$ of a tournament is defined as a $0-1$ matrix with $(i,j)$ entry 
equal to 1 if player $v_{i}$ defeats player $v_{j}$ and 0 otherwise (see (\ref{outdeg})). 
A tournament is completely determined by its out-degree matrix. Write an $O(n^{2})$ algorithm 
to generate the out-degree matrix of a regular tournament on $n$ vertices, where $n$ is any odd positive integer. 
\textit{Hint.} Circularly place $\textbinom{n-1}{2}$ ones in each row.
\vspace{-4mm}
\ujgyak\label{complexity}
Use Exercise \ref{regular} and the discussion in this section to determine 
the worst-case running time of \textsc{Score-Reconstruction1}.\gyakindex{\textsc{Score-Reconstruction1}} 
\ujgyak\label{ex}
Obtain the out-degree matrix of a tournament with score set $\{1,3,6\}$. 
How many vertices does this tournament have? Draw this tournament and give its outdegree-matrix.
\ujgyak\label{exs}
Use the tournament obtained in Exercise \ref{ex} to generate the out-degree matrix of 
a 1-tournament\index{onetournament@1-tournament} 
with score set $\{1,3,6,10\}.$ Write the score sequence of your tournament. 
\end{gyak}\index{score sets in 1-tournaments|)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Score sets in oriented graphs\label{sec30Sets2t}}\index{score sets in oriented graphs|(}
Oriented graphs are generalizations of tournaments. Formally, an \ki{oriented graph}\inddef{oriented graph} 
$D(V,A)$ with vertex set $V$ and arc set $A$ 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 $(0,1)$-\textit{tournaments.}\index{zeroonetournament@$(0,1)$-tournament} 
 
Figure \ref{figorientedgr} shows an oriented graph with score sequence $[1,3,3,5]$ and the coressponding 
score set $\{1,3,5\}.$ 
 
\begin{figure}[t]
\centering
\includegraphics[width=6.2cm,height=3.7cm]{orientedgr}
\caption{An oriented graph with score sequence $[1,3,3,5]$ and score set $\{1,3,5\}$.\label{figorientedgr}} 
\end{figure}
  
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\nevindex{Avery, Peter} 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 $v_{i}$ in a $k$-tournament $D$ with $n$ vertices is defined as 
$$
a(v_{i})= a_{i} =n-1+d^{+}_{v_{i}} -d^{-}_{v_{i}}\koz, 
$$
where $d^+ _{v_i}$ and $d^- _{v_i}$ are the out-degree and in-degree, respectively, of $v_i$. 
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 $D$ containing the vertex $v_i$ as $d^* _{v_i}$, then
$$
a_{i} = 2d^{+}_{v_{i}}+d^{*}_{v_{i}} \koz .
$$

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 
$u$ to $v$ if and only if $u$ defeats $v$. 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.\index{twotournament@2-tournament2-tournament}

Avery gave a complete characterization of score sequences of oriented graphs similar to Landau's theorem. 
\begin{tetel}\label{avery} \emph{(Avery, 1991)} 
A nondecreasing sequence $A = [a_1, \ldots, a_n ]$ of nonnegative integers is the score sequence 
of an oriented graph if and only if
\begin{equation}\label{av}
\sum_{i=1}^{k}a_i \geq k(k - 1)
\end{equation}
\noindent for $1\leq k \leq n$ with equality when $k = n.$ 
\end{tetel} 
\begin{biz}
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 \ref{chapterComparison}, 
that is chapter \textit{Comparison Based Ranking}).
\end{biz}

Just as in the case of 1-tournaments, the 
\ki{score set of an oriented graph}\inddef{score set of an oriented graph} 
is defined as the set of scores of its vertices. It is worth noting that 
a $(0,1)$-tournament has different score sets under Avery's\nevindex{Avery, Peter} and 
Landau's\nevindex{Landau, H. G.} score structures. In fact, the score of a vertex $v$ 
under Avery's score structure is twice the score of $v$ 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 \textsc{Quick-Set2} as follows: 

\begin{algN}{Quick-Set2$(n,\mathcal{M})$\inddef{\textsc{Quick-Set2}}}
1 \' $S = \emptyset$ \\
2 \' \key{for} \= $i = 1$ \key{to} $n$  \\
3 \'              \> $s_i = 0$ \\
4 \'              \> \key{for} \= $j = 1$ \key{to} $n$ \\
5 \'              \>              \> $s_i = s_i + 2m_{ij}$ \\
6 \'              \>              \> \key{if} \= $m_{ij == 0}$ and $m_{ji} == 0$ \\
7 \'              \>              \>             \> $s_i = s_i + 1$  \` \key{//} score sequence is computed \\
8 \' $S_1 = s_1$ \\
9 \' $k = 2$ \\
10 \' \key{for} \= $i = 2$ \key{to} $n$ \\
11 \'              \> \key{if} \= $s_i \neq s_{i-1}$ \` \key{//} is the found score new? \\
12 \'              \>             \> $S_k = s_i$ \\
13 \'              \>             \> $k = k +1$ \\
14 \' \key{return} $\mathbf{s}, \ S$
\end{algN}

The running time of \textsc{Quick-Set2} is $\Theta(n^{2})$ since the nested loop in lines 
02--07 requires $\Theta(n^2)$ the remaining lines require $\Theta(n)$ time.

\subsection{Oriented graphs with prescribed scoresets\label{subprescibedset2}}
In Section \ref{sec30Sets2t} 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\nevindex{Pirzada, Shariefuddin} and Naikoo\nevindex{Naikoo, Tariq A.} 
investigated this question and gave two sufficient conditions for a set of nonnegative integers 
to be the score set of some oriented graph.  
\begin{tetel}\label{theorem30ssog1} \emph{(Pirzada, Naikoo, 2008)}
Let $a, \ d, \ n$ nonnegative integers, $a > 0$and $S = \{a, ad, ad^{2}, \ldots, ad^{n}\}$, with $d > 2$  
or $d = 2$ and $n > 1.$ Then there exists an oriented graph with score set $S$ except for $a = 1, \ d = 2, \ n > 0$ 
and for $a = 1, \ d = 3, \ n > 0$.
\end{tetel}   
\begin{tetel}\label{theorem30ssog2} \emph{(Pirzada, Naikoo, 2008)}
If $n$ is a positive integer and $a_1, a_2, \ldots, a_n$ are nonnegative integers with 
$a_1 < a_2 < \cdots < a_n,$ 
then there exists an oriented graph with $a_n + 1$ vertices and with score set 
$S = \{s_1, s_2, \ldots, s_n \},$ where
\begin{equation}\label{ss}
s_{i} = \left\{\begin{array}{l}
s_{i-1} + a_{i} + 1 \ \ \ \ \ \var{for } i > 1\koz, \\
s_{i} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \var{for } i = 1\koz.
\end{array} \right .
\end{equation}
\end{tetel}

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 (\ref{ss}) 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 $n,$ 
the sets $\{1, 2, 2^2, \ldots, 2^n \}$ and $\{1, 3, 3^2, \ldots, 3^n \}$ 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 \ref{theorem30ssog1} depends on the following auxiliary assertion. 
\begin{lemma}\label{aux} \emph{(Naikoo, Pirzada, 2008)}
The number of vertices in an oriented graph with at least two distinct scores does not exceed its largest score.
\end{lemma}
\begin{biz} This assertion is the special case $k = 2$ of Lemma \ref{Lemma3031} 
due to Iványi\nevindex{Iványi, Antal Miklós} and Phong.\nevindex{Phong, Bui Minh}
\end{biz}

Here we omit formal proofs of Theorems \ref{theorem30ssog1} and \ref{theorem30ssog2} since they 
can be found on the internet and since we will implicitly prove these theorems  when we check 
the correctness of \textsc{Geometric-Construction2} and \textsc{Adding-Construction2}, respectively. 

We first present a recursive algorithm that takes positive integers $a,$ $d,$ and $n,$ satisfying 
the condition of Theorem \ref{ssog1}, as input and generates a 2-tournament $D(V,A)$ 
with score set $\{ a, ad, ad^2, \ldots, ad^n \}.$ Let $N_{p}$ denote the null digraph on $p$ vertices, 
i.e., the digraph with $n$ vertices and no arcs. 

\begin{algN}{Geometric-Construction2$(a,d,n)$}\inddef{\textsc{Geometric-Construction}}
1 \' \key{if} \ \ \ \ \= $n = 0$\\
2 \'                  \> $D = N_{a+1}$ \\
3 \'                  \> \key{return} $D$ \\
4 \' \key{if} \= $n = 1$\\
5 \'          \> \key{if} \= $a = 1$ and $d = 3$ \\
6 \'          \>          \> $X = N_{a+1}$ \\
7 \'          \>          \> $Y = N_{ad - a - 1}$ \\
8 \'          \>          \> $D = X \oplus Y$\\
9 \'          \>          \> add arcs to $D$ such \\
10 \'         \>          \> $X$ dominates $Y$\\
11 \'		  \>          \> \key{return} $D$ \\
12 \'         \> \key{if} \= $a > 2$ and $d = 2$ \\
13 \'         \>          \> $X = N_2$ with vertex set $\{u_1,u_2 \}$\\
14 \'         \>          \> $Y = N_{a - 2}$ with vertex set $\{v_1,v_2,\ldots,v_{a - 2} \}$\\
15 \'         \>          \> $Z = N_a$ with vertex set $\{z_1,z_2,\ldots,z_a\}$ \\
16 \'         \>          \> $D = X \oplus Y \oplus Z$\\
17 \'         \>          \> add arcs to $D$ such that\\
18 \'         \>          \> $v_i \rightarrow u_1$ for $i = 1, 2, \ldots,a$ \\
19 \'         \>          \> $v_i \rightarrow u_2$ for $i = 1, 2, \ldots,a$ \\
20 \'         \>          \> $w_1 \rightarrow u_1$
\algnewpageN
21 \'         \>          \> $w_2 \rightarrow u_2$ \\
22 \'         \>          \> $w_{i+2} \rightarrow v_i$ for $i = 1, 2, \ldots,a - 2$ \\
23 \'         \> \key{if} \= $a = 1$ and $d = 3$ \\
24 \'         \>          \> $X = N_{a+1}$ \\
25 \'         \>          \> $Y = N_{ad - a - 1}$ \\
26 \'         \>          \> $D = X \oplus Y$\\
27 \'         \>          \> add arcs to $D$ such \\
28 \'         \>          \> $X$ dominates $Y$\\
29 \'		  \>          \> \key{return} $D$
\end{algN}

The running time of \textsc{Geometric-Construction2} is ??????? 

\begin{pelda} Let $a = 2, \ d = 2$ and $n = 2.$ Then the prescribed score set is $\{2,4,8\}.$ The first step 
is the call of \textsc{Geometric} with parameters $(2,2,2).$

\end{pelda}

\subsubsection{Algorithm description}  
If $n = 0,$ then the algorithm returns the null digraph $N_{a+1}.$ Note that $N_{a+1}$ is well-defined 
as $a + 1 > 0.$ Each vertex of $N_{a+1}$ has score $a + 1 - 1 + 0 - 0 = a.$ Therefore the score set 
of $N_{a+1}$ is $S = \{a\}.$ Thus the algorithm is correct for $n = 0.$ 

If $n = 1,$ then four cases arise. 

Case i). If $a = 1$ and $d > 3,$ then $a + 1 > 0$ and $ad - 2a - 1 > 0.$ Construct an oriented graph $D$ with 
vertex set $V = X \cup Y,$ where $X \cap Y = \emptyset,$ $|X| = a + 1,$ $|Y| = ad - 2a - 1$ and 
$Y \rightarrow X.$ Then $D$ has $ad - a$ vertices and the different scores are $a$ and $ad.$ 

Case ii). If $a = 2$ and $d = 2.$ Construct an oriented graph $D$ with vertex set $\{v_1,v_2,v_3\}$ and 
$v_4$ and arc set $(v_1,v_3),(v_2,v_4).$ The score set of $D$ is $\{2,4\}.$

case iii). If $a > 2$ and $d = 2,$ then 
with vertex set $V = X \cup Y,$ where $X \cap Y = \emptyset,$ $|X| = a + 1,$ $|Y| = ad - 2a - 1$ and 
$Y \rightarrow X.$ Then the scores are $a$ for all $x \in X$ and $ad$ for all $y \in Y.$


Now we prove the correctness of \textsc{Geometric} by induction. That is, we show that 
if the algorithm is valid for $n = 0, 1,\ldots, p$ for some integer $p \geq 1$ then it is also valid 
for $n = p + 1.$ Let $a$ and $d$ be positive integers with $a > 0$ and $d > 1$ such that for $a = 1,$ 
$d \neq 2, 3.$ By the induction hypothesis the algorithm can construct an oriented graph $D^{(1)}$ 
with score set $\{a, ad, \ldots, ad^p\}$ and $a, ad, \ldots, ad^p$ are the distinct scores 
of the vertices of $D^{(1)}.$ Let $U$ be the vertex set of $D^{(1)}.$

There are three possibilities: 
\begin{itemize}
\item $a = 1$ and $d > 3,$ 
\item $a > 1$ and $d = 2$ or 
\item $a > 1$ and $d > 2.$ 
\end{itemize}
Obviously, for $d > 1$ in all the above cases we have $ad^{p+1}\geq 2ad^{p}.$ Also the score set 
of $D^{(1)},$ namely $\{a, ad, \ldots, ad^{p}\},$ has at least two distinct scores for $p \geq 1.$ 
Therefore, by Lemma \ref{aux} we have $\vert U \vert \leq ad^{p}.$ Hence 
$ad^{p + 1}\geq 2 \vert U \vert$ so that $ad^{p + 1} - 2 \vert U\vert + 1 > 0.$ 

Let $N_{ad^{p + 1} - 2 \vert U \vert + 1}$ be the null digraph with vertex set $X.$
The algorithm now generates the vertex and arc disjoint union $D=D^{(1)}\oplus N_{ad^{p+1}-2\vert U\vert+1}$ 
and adds an arc directed from each vertex in $N_{ad^{p+1}-2 \vert U\ vert + 1}$ to every vertex of $D^{(1)}.$ 
The output $D(V,A)$ of \textsc{Geometric-Construction2}, therefore, has 
$\vert V\vert = \vert U \vert + ad^{p+1} - 2 \vert U \vert + 1 = ad^{p+1}-\vert U\vert + 1$ vertices. 
Moreover, $a + \vert X \vert - \vert X \vert = a,$, $ad + \vert X \vert - \vert X \vert = ad.$ 
$ad^{2} + \vert X \vert - \vert X \vert = ad^2, \ldots, ad^p + \vert X \vert - \vert X \vert = ad^p$ 
are the distinct scores of the vertices in $U,$ while $a_{x} = \vert U \vert - 1 + \vert V\vert - 0 = 
ad^{p+1} - \vert V \vert + 1 - 1 + \vert V \vert = ad^{p+1}$ for all vertices $x\in X.$ 

Therefore the score set of $D$ is $S = \{a, ad, ad^2, \ldots, ad^p, ad^{p+1}\}$ 
which shows that the algorithm works for $n = p + 1.$ Hence the algorithm is valid for all 
$a,$ $d$ and $n$ satisfying the hypothesis of Theorem \ref{ssog1}.

The recursive procedure \textsc{Geometric} runs $n$ times and during its $i^{th}$ run 
the procedure adds $O(ad^{n + 1 -i})$ arcs to the oriented graph $D.$ The overall complexity 
of the algorithm is therefore $O(nad^n).$  

As noted in Theorem \ref{ssog1}, there exists no 1-tournament when either $a = 1, \ d = 2, \ n > 0$ or 
$a = 1, \ d = 3, \ n > 0.$ It is quite interesting to investigate these exceptional cases 
as it provides more insight into the problem. 

Let us assume that $\mathbf{S} = \{ 1, 2, 2^2,\ldots, 2^n\}$ is a score set of some oriented graph $D$ 
for $n > 0.$ Then there exist positive integers, say $x_1, x_2, x_3, \ldots, x_{n+1}$ such that
$$
S_1 = [1^{x_1},2^{x_2}, \ldots, (2^2)^{x_3},\ldots,(2^n)^{x_{n+1}}
$$
is the score sequence of $D.$ Therefore, by relations (\ref{av}) of score sequences of 1-tournaments, we have
$$
x_1 + 2x_2 + 2^{2}x_3 +\cdots+ 2^{n}x_{n+1} = 
\left(\sum_{i=1}^{n+1}x_i\right)\left(\sum_{i=1}^{n+1}x_i -1 \right)\koz,
$$
which implies that $x_1$ is even. However, $x_1$ is a positive integer, therefore $x_1 \geq 2.$ 
Let the scores be $a_1 = 1,$ $a_2 = 1$ and $a_3 \geq 1.$ By inequalities (\ref{av}) 
$a_1 + a_2 + a_3 \geq 3(3-1) = 6,$ or in other words, $a_3 \geq 4.$ This implies that 
$x_2 = 0,$ a contradiction.

The proof of the other exceptional case ($\mathcal{S} = \{ 1, 3, 3^2, \ldots, 3^n \}$) is left as an 
exercise (Exercise \ref{case}).

Let $I_p = a_1 > a_2 > \cdots > a_p$for $1 \leq p \leq n.$ 
The next algorithm takes the set $I = \{a_1 < a_2 < \cdots < a_n \}$ consisting of $n$ nonnegative integers 
as input and recursively constructs an oriented graph $D(V,A)$ with the score set 
$S = \{s_1, s_2, \ldots, s_n\}$ where  the scores $s_i$ are of the form \ref{ss}. 

\begin{alg}{Adding-Construction2$(n,I_n)$}\inddef{\textsc{Adding-Construction}}
1 \' \key{if} \ \ \ \ \= $n = 0$\\
2 \'                  \> $D = N_{a_1+1}$ \\
3 \'                  \> \key{return} $D$ \\
4 \' \key{else}       \> $D^{(1)}$ = \textsc{Adding-Construction}$(n - 1,I_{n - 1})$\\
5 \'                  \> $D =$ \= $D^1 \oplus N_{a_{n+1}-a_n}$\\
6 \'                  \> add arcs to $D$ such that $N_{a_{n}-a_{n-1}}$ dominates $D^{(1)}$ \\
7 \'  \key{return} $D$\\
\end{alg}

The running time of \textsc{Adding-Construction2} is ???????

\begin{pelda} ?????
\end{pelda}

\subsubsection{Algorithm description}  
If $n = 1,$ the algorithm returns the null digraph $N_{a_{1} + 1}.$ Each vertex of $N_{a_{1} + 1}$ 
has the score $a_1 + 1 - 1 + 0 - 0 = a_1 = a'_1.$ Therefore the score set of $N_{a_{1} + 1}$ is 
$S = \{a'_{1}\}$ as required.

We prove the correctness of \textsc{Adding-Construction2} in general by induction on $n.$ 
Assume that the algorithm is valid for $n = 1, 2, \ldots, p,$ for some integer $p \geq 2.$ 
We show that the algorithm is also valid for $n=p + 1.$ Let $a_1, a_2, \ldots, a_{p+1}$ 
be nonnegative integers with $a_1 < a_2 < \cdots< a_{p+1}.$ Since $a_1 < a_2 < \cdots< a_p,$ 
by the induction hypothesis, the algorithm returns an oriented graph $D^{(1)}$ on $a_p + 1$ 
vertices with score set $\{a'_1, a'_2, \ldots, a'_p \},$ where $a'_i$ is given by equations (\ref{ss}). 
That is, score set of $D^{(1)}$ is $\{a_1, a_1 + a_2 + 1, a_2 + a_3 + 1, \ldots, a_{p-1} + a_p + 1 \}.$ 
So $a_1,$ $a_1 + a_2 + 1,$ $a_2 + a_3 + 1, \ldots, a_{p-1} + a_p + 1$ are the distinct scores 
of the vertices of $D.$ Let $X$ be the vertex set of $D^{(1)}$ so that $\vert X \vert = a_p + 1.$ 
Since $a_{p+1} > a_p,$ $a_{p+1} - a_p > 0,$ the algorithm constructs a new oriented graph 
$D=D^{(1)}\oplus N_{p+1}$ with vertex set $V = X \cup Y,$ where $Y$ is the vertex set of 
$N_{p+1}$ and $\vert Y \vert = a_{p+1} - a_p.$ Arcs are added to $D$ such that there is an arc 
directed from each vertex in $Y$ to every vertex in $X.$ Thus $D$ has $\vert V \vert = 
\vert X \vert + \vert Y \vert = a_p +1+ a_{p+1} - a_p = a_{p+1} + 1$ vertices. 
The distinct score of vertices in $X$ are $a_1 + \vert Y \vert - \vert Y \vert = 
a_1 = a'_1, a_1 + a_2 + 1 + \vert Y \vert - \vert Y \vert = 
a_1 + a_2 + 1 = a'_2, a_2 + a_3 + 1 + \vert Y \vert - \vert Y \vert = a_2 + a_3 +1 = a'_3, \ldots, 
a_{p-1}+a{p}+1+\vert Y\vert-\vert Y\vert =a_{p-1} + a_p + 1 = a'_p,$ while 
$a_y = \vert X\vert - 1 + \vert V \vert - 0 = a_{p+1} + 1 - 1 + a_p + 1 = a_p + a_{p+1} + 1 = 
a'_{p+1}$ for all $y \in Y.$

Therefore the score set of $D$ is $S = \{s_1, s_2, \ldots, s_p, s_{p+1} \}$ which proves 
the validity of algorithm for $n = p + 1.$ Hence by induction, 
\textsc{Adding-Construction2} is valid for all $n.$

The analysis of computational complexity of \textsc{General-Construction} 
is left as an exercise (Exercise \ref{ss1complexity}). 

\begin{gyak}
\ujgyak\label{case}
Prove that there exists no oriented graph with score set $\{1,3,3^{2},\ldots,3^{n}\}$ for any $n > 0.$
\ujgyak\label{bothexceptional} 
Prove that if $n \geq 2$ and $\mathcal{S} = \{ 1,a_2,a_3,\ldots,a_n \},$ then $a_2 \geq 4.$
\ujgyak\label{ss1complexity}
\textsc{Adding-Construction} is a recursive algorithm. Analyse its running time and 
compare its performance with the performance of \textsc{Geometric-Construction}. 
\ujgyak\label{orientedgraph1}
Implement \textsc{Adding-Construction}  in a suitable programming language and use it to construct 
an oriented graph with score set $\{2,4,8\}.$ Write the score sequence of your oriented graph.  
\ujgyak\label{orientedgraph2}
Implement \textsc{Adding-Construction} in a suitable programming language and use it to construct 
an oriented graph with score set $\{1,4,6,9\}.$ Write the score sequence of your oriented graph.
\ujgyak\label{lemma}
Give a proof of Lemma \ref{aux}. 
\ujgyak\label{tournamentgraph1}
For any nonnegative integer $n,$ what is the score set of the regular tournament $T_{2n+1}$ 
when considered as an oriented graph. 
\ujgyak\label{tournamentgraph2}
Determine the score set of the oriented graph $D=T_{3}\oplus T_{5},$ where $T_{5}$ dominates 
$T_{3},$ i.e., there is an arc directed from every vertex of $T_{5}$ to every vertex of $T_3.$
\vspace{-4mm}
\ujgyak\label{cyclealgo}
Write an $O(n)$ algorithm to determine the score set 
of directed cycles\gyakindex{directed cycle}\gyakindex{cycle} (i.e., cycles with directed edges). 
How can we make this algorithm work for directed wheels (note that a 
\textit{wheel}\gyakindex{wheel}\gyakindex{directed wheel} 
is a cycle with an additional vertex joined to all the vertices on the cycle).  
\end{gyak}\index{score sets in oriented graphs|)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Unicity of score sets\label{sec30Unicity}}\index{unicity of score sets|(}
\ki{$k$-tournaments}\inddef{ktournament@$k$-tournament} (multitournaments)\index{multitournament} 
are directed graphs in which each pair of vertices is connected with exactly $k$ arcs. 

Reid formulated the following conjecture in \cite{Reid1978}.
\begin{sejtes} Any set of nonnegative integers is the score set of some 1-tournament T.
\end{sejtes}

Using Landau's theorem this conjecture can be formulated in the following arithmetic form too.
\begin{sejtes} If $0 \leq r_1 < r_2 < \cdots < r_m,$ then there exist such positive integers 
$x_1, \ x_2, \ \ldots, \ x_m,$ that
$$\sum_{i=1}^{j} x_i r_i \geq \frac{(\sum_{i=1}^{j} x_i)(\sum_{i=1}^{j} x_i - 1)}{2}, \ j \in[1:m]$$
and
$$\sum_{i=1}^{m} x_i r_i = \frac{(\sum_{i=1}^{m} x_i)(\sum_{i=1}^{m} x_i - 1)}{2}\koz .$$
\end{sejtes}

In this case we say that the sequence $\mathbf{s} = \langle s_1,\ldots,s_n \rangle = \langle r_1^{x_1}, 
\ldots, r_m^{x_m} \rangle$ realizes the sequence $\mathbf{r} = \langle r_1,\ldots,r_m \rangle$ or 
$\mathbf{s}$ is a solution for $\mathbf{r}.$

Reid gave a constructive proof of his conjecture for sets containing one, two or three elements \cite{Reid1978}.

Later Hager published a constructive proof for sets with four and five elements \cite{Hager1986} and 
Yao \cite{Yao1989} published the outline of a nonconstructive proof of the general case.

A score set is called \ki{k-unique,}\inddef{kunique score set@$k$-unique score set} 
if there exists exactly 1 score sequence of $k$-tournaments\index{ktournament@$k$-tournament} 
generating the given set. In the talk we investigate the following questions:
\begin{enumerate}
\item
characterization of the unique score sets of 1-tournaments;
\item
extension of the Reid's conjecture to 2-tournaments.
\end{enumerate}

\subsection{1-unique score sets\label{subsec3031}} 
At first we formulate a useful necessary condition.
\begin{lemma}\label{lemma3031m1} (Iványi\nevindex{Iványi, Antal Miklós} and Phong,\nevindex{Phong, Bui Minh} 2004) 
If $k \geq 1,$ then for any $(n,k)$-tournament 
holds that the sequence $\mathbf{s}$ is a solution for $\mathbf{r},$ then 
in the case $m = 1$ we have
\begin{equation}
n = 2r_1 + 1
\end{equation}
and in the case $m \geq 2$ we have
\begin{equation}
\frac{2r_1}{k} + 1 < n < \frac{2r_m}{k} + 1
\end{equation}
and
\begin{equation}
n \geq r_m + 1\koz.
\end{equation}
\end{lemma}
\begin{biz} If

\end{biz}
This lemma implies the exact answer for the case $m = 1.$
\begin{kov} (Iványi\nevindex{Iványi, Antal Miklós} and Phong,\nevindex{Phong, Bui Minh} 
2004) If $\mathbf{r} = \langle r_1 \rangle,$ then exactly the sequence 
$\mathbf{s} = \langle r_1^{2r_1 + 1} \rangle$ is a solution for $\mathbf{r}.$
\end{kov}
\begin{biz} Lemma \ref{lemmam3031m1} implies that only this solution is acceptable. One can check that it 
satisfies the required inequality and equality.
\end{biz}

Now we present a useful method of the investigation of the uniqueness. Let 
$\mathbf{r} = \langle a, a + d \rangle.$ Then according to the Reid-equa\-lity we get
$$2ax + 2(a + d)y = n(n - 1)$$
implying
\begin{equation}
y = \frac{n(n - 2a - 1)}{2d} \koz .\label{eqe14}
\end{equation}
But here only the values $n = 2a + 1 + i \ (i \in [1,2d - 1])$ are permitted where 
\begin{equation}
i \geq d + 1 - a \koz.
\end{equation} 

By substitution $a = (q - 1)d$ from (\ref{eqe14}) we get
\begin{equation}
y = \frac{(2qd - 2d + 2r + 1 + i)i}{2d}\koz.
\end{equation}
Here $y$ must be an integer, so transform this formula into
\begin{equation}
y = i(q - d) + \frac{i(2r + 1 + i)}{2d}\koz. \label{eqe15}
\end{equation} 
\begin{tetel} If $0 \leq a < b,$ then there exist positive integers $x$ and $y$ satisfying
$$ax \geq \frac{x(x - 1)}{2}$$
and
$$ax + by = \frac{(x + y)(x + y - 1)}{2}\koz.$$
In the following cases there is only one solution:
\begin{itemize}
\item
a = 0;
\item
d = 1;
\item
d = 2.
\end{itemize}
In the following case there are at least two solutions:
\begin{itemize}
\item
$d$ is odd and $3 \leq d \leq a.$
\end{itemize}
\end{tetel}
\begin{biz} a) Existence of a solution.
Let $d = b - a$ and $i = 2d - 2r -1.$ Then $n = 2(b -r),$ 
$y = q(2d - 2r -1), \ x = q(2r + 1)$ satisfy all requirements.
  
b) Uniqueness. If $a = 0,$ then $d = b,$ $q = 1$ and $y$ is integer only if $i = 2b - 1.$ So we get the unique 
$\langle 0^1, b^{2b - 1} \rangle$ solution.   

If $d = 1,$ then only $i = 1$ is permitted, implying the unique solution $\langle a^b,b^b \rangle.$

If $d = 2$ or $d$ is odd, then we also can analyse formula (\ref{eqe15}).
\end{biz}

This theorem left open the case when the difference $d$ is odd and the investigated set is sparse 
and also the case when the difference is an even number greater then 2. 

\subsection{2-unique score sets\label{subs2unique}}
Now we present a new form of Reid-problem for 2-tournaments.

For a fixed sequence $\mathbf{q}[m]= \langle q_1,\ldots,q_m \rangle$ with $q_1 < \cdots$ $ < q_m$ 
of positive integers, we shall 
denote by $\mathcal{G}(\mathbf{q}[m])$ the set $\mathcal{G}$ of sequences $\mathbf{g} =  
\langle g_1,\ldots,g_m \rangle$ such that

$$\sum_{i=1}^{k}q_ig_i~\ge ~ \left(\sum_{i=1}^{k}g_i\right)^2, ~~~ k \in [1:m-1]$$
and
$$\sum_{i=1}^{m}q_ig_i~=~ \left(\sum_{i=1}^{m}g_i\right)^2.$$

Here we also say that \textbf{g} is a solution for \textbf{q.} 

We wish to give necessary and sufficient conditions for $\mathbf{q}[m]$ to have a solution that is a nonempty  
$\mathcal{G}(\mathbf{q}[m]).$)
\bigskip
\begin{tetel} For the sequence $\mathbf{q}[1]=\langle q_1 \rangle,$ we have 
$\mathcal{G}(\mathbf{q}[1])=\langle q_1 \rangle.$ 
\end{tetel}
\begin{biz} If $\mathbf{q}[1] = \langle q_1 \rangle,$ then it is obvious that the solution 
of $q_1 g_1 = g_1^2$ is given in the form $g_1=q_1$. Hence we have $\mathcal{G}(\mathbf{q}[1])=\langle q_1 \rangle.$  
\end{biz}
\begin{tetel} Let $\mathbf{q}[2]=\langle q_1,q_2 \rangle$ be a sequence of positive integers 
with $d = q_2 - q_1 > 0.$  
Then $\mathcal{G}(\mathbf{q}[2])\neq \emptyset$ if and only if either 
$d\not\vert (q_1,q_2)$ or $d\vert (q_1,q_2)$ and there is a 
prime $p$ such that $p^2\vert d$.
\end{tetel}
\begin{biz} According to the definition of  
$\mathcal{G}(\mathbf{q}[m]),$ we need only find positive integers $g_1,g_2$ such that 
$q_1 \geq g_1$ and $q_1g_1 + q_2g_2 = (g_1 + g_2)^2.$ 

Let $q,~r$ be integers for which $q_2 = qd + r,$ where $0\le r<d.$ If $d \not\vert (q_1,q_2),$ 
then $r\neq 0$ and let $g_1 = rq$ and $g_2 =q_2- r(q + 1).$ Hence we have
$$g_1 = rq = r{q_2 -r \over {q_2 - q_1}} = r + r{q_1 -r \over {q_2 -q_1}}$$
$$<r + (R_1 - r) = R_1\koz,$$
$$g_2 = R_2 - r(q+1) =$$
$$q_2 - (q_2 - r){r \over{q_2 - q_1}} - r$$
$$>q_2 - (q_2 - r) - r = 0$$
and
$$q_1g_1 + q_2g_2 = q_1rq + q_2^2 - q_2r(q + 1)$$
$$ = q_2^2 + r(q_1q - q_2q + q_2) - 2q_2r=$$
$$=(q_2 - r)^2 = (g_1 + g_2)^2.$$
Now assume that $d \vert (q_1,q_2)$ and there is a prime $p$ such that $p^2 \vert d.$ In this case 
$r = 0$ and we choose $g_1,~g_2$ as follows:
$$g_1:={q_2 \over p}-{d \over {p^2}}~~\hbox{and}~~g_2:=g_1(p-1)\koz.$$
It is obvious that
$$g_1 > 0,~g_2 > 0~,~g_1 \le R_1$$
and
$$q_1g_1 + q_2g_2 = g_1(q_1 + (p - 1)q_2)$$
$$= g_1(pq_2 - d) =$$
$$= g_1p^2({q_2\over p}-{d\over {p^2}}) = (g_1p)^2 = (g_1 + g_2)^2.$$

Finally, assume that $d = 1$ or $d \vert (q_1,q_2)$ and $d$ is the product of distinct primes. 
If there are positive integers $g_1, g_2$ such that $q_1\ge g_1$ and 
$q_1g_1 + R_2g_2 = (g_1 + g_2)^2,$ then we have $d \vert g_1 + g_2$ and
$${1 \over d}(g_1 + g_2)^2-{q_1 \over d}(g_1 + g_2) = g_2>0\koz,$$ 
$${1\over d}(g_1+g_2)^2-{R_2\over d}(g_1+g_2)=-g_1 < 0\koz,$$
consequently
$${q_2\over d} = {q_1 \over d} + 1 > {g_1 + g_2\over d} > {q_1\over d}\koz.$$
This is impossible.
\end{biz} 
\begin{tetel}\label{th30two} \emph{Iványi, Phong, 2004} Let $\mathbf{q}[2] = <q_1,~q_2>$ be the sequence 
of positive integers with conditions $q_1 < R_2,$~$(q_1,q_2)=1$,~$2q_1>q_2$~~and~~$d:=q_2-R_1$~has 
$s$ distinct prime factors. Then 
$$\vert \mathcal{G}(\mathbf{q}[2]) \vert = 2^s - 1\koz.$$
\end{tetel}
\begin{biz} Since $d = q_2 - q_1 < q_1$ and $(q_1,q_2) = 1,$ the congruence $x^2\equiv q_2x\pmod d$ 
has $2^s-1$ solutions in positive integers less than $d.$ For each solution $x$ we 
set $g_1={x(q_2 - x)\over d}$ and $g_2 = (d - x){q_2 - x\over d}.$  
One can check that $g_1, ~ g_2$ satisfy conditions $q_1\ge g_1$ and $q_1g_1 + q_2g_2=(g_1 + g_2)^2.$ 
\end{biz}
\begin{gyak}
\ujgyak
How many ?
\ujgyak
Design an algorithm
\end{gyak}\index{unicity of score sets|)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Kings and serfs in tournaments\label{sec30Kings1t}}\index{kings and serfs in 1-tournaments|(}
Sociologists are often interested in determining the most \textit{dominant} actors in a social network. 
Moreover, dominance in animal societies is an important theme in ecology and population biology. 
Social networks are generally modelled as digraphs with vertices representing actors and arcs 
representing dominance relations among actors. The concept of ``king'' 
is very closely related to dominance in digraphs. Kings and serfs were initially introduced 
to study dominance in round-robin competitions. These concepts were latter extended to more general 
families of digraphs such as multipartite tournaments, quasi-transitive digraphs, 
semicomplete multipartite digraphs and oriented graphs. In this section our focus will be on algorithmic 
aspects of kings and serfs in tournaments and their applications in majority preference voting. 

A king in a tournament dominates every other vertex either directly or through another vertex. 
To make the idea more formal we define a \textit{path} of length $k$ from a vertex $u$ to a vertex 
$v$ in a tournament (or any digraph) as a sequence of arcs $e_{1}, e_{2},\ldots, e_{k}$ where $u$ 
is the initial vertex of $e_{1}$, $v$ is the terminal vertex of $e_{k}$ and the terminal vertex of 
$e_i$ is the same as the initial vertex of $e_{i+1}$, for all $1\leq i\leq k-1$. If there is a path 
of length 1 or 2 from a vertex $u$ to a vertex $v$, then $v$ 
is said to be \ki{reachable}\inddef{reachable vertex}  
from $u$ within two steps. Analogously, if there is a path of length $1,2,\ldots$ or $r$ from $u$ to $v$ 
then $v$ is said to be reachable from $u$ within $r$ steps. 
Let $T$ be an $n$-tournament. A vertex $u$ in $T$ is called an \ki{r-king,}\inddef{rking@$r$-king} 
where $1 \leq r \leq n-1,$ if every other vertex $v$ in the tournament is reachable within $r$ steps 
from $u.$ A vertex $u$ is called an \ki{r-serf}\index{rserf@$r$-serf} if $u$ is reachable within $r$
if $u$ is reachable within $r$ 
steps from every other vertex $v$ in $T.$ In particular, a 2-king is simply called a king and a 
2-serf is called a serf. 
\begin{figure}[!t]
\centering
\includegraphics{kingsandserfs}
\caption{A tournament with three kings $\{u,v,y\}$ and three serfs $\{u,v,x\}.$ 
Note that $z$ is neither a king nor a serf and $\{u.v\}$ are both kings and serfs.\label{fig:kingsandserfs}} 
\end{figure}

S. B. Maurer\nevindex{Maurer, Stephen B.} introduced the dual terms of king and serf in a delightful exposition 
of a tournament model for dominance in flocks of chicken. In his influential series of papers 
on dominance in animal societies, H. G. Landau\nevindex{Landau, H. G.} proved that every tournament 
has a king (although he did not use the word king). In fact, he showed the following. 
\begin{tetel}\label{max} \emph{(Landau, 1953)}
Every vertex of maximum score in a tournament is a king. 
\end{tetel}
The proof is quite intuitive. Suppose to the contrary that $u$ is a vertex with maximum score in a tournament 
$T$ and $u$ is not a king. Then there exists another vertex $v$ in $T$ such that $v$ is not reachable 
from $u$ within 2 steps. But this means that $u$ and all out-neighbours of $u$ are reachable 
from $v$ in 1 step and so $s(v)>s(u),$ a contradiction. Another classical result by 
J. W. Moon\nevindex{Moon, John W.} states that 
\begin{tetel}\label{NumberOfKings} \emph{(Moon, 1968)}
A tournament without transmitters (vertices with in-degree 0) contains at least three kings. 
\end{tetel}

It is natural to ask if the bound on the number of kings given in Theorem \ref{NumberOfKings} is tight. 
The answer is yes, as demonstrated by the following example. 

\begin{pelda}\label{threekings} Let $T$ be a tournament with vertex set $\{v_1, v_2,\ldots,v_5\}.$ 
Let us denote by $(u,v),$ an arc directed from $u$ to $v.$ Suppose that the arc set of $T$ 
consists of the arcs $(v_3, v_5),$ $(v_4, v_3),$ all arcs of the form $(v_{j-1}, v_{j}),$ 
with $1< j\leq 5$ and all arcs of the form $(v_{{j+2}},v_{j}),(v_{{j+3}},v_{j}),\ldots,(v_{{n}},v_{j})$ 
with $j=1,2,4.$ Then it can be easily verified (Exercise \ref{example}) that $T$ has no 
transmitters and $v_2,$ $v_3$ and $v_4$ are the only kings in $T.$  
\end{pelda} 

K. B. Reid\nevindex{Reid, K. Brooks} proved the existence of a tournament with an arbitrary number 
of vertices and an arbitrary number of kings, with few exceptions. 
\begin{tetel}\label{except} \emph{(Reid, 1982)}
For all integers $n\geq k \geq 1$ there exists a tournament on $n$ vertices with exactly $k$ 
kings except when $k = 2$ or when $n = k = 4$ (in which case no such $n$-tournament exists). 
\end{tetel}

Hence no tournament has exactly two kings. The above theorems can be stated just as well in terms of serfs. 
To see this, note that the \textit{converse} $T'$ of a tournament $T,$ obtained by reversing 
the arcs of $T,$ is also a tournament and that the kings and serfs of $T$ and $T'$ are interchanged. 

The \ki{king set}\inddef{king set} of a tournament consists of all kings in the tournament. 
We can define the \ki{serf set}\inddef{serf set} analogously. The problem of determining the king set 
of a tournament is very important both for theoretical and practical considerations. In voting theory 
literature, political scientists often refer to the uncovered set in majority preference voting. 
This uncovered set is actually the king set for the tournament whose vertices consist of the candidates 
to be elected and arcs represent the outcomes of the two-way race between candidates. 
Here we present a simple polynomial time algorithm for determining the king set of a tournament. 
Given an $n$-tournament $T,$ let us define an $n \times n$ matrix $D^{+}_{T}$ as
\begin{equation}\label{outdeg}
(D^+_T)_{ij} = \left \{
\begin{array}{l}
\ 1 \ \ \ \ \hbox{if }  (v_i,v_j)  \textrm{ is an arc of } T\koz, \\ 
\ 0 \ \ \ \ \hbox{ otherwise}\koz.	
\end{array}  \right .
\end{equation}

We call $D^{+}_{T},$ the \textit{out-degree matrix} of $T.$ When there is no danger of ambiguity we will 
drop the subscript $T$ and simply denote the out-degree matrix by $D^{+}.$ \textsc{King-Set} 
takes a tournament $T(V,A)$ as input, calculates the out-degree matrix $D^{+}$ of $T$ and uses 
it to generate the king set $K$ of $T.$ Let $O$ be the $n \times n$ zero matrix and let $I$ be the 
$n \times n$ identity matrix. 

\begin{alg}{King-Set$(V,A)$}\inddef{\textsc{King-Set}}
1 \' $D^{+} = $\\
2 \' $K = \emptyset$ \\
3 \' \key{for} \= $i = 1$ \key{to} $n$\\
4 \'           \> \key{for} \= $j = 1$ \key{to} $n$\\
5 \'           \>           \> \key{if} \= $(v_{i},v_{j})\in A$ \\
6 \'           \>           \>          \> $(D^{+})_{{ij}} = 1$ \\
7 \' $M = I+D^{+}+(D^{+})^{2}$\\
8 \' $K = \{v_{i} \in V \vert \forall v_{j} \in V, (M)_{{ij}} \neq 0\}$\\
9 \'       \> $N_n$ dominates $D^(1)$ \\
9 \'  \key{return} $K$
\end{alg}

\subsubsection{Algorithm description} 
The algorithm works on the same principle as the algorithm for finding the number of paths, 
from one vertex to another, in a digraph (Exercise \ref{path} asks you to derive this algorithm). 
The $(i,j)$ entry of the matrix $(D^{+})^{2}$ is equal to the number of paths of length two from vertex 
$v_{i}$ to vertex $v_{j}$ (check this!). Therefore, the $(i,j)$ entry of matrix $D^{+}+(D^{+})^{2}$ 
counts the number of paths of length one or two from $v_{i}$ to $v_{j}$; and if vertex $v_{i}$ is a king, 
all entries in the $i^{th}$ row of $I+D^{+}+(D^{+})^{2}$ must be non-zero. 

The computational complexity of Algorithm \textsc{King-Set} depends on the way $(D^{+}_{T})^{2}$ is computed. 
If naive matrix multiplication is used, the algorithm runs in $\Theta(n^{3})$ time. 
However, using the fast matrix multiplication by Coppersmith\nevindex{Coppersmith, Don} and 
Winograd,\nevindex{Winograd, Shmuel} the running time can be reduced to $O(n^{2.38}).$ 
The Reader should note that by using the duality of kings and serfs, \textsc{King-Set} can be adapted 
for finding the serf set of a tournament. 

\subsubsection{King sets in majority preference voting} 
Kings frequently arise in political science literature. A 
\ki{majority preference voting}\inddef{majority preference voting} procedure asks each voter to rank 
candidates in order of preference. The results can be modeled by a tournament where vertices represent 
the candidates and arcs point toward the loser of each two way race, where candidate $u$ defeats 
candidate $v$ if some majority of voters prefer $u$ to $v.$ Political scientists are often 
interested in determining uncovered vertices in the resulting tournament. A vertex $u$ is said 
to \textit{cover}\index{vertex cover} another vertex $v$ if $u$ defeats $v$ 
and also defeats every vertex that $v$ defeats. 
  
The covering relation is clearly transitive and has maximal elements, called 
\ki{uncovered vertices.}\inddef{uncovered vertex} An uncovered vertex $u$ has the strategically 
important property that $u$ defeats any other vertex $v$ in no more than two steps, i.e., either 
\begin{enumerate}
\item $u$ defeats $v$ or 
\item there is some third alternative $w$ such that $u$ defeats $w$ and $w$ defeats $v$. 
\end{enumerate}
Thus an uncovered vertex is actually a king. In fact the uncovered set, consisting of all uncovered vertices, 
is precisely the set of all kings (see Exercise \ref{uncover}).

The idea behind finding kings in a tournament can be easily extended to finding $r$-kings 
for any positive integer $r.$ 

\begin{alg}{$r$King-Set$(V,A,r)$}\inddef{rKingSet@$r$\textsc{King-Set}}
1 \' $D^{+} = 0$\\
2 \' $K = \emptyset$ \\
3 \' \key{for} \= $i = 1$ \key{to} $n$\\
4 \'           \> \key{for} \= $j = 1$ \key{to} $n$\\
5 \'           \>           \> \key{if} \= $(v_{i},v_{j})\in A$ \\
6 \'           \>           \>          \> $(D^{+})_{{ij}} = 1$ \\
7 \' $M =I+D^{+} + \ldots+(D^{+})^{r}$\\
8 \' $K = \{v_{i} \in V \vert \forall v_{j}\in V, (M)_{{ij}}\neq 0\}$\\
9 \'  \key{return} $K$\\
\end{alg}

The above algorithm runs in $O(rn^3)$ if the matrix multiplications are performed naively, 
and in $O(rn^{2.38})$ time if fast matrix multiplication is incorporated.

As we have seen, kings dominate in tournaments. However, there exists a stronger notion of dominance 
in tournaments in the form of strong kings. Let us write $u\rightarrow v$ 
to denote that $u$ defeats $v$ in a tournament $T,$ or in other words $(u,v)$ is an arc of $T.$ 
If $U_{1}$ and $U_{2}$ are disjoint subsets of vertices of $T$ then we write $U_{1}\rightarrow U_{2}$ 
to denote that all vertices in $U_{1}$ defeat all vertices in $U_{2}.$ We define 
$B_{T}(u, v) = \{w\in V-\{u,v\}: u\rightarrow w \mbox{ and } w\rightarrow v\},$ where $V$ denotes 
the vertex set of $T.$ Let $b_{T}(u, v) = \vert B_{T}(u, v)\vert.$ When no ambiguity arises, 
we drop the subscript $T$ from the notation. 

A vertex $u$ in a tournament $T$ is said to be a \ki{strong king}\inddef{strong king} if 
$u\rightarrow v$ or $b(u,v)>b(v,u)$ for every other vertex $v$ of $T.$

Note that $b_{T}(u, v)$ is the number of paths of length two through which $v$ is reachable from $u.$ 
Therefore, $b_{T}(v_{i}, v_{j}) = ((D^{+}_{_T})^{2})_{{ij}},$ where $D^{+}_{T}$ is the out-degree 
matrix of $T.$

Obviously, it is not true that every king is a strong king. For example, Figure 
\ref{figtwostrongkings} demonstrates a tournament with three kings, namely $x,$ $y$ and $z.$  
However, only $x$ and $y$ are strong kings as $b(z,x) < b(x,z).$ 
Figure \ref{figtwostrongkings} also shows that when searching for the most dominant vertex 
in real life applications, a king may not be the best choice (vertex $z$ is a king, 
but it defeats only one vertex and is defeated by all other vertices). Therefore, choosing a strong king 
is a better option. This intuition is further confirmed by the fact that, in the probabilistic sense 
it can be shown that in almost all tournaments every vertex is a king. 
\begin{figure}[h]
\centering
\includegraphics{twostrongkings}
\caption{A tournament with three kings and two strong kings}
\label{figtwostrongkings}
\end{figure}

We have already shown that every tournament has a king. 
We now prove that every tournament has a strong king. 
\begin{tetel}\label{stronking} (???, ????)
Every vertex with maximum score in a tournament is a strong king.
\end{tetel}
\begin{biz} Suppose $u$ is a vertex with maximum score in a tournament $T$ that is not a strong king. 
Then there is a vertex $v$ in $T$ such that $v \rightarrow u$ and $b(u,v)\leq b(v,u).$ Let $V$ be 
the vertex set of $T.$ Define 
\begin{equation*}
W = \{w\in V-\{u,v\}: u\rightarrow w \textnormal{ and } v\rightarrow w\}\koz. 
\end{equation*}
Then $s(u) = b(u, v) + \vert W\vert $ and $s(v) = b(v,u) +\vert W\vert + 1.$ This implies that 
$s(u) < s(v),$ a contradiction.
\end{biz}



The problem of finding strong kings is no harder than finding kings in tournaments. 
Like \textsc{King-Set}, we present a polynomial time algorithm for finding all strong kings 
in a tournament using the out-degree matrix $D^+.$ 

\begin{alg}{Strong-Kings$(V,A)$}\inddef{\textsc{Strong-Kings}}
1 \' $D^+ = 0$\\
2 \' $K = \emptyset$ \\
3 \' \key{for} \= $i = 1$ \key{to} $n$\\
4 \'           \> \key{for} \= $j = 1$ \key{to} $n$\\
5 \'           \>           \> \key{if} \= $(v_{i},v_{j})\in A$ \\
6 \'           \>           \>          \> $D^+_{ij} = 1$ \\
7 \' $M = D^+ + (D^+)^2$\\
8 \' $K = \{ v_i \in V \ \vert \ \forall j (1\leq j\leq n \textnormal{ and } j\neq i), M_{ij} > M_{ji} \}$\\
9 \'  \key{return} $K$\\
\end{alg}

\textsc{Strong-Kings} has the same order of running time \textsc{King-Set}. 

So far we have been focusing on finding certain type of dominant vertices (like kings and strong kings) 
in a tournament. Another very important problem is to construct tournaments with a certain number 
of dominant vertices. Maurer posed the problem of determining all 4-tuples $(n,k,s,b)$ 
for which there exists a tournament on $n$ vertices with exactly $k$ kings and $s$ serfs such 
that $b$ of the kings are also serfs. Such a tournament is called an $(n,k,s,b)$-tournament. 
For example the tournament given in Figure \ref{figkingsandserfs} is a $(5,3,3,2)$-tournament. 
Reid gave the following characterization of such 4-tuples.

\begin{tetel}
Suppose that $n \geq k \geq s \geq b \geq 0$ and $n > 0.$ There exists an $(n,k,s,b)$-tournament 
if and only if the following conditions hold.
\begin{enumerate}
	\item $n\geq k+s-b$, 
	\item $s\neq 2$ and $k\neq 2$,
  \item either $n= k= s= b\neq 4$ or $n>k$ and $s>b$,
  \item $(n,k,s,b)$ is none of $(n,4,3,2)$, $(5,4,1,0)$, or $(7,6,3,2)$.
\end{enumerate}
\end{tetel}

However, the corresponding problem for strong kings has been considered only recently. 
For $1\leq k \leq n,$ a tournament on $n$ vertices is called an $(n, k)$-tournament if it has exactly 
$k$ strong kings. The construction of $(n,k)$- tournaments follows from the results proved by Chen, Chang, Cheng and Wang in 2004. The results imply the existence of $(n,k)$-tournaments for all $1\leq k\leq n$ satisfying 
\begin{eqnarray}
k \neq n - 1, \ \mbox{when } n \mbox{ is odd} \\
\ \ \ \ \ \ \ \ \ k \neq n, \ \ \ \ \ \mbox{when } n \mbox{ is even\koz.}
\end{eqnarray}

Algorithm $nk$-\textsc{Tournament} takes positive integers $n$ and $k$ as input satisfying the constraints 
(26.2) and (26.3) and outputs an $(n,k)$-tournament and the set $K$ of its strong kings. 
Also for any vertex $u$ of a tournament $T,$ we adopt the notation of Chen et al. in letting 
$O(u)$ (respectively, $I(u)$) denote the set of vertices reachable from $u$ in one step 
(respectively, set of vertices from which $u$ is reachable in one step). Note that $O(u)$ and $I(u)$ 
are often referred to as the first out-neighbourhood and first in-neighbourhood of $u$ respectively. 

\begin{algN}{$nk$-Tournament$(n,k)$}\inddef{nktournament@$nk$-\textsc{Tournament}}
1 \' $K = \emptyset$ \\
3 \' $T =$ null digraph on $n$ verices\\
4 \' \key{if} \= $k$ is odd\\
5 \'          \> $T = T_k$ \\
6 \'          \> $K = \{v_{1},\ldots,v_{k}\}$ \\
7 \' \key{if} \= $n \neq k$ \\
8 \'          \> \key{for} \= $i = k + 1$ \key{to} $n$ \\
9 \'         \>           \> $V = V \cup \{v_{i}\}$ \\
10 \'         \>           \> $A = A\cup \{(u,v_{i}): u\in V - \{v_{i} \} \}$ \\ 
11 \' \key{if} \= $k$ is even \\
12 \'          \> $T = T_{k-1}$ \\
13 \'          \> $V = V \cup \{x,y,z \}$ \\
14 \'          \> $K = \{v_{1},\ldots,v_{k-3},x\}$ \\
15 \'          \> choose $u \in V$ arbitrarily \\
16 \'          \> $A = A \cup \{(v,x): v\in O(u)\}$\\
17 \'          \> $A = A \cup \{(x,v): v\in \{u,y\} \cup I(u) \}$ \\
18 \'          \> $A = A \cup \{(v,y): v\in \{u\}\cup I(u)\cup O(u)\}$ \\
19 \'          \> $A = A \cup \{(v,z): v\in \{u\} \cup I(u)\}$ \\
20 \'          \> $A = A \cup \{(z,v): v\in O(u)\}$ \\
21 \'          \> \key{if} \= $n \neq k + 2$ \\
22 \'          \>          \> \key{for} \= $i = k + 1$ \key{to}  $n$ \\
23 \'          \>          \>           \> $V = V \cup \{v_{i}\}$ \\
24 \'          \>          \>           \> $A = A\cup \{(u,v_{i}): u\in V-\{v_{i}\}\}$ \\
25 \' \key{return} $T,K$
\end{algN}

\subsubsection{Algorithm description} The algorithm consists of performing two separate inductions 
 to generate an $(n,k)$-tournament, one for odd $k$ and one for even $k.$. 
 If $k$ is odd then we start by letting $T=T_k,$ the regular tournament on $k$ vertices 
 (which always exists for odd $k$), and inductively add $n-k$ vertices to $T$ that are defeated 
 by all the vertices of $T_k.$ Thus the resulting tournament has $n$ vertices and $k$ kings 
 (the vertices of $T_k$). The construction for even $k$ is a bit more involved. We start with 
 $T=T_{k-1}.$ Note that every vertex of $T_{k-1}$ has score $m = \textbinom{n-4}{2}.$ 
 We then add three vertices $x,$ $y$ and $z$ and several arcs to $T_{k-1}$ such that for a fixed 
 existing vertex $u$ of $T_{k-1}.$
\begin{itemize}
 \item	$O(u) \rightarrow \{x\} \rightarrow \{u,y\}\cup I(u),$
 \item $\{u\}\cup I(u)\cup O(u)\rightarrow \{y\} \rightarrow \{x, z\},$
 \item $\{u\}\cup I(u)\rightarrow \{z\} \rightarrow O(u).$
\end{itemize}

\begin{figure}[!t]
\centering
\includegraphics{nk}
\caption{Construction of an $(n,k)$-tournament with even $k$.\label{fignk}}
\end{figure}

The resulting tournament $T$ (illustrated in Figure \ref{fignk}) has $k+2$ vertices with scores 
$s(x)=\vert I(x)\vert+2=m+2,$ $s(y)=2,$ $s(z)=\vert O(x)\vert = m$ and $s(v) = m+2,$, for all vertices 
$v$ of $T_{k-1}.$ Now by Theorem \ref{stronking} all vertices $v$ of $T_{k-1}$ and the new vertex 
$x$ are strong kings of $T,$ while $y$ and $z$ are not (Exercise \ref{maxscore}). Thus $T$ is a 
$(k+2, k)$-tournament that can now be extended to an $(n,k)$-tournament by adding $n-k-2$ 
more vertices that are defeated by all the existing vertices of $T$ (just like in the case of odd $k$).  

$nk$-\textsc{Tournament} runs in quadratic time as it takes $O(n^{2})$ operations 
to construct a regular tournament and the remaining steps in the algorithm are completed in linear time.  
\begin{gyak}
\ujgyak\label{path}
The out-degree matrix $D^+$ of an $n$-vertex oriented graph is an $n \times n$ matrix 
whose $(i,j)$ entry is given by $d_{ij}=\mbox{number of arcs directed from }v_i \mbox{ to } v_j.$ 
Describe an algorithm based on the out-degree matrix for finding the number of paths of length 
$k<n$ between any two vertices of the graph. 
\ujgyak\label{example}
Draw the tournament discussed in Example \ref{threekings} and show that it has no transmitters 
and exactly three kings.  
\ujgyak\label{example2}
Using the 5-tournament in Example \ref{threekings} give the construction of an $n$-tournament 
with no transmitters and exactly three kings. 
\ujgyak\label{allserf}
For every odd number $n \geq 3,$ give an example of an $n$-tournament, in which all vertices are serfs.
\ujgyak\label{nonking}
Prove that any tournament on 4 vertices contains a vertex which is not a king.
\ujgyak\label{bipartite}
A \textit{bipartite tournament}\gyakindex{bipartite tournament} is an orientation of a complete 
bipartite graph. A vertex $v$ of a bipartite 
tournament is called a 4-king\footnote{Several bipartite and multipartite tournaments have no 2-king 
or 3-king. However, a multipartite tournament with at least one vertex of in-degree zero contains 
a 4-king. Therefore it is logical to look for 4-kings in a multipartite tournament.\gyakindex{multipartite tournament}} 
(or simply a king) if there is a directed path of length 4 from $v$ to every other vertex of the tournament. 
\noindent Derive an algorithm to obtain all 4-kings in a bipartite tournament and compare 
its complexity with the complexity of $r$-\textsc{Kings} for finding $r$-kings in ordinary tournaments. 
\ujgyak\label{multipartite}
As the name suggests a multipartite tournament is an orientation of a complete multipartite graph. 
Extend the algorithm obtained in Exercise \ref{bipartite} to find all 4-kings 
in multipartite tournaments. Again compare the performance of your algorithms with $r$-\textsc{Kings}.  
\ujgyak\label{uncover}
Prove that the uncovered set arising in majority preference voting is exactly the king set 
of the majority preference tournament. 
\ujgyak\label{maxscore}
Show that when $k$ is even, the output of $nk$-\textsc{Tournament} has exactly $k$ kings. 
\end{gyak}\index{kings and serfs in 1-tournaments|)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Weak kings in oriented graphs\label{sec30Kings2t}}\index{weak kings in 2-tournaments|(}
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 $(u,v)$ denotes that actor $u$ 
has some relation with actor $v.$. 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 \ref{secKingsAndSerfs}, we have already defined kings and $r$-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 ``\textit{weak kings}'' was initiated in 
2008 by S. Pirzada\nevindex{Pirzada, Shariefuddin} and N. A. Shah.\nevindex{Shah, N. A.} 
Here we follow their notation. For any two vertices $u$ and $v$ in an oriented graph $D,$, 
one of the following possibilities exist.
\begin{enumerate}
	\item An arc directed from $u$ to $v$, denoted by $u(1-0)v$ (i.e., $u$ defeats $v$).
  \item An arc directed from $v$ to $u$ , denoted by $u(0-1)v$ (i.e., $v$ defeats $u$).
  \item There is no arc from $u$ to $v$ or from $v$ to $u$ , and is denoted by $u(0-0)v$ (i.e., there is a tie).\\
\end{enumerate}

A \ki{triple}\inddef{triple} in an oriented graph is an induced oriented subgraph 
with three vertices. For any three vertices $u,$ $v$ and $w,$ the triples of the form 
$u(1-0)v(1-0)w(1-0)u,$ $u(1-0) v(1-0)w(0-0)u,$ $u(0-0)v(1-0)w(1-0)u$ or $u(1-0)v(0-0)w(1-0)u$ 
are said to be \ki{intransitive,}\inddef{intransitive triple}\index{triple!intransitive triple} 
while the triples of the form 
$u(1-0)v(1-0)w(0-1)u,$ $u(0-1)v(1-0)w(1-0)u,$ $u(1-0)v(0-1)w(1-0)u,$ $u (1-0)v(0-1)w(0-0)u,$ 
$u(0-1)v(0-0)w(1-0)u,$ $u(0-0)v(1-0)w(0-1)u,$ $u(1-0)v(0-0)w(0-1)u,$ $u(0-0)v(0-1)w(1-0)u,$ 
$u(0-1)v(1-0)w(0-0)u,$ $u(1-0)v(0-0)w(0-0)u,$ $u(0-1)v(0-0)w(0-0)u,$ $u(0-0)v(1-0)w(0-0)u,$ 
$u(0-0)v(0-1)w(0-0)u,$ $u(0-0)v(0-0)w(1-0)u$ or $u(0-0)v(0-0)w(0-1)u$ are said to be 
\ki{transitive.}\inddef{transitive triple}\index{triple!transitive triple} 
An oriented graph is said to be \ki{transitive}\inddef{transitive oriented graph} 
if all its triples are transitive. The converse $\overline{D}$ of an oriented graph $D$ 
is obtained by reversing each arc of $D$.\\

Let $u$ and $v$ be vertices in an oriented graph $D$ such that either $u(1-0)v$ or $u(0-0)v$ or 
$u(1-0)w(1-0)v$ or $u(1-0)w(0-0)v$ or $u(0-0)w(1-0)v$ for some vertex $w$ in $D.$ 
Then $v$ is said to be weakly reachable within two steps from $u.$ If either $u(1-0)v,$ 
or $u(1-0)w(1-0)v$ for some $w$ in $D,$ then $v$ is reachable within two steps from $u.$\\

A vertex $u$ in an oriented graph $D$ is called a \ki{weak king}\inddef{weak king} if every other vertex 
$v$ in $D$ is weakly reachable within two steps from $u.$ A vertex $u$ is called a \ki{king}\inddef{king} 
if every other vertex $v$ in $D$ is reachable within two steps from $u.$ 
A vertex $u$ in an oriented graph $D$ is called a \ki{weak serf}\inddef{weak serf} 
if $u$ is weakly reachable within two steps from every other vertex in $D,$ 
and a vertex $u$ in $D$ is called a \ki{serf}\inddef{serf} if $u$ is reachable 
within two steps from every other vertex $v$ in $D.$ 
\begin{figure}[!t]
\centering
\includegraphics[width=10cm,height=5cm]{p2a}
\caption{Six vertices and six weak kings.\label{figp2a}}
\end{figure}

\begin{figure}[!t]
\centering
\includegraphics[width=10cm,height=5cm]{p2b}
\caption{Six vertices and five weak kings.\label{figp2b}}
\end{figure}

\begin{figure}[!t]
\centering
\includegraphics[width=10cm,height=5cm]{p2c}
\caption{Six vertices and four weak kings.\label{figp2c}}
\end{figure}

\begin{figure}[!t]
\centering
\includegraphics[width=10cm,height=5cm]{p2d}
\caption{Six vertices and three weak kings.\label{figp2d}}
\end{figure}

\begin{figure}[!t]
\centering
\includegraphics[width=10cm,height=5cm]{p2e}
\caption{Six vertices and two weak kings.\label{figp2e}}
\end{figure}

We note that there exist oriented graphs on $n$ vertices with exactly $k$ kings 
for all integers $n\geq k\geq 1,$ with the exception of $n = k = 4.$ Theorem \ref{except} 
guarantees the existence of complete oriented graphs (tournaments) with $n$ vertices and 
exactly $k$ kings for all integers $n\geq k\geq 1,$ with the exceptions $k = 2$ and $n = k = 4.$ 
An oriented graph $D$ with exactly two kings can be constructed as follows. 
Let $V=\{ v_{1},v_{2},\ldots,v_{n}\}$ be the vertex set of $D,$ 
with arcs defined as $v_{1}(1-0)v_{i},$ for $i = 2,4,\ldots,n$; $v_{1}(0-1)v_{3}$; $v_{2}(1-0)v_{3}$ 
and $v_{2}(1-0)v_{i}$, for $4\leq i\leq n$; and for all other $i\neq j,$   
$v_{i}(0-0)v_{j}.$ The vertices $v_1$ and $v_3$ are the only kings in $D$ 
(Exercise \ref{exactlytwokings}).

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 $D$ be the incomplete oriented graph with 4 vertices, 
all of whom are kings. Then $D$ 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 \ref{except}. 

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 \ref{secScoreSetsInOriented}. 
Considering Theorem \ref{max}, 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: 

\begin{pelda}\label{counterexample}
Consider the oriented graph $D$ shown in Figure \ref{figcounter}. The scores of vertices 
$v_1,$ $v_2,$ $v_3$ and $v_4$ are respectively 2, 3, 3 and 4. Clearly, $v_4$ is a vertex of maximum 
score but is not a king as $v_1$ is not reachable within two steps from $v_4$. However, $v_4$ is a weak king.
\begin{figure}[!t]
\centering
\includegraphics{counter}
\caption{Vertex of maximum score is not a king.\label{figcounter}}
\end{figure}

Now consider the oriented graph $D^*$ with vertices $u_1,$, $u_2,$ $u_3,$ $u_4$ and $u_5,$ 
and arcs defined by $u_{1}(1-0)u_{2},$ $u_{2}(1-0)u_{i},$ for $i = 3, \ 4, q 5$ and $u_i(0-0)u_j$ 
for all other $i\neq j.$ Clearly, $s(u_{1}) = 5,$ $s(u_2) = 6,$ $s(u_3)= 3,$ $s(u_4) = 3,$ 
and $s(u_{5})= 3.$ Evidently, $u_1$ is a king in $D^*$ whereas the vertex $u_2$ of maximum score is not a king. 
\end{pelda}

However, we do have the following weaker result.
\begin{tetel}\label{maxweak}
If $u$ is a vertex with maximum score in a 2-tournament $D,$ then $u$ is a weak king.
\end{tetel}
\begin{biz} Let $u$ be a vertex of maximum score in $D,$ and let $X,$ $Y$ and $Z$ be 
respectively the set of vertices $x,$ $y,$ and $z$ such that $u(1-0)x,$ $u(0-0)y,$ 
and $u(0-1)z.$ Let $\vert X \vert=n_1,$ $\vert Y \vert=n_2$ and $\vert Z \vert=n_3.$ 
Clearly, $s(u)=2n_1+n_2.$ If $n_3 = 0,$ the result is trivial. So assume that 
$n_3\neq 0.$ We claim that each $z \in Z$ is weakly reachable within two steps from $u.$ 
If not, let $z_0$ be a vertex in $Z$ not weakly reachable within two steps from $u.$ 
Then for each $x \in X$ and each $y \in Y,$ $z_{0}(1-0)x,$ and $z_0(1-0)y$ or $z_0(0-0)y.$ 
In case $z_0(1-0)x$ and $z_0(1-0)y$ for each $x\in X$ and each $y\in Y,$ 
then $s(z_0)\geq 2+2n_1+2n_2 = s(u)+n_2 + 2 > s(u).$ which contradicts the choice of $u.$ 
If  $z_0(1-0)x$ and $z_0(0-0)y$ for each $x\in X$ and each $y\in Y,$ then 
$s(z_0)\geq 2+2n_1+n_2 = s(u)+2 > s(u),$ again contradicting the choice of $u.$ 
This establishes the claim, and hence the proof is complete.
\end{biz}


We now consider the problem of finding all weak kings in an oriented graph 
(as kings can be determined by applying Algorithm \ref{KingSet1}). Let $D^{-}$ and $D^{+}$ 
respectively denote the in-degree and out-degree matrix of an oriented graph $D(V,A)$ with $n$ vertices. 
Also let $O$ and $J$ denote the $n \times n$ zero matrix and all-ones matrix respectively. 

\begin{algN}{Weak-Kings$(V,A)$}\inddef{\textsc{Weak-Kings}}
1 \' $D^+ = 0$\\
2 \' $D^- = 0$\\
3 \' $K = \emptyset$ \\
4 \' \key{for} \= $i = 1$ \key{to} $n$ and $j = 1$ \key{to} n\\
5 \'           \> \key{for} \= $j = 1$ \key{to} $n$\\
6 \'           \>           \> \key{if} \ \ \ \= $(v_{i},v_{j})\in A$ \\
7 \'           \>           \>                \> $D^+_{ij} = 1$ \\
8 \'           \>           \> \key{else}     \> \key{if} \= $(v_{i},v_{j}) \in A$ \\
9 \'           \>           \>                \>          \> $D^-_{ij} = 1$ \\
10 \' $M = J - D^-$ \\
11 \' $M = D^+ + (D^+)^2$\\
12 \' $N = M + M D^+ + D^+ M$ \\
13 \' $K = \{v_i \in V  \ \vert \ \forall v_j \in V, (N)_{ij} \neq 0 \}$ \\
14 \'  \key{return} $K$\\
\end{algN}

Algorithm \ref{WeakKings} returns the set of all weak kings of an oriented graph. Exercise \ref{weak} 
asks you to prove that the algorithm works correctly and to determine its running time. 

Indeed, it is also possible to extend Theorem \ref{NumberOfKings} to weak kings in oriented graphs 
as an oriented graph $D$ without transmitters (vertices of in-degree 0) has at least three weak kings. 
To see this let $u$ be a vertex of maximum score in the oriented graph $D$. 
Clearly, by Theorem \ref{maxweak}, $u$ is a weak king. As $D$ has no transmitters, 
there is at least one vertex $v$ such that $v(1-0)u.$ Let $S$ be the set of these vertices $v,$ 
and let $v_{1}$ be a vertex of maximum score in $S.$ Let $X,$ $Y$ and $Z$ respectively be the set 
of vertices $x,$ $y$ and $z,$ other than $u,$ with $v_{1}(1-0)x,$ $v_{1}(0-0)y$ and $v_{1}(0-1)z.$ 
Assume that $\vert X\vert=n_{1},$ $\vert Y\vert=n_{2},$ and $\vert Z\vert=n_{3}$ so that 
$s(v_1) = 2n_1 + n_2 + 2.$ We note that all vertices of $Z$ are weakly reachable within two steps from 
$v_1.$ If this is not the case, let $z_0$ be a vertex which is not weakly reachable within two steps 
from $v_1.$ Then  $z_0(1-0)u,$ and (a) $z_{0}(1-0)x$ and (b) $z_{0}(1-0)y$ or $z_{0}(0-0)y$ 
for each $x \in X$ and each $y \in Y.$

If for each $x$ in $X$ and each $y$ in $Y,$ $z_{0}(1-0)x$ and $z_{0}(1-0)y,$ then $s(z_0) \geq 2n_1 + 2n_2 + 4 
= s(v_1) + n_2 + 2 > s(v_1).$ This contradicts the choice of $v_1.$ If for each $x$ in $X$ and each 
$y$ in $Y,$ $z_0(1-0)x$ and $z_0(0-0)y,$ then $s(z_{0}) \geq 2n_1 + n_2 + 4 > s(v_1),$ 
again contradicting the choice of $v_1.$ This establishes the claim, and thus $v_1$ is also a weak king.
 
Now let $W$ be set of vertices $w$ with $w(1-0)v_1$ and let $w_1$ be the vertex of maximum score in $W.$ 
Then by the same argument as above, every other vertex in $D$ is weakly reachable within two steps from $w_1,$ 
and so $w_1$ is a weak king. Since $D$ is asymmetric, and in $D$ we have $w_1(1-0)v_1$ and $v_1(1-0)u,$ 
therefore $u,$ $v_1$ and $w_1$ are necessarily distinct vertices. Hence $D$ 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 $n$ vertices with exactly $k$ weak kings, for all integers $n \geq k \geq 1.$ 
The following algorithm constructs such an oriented graph. 

\begin{algN}{$k$-Weak-Kings$(n,k)$}\inddef{nkweakkings@$nk$-\textsc{Weak-Kings}}
1 \' $V = \{ x, y, u_1, u_2, \ldots, u_{n-2} \}$ \\
2 \' $x(0-0)y$ \\
3 \' \key{if} \= $k > 2$ \\
4 \'          \> \key{for} \= $i = 1$ \key{to} $n - 2$ \\
5 \'          \>           \> $u_i(1-0)x $ \\
6 \'          \>           \> $u_i(0-1)y$  \\
7 \'          \>           \>  \\
8 \'          \> \key{for} \> $i = n - 3$ \key{downto} $k - 2$ \\
9 \'          \>           \> $u_{n-2}(1-0)u_i$   \\
10 \'         \> \key{for} \> $i = k - 3$ \key{downto} $1$ \\
11 \'         \>           \> $u_{n-2}(0-0)u_i$ \\
12 \'         \> $K = \{ x,y,u_{n-2} \} \cup \{ u_i \ \vert \ i = 1, \ldots, k-3 \}$ \\
13 \'         \> \key{else} \= \key{if} \ \ \ \= $k = 2$ \\
14 \'         \>            \>                \> \key{for} \= $i = 1$ \key{to} $n - 2$ \\
15 \'         \>            \>                \>           \> $x(1-0)u_{i}$ \\ 
16 \'         \>            \>                \>           \> $y(1-0)u_{i}$ \\
17 \'         \>            \>                \> \key{for} \= $j = 1$ \key{to} $n - 2$ \\
18 \'         \>            \>                \>           \> \key{if} \= $i \neq j$ \\
19 \'         \>            \>                \>           \>          \> $u_i(0-0)u_j$ \\
20 \'         \>            \>                \> $K = \{ x,y \} $ \\
21 \'         \>            \> \key{else}     \> $x(1-0)u_i$ \\
22 \'         \>            \>                \> $u_1(1-0)y$ \\ 
23 \'         \>            \>                \> \key{for} \= $i = 2$ \key{to} $n - 2$ \\ 
24 \'         \>            \>                \>           \> $u_1(1-0)u_i$ \\
25 \'         \>            \>                \>           \> $x(1-0)u_i$ \\
26 \'         \>            \>                \>           \> $y(1-0)u_i$ \\
27 \'         \>            \>                \> $K = \{ u_1 \}$ \\
28 \' \key{return} $V,A,K$\\
\end{algN}

\subsubsection{Algorithm description} 
When $k = n,$ the algorithm defines the arcs of a 2-tournament $D$ 
with vertex set $V = \lbrace x, y, u_{1}, u_{2},\cdots, u_{n-2}\rbrace$ as 

$x(0-0)y,$ 

$u_{i}(1-0)x$ and $u_{i}(0-1)y$ for all $1\leq i\leq n-2,$

$u_{i}(0-0)u_{j}$ \ for all $i\neq j$ and $1\leq i \leq n-2$, $1\leq j\leq n-2,$ 

Clearly, $x$ is a weak king as $x(0-0)y$ and $x(0-0)y(1-0)u_{i}$  for all $1\leq i\leq n-2.$. 
Also $y$ is a weak king as $y(0-0)x$ and $y(1-0)u_{i}$ for all $1\leq i\leq n-2.$ 
Finally, every $u_{i}$ is a weak king, since  $u_{i}(0-0)u_{j},$ for all  $i\neq j$ and $u_{i}(1-0)x$ 
and  $u_{i}(1-0)x(0-0)y.$ Thus $D$ contains exactly $n$ weak kings.

If $n=k-1,$ the algorithm creates one additional arc $u_{n-2}(1-0)u_{n-3}$ in $D.$ 
The resulting oriented graph contains exactly $n-1$ weak kings, since now $u_{n-2}$ 
is not weakly reachable within two steps from $u_{n-3}$ and so $u_{n-3}$  is not a weak king.
  
If $n=k-2$ then the algorithm creates two additional arcs in $D.$ namely $u_{n-2}(1-0)u_{n-3}$ and 
$u_{n-2}(1-0)u_{n-4}.$ Thus $D$ now contains exactly $n-2$ weak kings, with $u_{n-3}$ and $u_{n-4}$ 
not being weak kings. 

Continuing in this way, for any $3\leq k\leq n,$ the algorithm creates new arcs $u_{n-2}(1-0)u_{i}$ 
in $D$ for all $k-2\leq i\leq n-3.$ The resulting graph $D$ contains exactly $k$ weak kings.

If $k=2,$ then $D$ is constructed so that $x(0-0)y,$ $x(1-0)u_{i}.$ $y(1-0)u_{i}$ and  $u_{i}(0-0)u_{j}$ 
for all $1\leq i\leq n-2,$ $1\leq j\leq n-2$ and $i\neq j.$ Thus $D$ contains exactly two weak kings $x$ and $y.$ 

Finally, $D$ has exactly one weak king if it is constructed such that $x(0-0)y,$  $u_{1}(1-0)x,$ 
$u_{1}(1-0)y$ and $u_{1}(1-0)u_{i},$ $x(1-0)u_{i}$ and $y(1-0)u_{i}$ for all $2\leq i\leq n-2.$ 

Due to the nested \key{for} loops the algorithm runs in $O(n^{2})$ time. 

Figure \ref{figp2a} shows a 6 vertex oriented graph with exactly 6 weak kings, Figure \ref{figp2b} 
shows a 6 vertex oriented graph with exactly 5 weak kings namely $x,$ $y,$ $v_{1},$ $v_{2}$  and 
$v_{4},$ Figure \ref{figp2c} shows a 6 vertex oriented graph with exactly 4 weak kings namely  $x,$ 
$y.$ $v_{1}$ and $v_{4}.$  Figure \ref{figp2d} shows a 6 vertex oriented graph with exactly 3 weak kings 
namely  $x,$ $y$  and  $v_4$ and Figure \ref{figp2e} shows a 6 vertex oriented graph with exactly 
2 weak kings namely $x$ and $y.$ 

The directional dual of a weak king is a weak serf, and thus a vertex $u$ is a weak king of 
an oriented graph $D$ if and only if $u$ is a weak serf of $\bar{D},$ the converse of $D.$ 
So by duality, there exists an oriented graph on $n$ vertices with exactly $s$ weak serfs for all integers 
$n \geq s \geq 1.$ If $n = k \geq 1,$ then every vertex in any such oriented graph is both a weak king 
and a weak serf. Also if $n > k \geq 1,$ the oriented graph described in algorithm $k$\textsc{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 $(n, k, s, b)$ does there exist an oriented graph with $n$ vertices, 
exactly $k$ weak kings, $s$ weak serfs and that exactly $b$ of the weak kings are also serfs? 
By analogy with $(n, k, s, b)$-tournaments, such oriented graphs are called 
$(n, k, s, b)$-oriented graphs. Without loss of generality, we assume that $k \geq s.$ 
The following results by Pirzada\nevindex{Pirzada, Shariefuddin} and 
Shah\nevindex{Shah, N. A.} address this problem. 

\begin{tetel}\label{nkss} \emph{(Pirzada, Shah, 2008)}
If $n > k \geq s \geq 0,$ then there exists no $(n, k, s, s)$-oriented graph.
\end{tetel}

\begin{tetel}\label{nksb} \emph{(Pirzada, Shah, 2008)}
There exist $(n, k, s, b)$-oriented graphs, $n \geq k \geq s > b \geq 0$ and $n > 0,$ $n \geq k + s - b.$
\end{tetel}
\begin{biz} Let $D_1$ be the oriented graph with vertex set $\lbrace x_1, y_1, u_1, u_2, 
\cdots ,u_{k-b-2}\rbrace$ and $x_1(0-0)y_1,$ $u_{i}(1-0)x_{1},$ $u_{i}(0-1)y_{1}$ for all 
$1 \leq i \leq k-b-2,$ and $u_{i}(0-0)u_{j}$ for all $i\neq j.$

Take the oriented graph $D_2$ with vertex set $\lbrace x_2, y_2, v_1, v_2, \ldots, v_{b-2}\rbrace$ 
and arcs defined as in $D_1.$ Let $D_3$ be the oriented graph with vertex set $\lbrace z_1, z_2, 
\ldots,z_{s-b}\rbrace$ and $z_i(0-0)z_j$ for all $i, j.$ Let $D$ be the oriented graph 
$D_1 \cup D_2 \cup D_3$ (see Figure \ref{figp3}) with\\

$z_i(1-0)y_2$ \    for  $1 \leq i \leq s - b$

$z_i(0-0)x_2$ \   for  $1 \leq i \leq s - b$

$z_i(0-0)v_j$ \ for  $1 \leq i \leq s-b,$ $1 \leq j \leq b - 2$

$x_1(1-0)z_i,$ \ $y_1(1-0)z_i$ for  $1 \leq i \leq s - b$

$u_r(0-0)z_i$ \ for $1 \leq r \leq k-b-2,$ $1 \leq i \leq s - b$

$x_1(1-0)y_2,$ \  $y_1 (1-0)y_2$ 
              
$v_r(1-0)y_2$ \   for  $1 \leq r \leq k - b - 2$
     
$x_1(0-0)x_2,$ \ $y_1(0-0)x_2$

$v_r(0-0)v_j,$ \ for $1 \leq r \leq k - b - 2,$ $1 \leq j \leq b-2.$ 

\begin{figure}[!t]
\centering
\includegraphics[width=12cm,height=9cm]{p3}
\caption{Construction of an $(n, k, s, b)$-oriented graph.}
\label{figp3}
\end{figure}

Clearly $D$ contains exactly $k$ weak kings and the weak king set is $\lbrace x_1, y_1\rbrace\cup\lbrace 
u_1, u_2,\ldots, u_{k-b-2}\rbrace\cup\lbrace x_2, y_2\rbrace\cup\lbrace v_1, v_2,\ldots, 
v_{b-2}\rbrace.$ $D$ contains exactly $s$ weak serfs with the weak serf set 
as $\lbrace x_2, y_2\rbrace\cup\lbrace v_1, v_2, \ldots, v_{b-2}\rbrace\cup\lbrace z_1, z_2,\ldots, 
z_{s-b}\rbrace.$ Also from these $k$ weak kings, exactly $b$ are weak serfs. The weak king-serf set 
is $\lbrace x_2, y_2\rbrace\cup\lbrace v_1, v_2,\ldots, v_{b-2}\rbrace.$
\end{biz}

Exercise \ref{do} asks the reader to derive an algorithm for generating an $(n,k,s,b)$-oriented graph 
when the hypothesis of Theorem \ref{nksb} is satisfied.

\begin{gyak}
\ujgyak\label{exactlytwokings}
Give an algorithm that generates an oriented graph with $n$ vertices and exactly 2 kings. 
Prove the correctness of your algorithm.  
\ujgyak\label{counterex}
Draw the graph $D^*$ discussed in Example \ref{counterexample}. 
\ujgyak\label{weak}
Prove that \textsc{Weak-Kings2} is correct. Also determine its runtime.
\ujgyak\label{weak2}
Construct an oriented graph with six vertices and exactly one king. 
\ujgyak\label{do}
Derive an algorithm that takes a 4-tuple $(n,k,s,b)$ satisfying the hypothesis of Theorem \ref{nksb} 
as input and generates an $(n,k,s,b)$-oriented graph. Analyze the performance of your algorithm. 
\end{gyak}\index{weak kings in 2-tournaments|)}

\begin{fld}
\ujfld{Optimal reconstruction of score sets\label{Optimalscoreset}}
{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 \ref{regular} and try to find a smaller tournament  with score set $\{0,1,3,6,10\}$.

b) Write a back-track program which constructs the smallest tournament whose score set is $\{0,1,3,6,10\}$.  

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

d) Estimate the running time of your programmes. 

\textit{Hint.} Read Yoo's proof.}
\ujfld{Losing set\label{loosingset}}
{We define the \ki{losing score}\felindex{losing score} of a vertex 
as the in-degree of the vertex. The \textit{loosing score set}\felindex{losing 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 $L = \{r_{1},r_{2},\ldots,r_{n}\}$ of nonnegative integers with 
$r_{1} < r_{2} - r_{1} < r_{3} - r_{2} < \cdots < r_{n} - r_{n-1},$ write an algorithm to generate a tournament 
with loosing score set $L.$ 
\ujfld{Imbalance set\label{imbalanceset}}
{Let}
\ujfld{Unicity\label{imbalanceset}}
{Let}
\ujfld{generalized weak kings}\label{strongabkings}
{Extend the definition of strong kings to $(a,b)$-tournaments and give sufficient conditions of the existence of 
the defined new types of kings.}
\ujfld{generalized weak kings}\label{weakabkings}
{Extend the definition of weak kings to $(a,b)$-tournaments and give sufficient conditions of the existence of 
the defined new types of kings.} 
\end{fld}

\begin{fejmegj}{\label{secChapterNotes}}
Many classical ans several contemporary graph theory textbooks are available to Readers. Such books are e.g. 
the books of Dénes Kõnig\nevindex{Kõnig, Dénes (1884--1944)} \cite{Konig1936}, 
Claude Berge\nevindex{Berge, Claude (1926--2002)} \cite{Berge1976} and 
László Lovász\nevindex{Lovász, László} \cite{Lovasz1979}. 
However, there is a dearth of books 
focusing on recent advances in the theory of digraphs. The book due to 
Bang-Jensen\nevindex{Bang-Jensen, J{\o}rgen} and Gutin \nevindex{Gutin, Gregory} \cite{BangG2009} 
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,\nevindex{Harary, Frank} 
Norman\nevindex{Norman, R. Z.} and Cartwright\nevindex{Cartwright, D.} \cite{HararyNC1965}, 
and Chartrand,\nevindex{Chartrand, Gary} Lesniak\nevindex{Lesniak, Linda} and Zhang\nevindex{Zhang, Ping}  
\cite{ChartrandL2005,ChartrandLZ2010}, Gross and  Yellen \cite{GrossY2004} 
present introductory material on tournaments and score structures. 
Moon's\nevindex{Moon, John W.} book on tournaments \cite{Moon1968} 
is also a good resource but is now out of print. 

The books A. Schrijver\nevindex{Schrijver, Alexander} \cite{Schrijver2003} and 
A. Frank\nevindex{Frank, András} \cite{Frank2011} 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,\nevindex{Landau, H. G.} K. B. Reid\nevindex{Reid, K. Brooks} and 
J. W. Moon.\nevindex{Moon, John W.} For classical and recent results in this area we refer 
to the excellent surveys by Reid \cite{Reid1978,Reid1996,Reid2004}.\nevindex{Reid, K. Brooks} 
Landau's pioneering work on kings and score structure 
appeared in 1953 \cite{Landau1953}. Reid stated his famous score set conjecture in \cite{Reid1978}. 
Partial results were proved by M. Hager\nevindex{Hager, Michael} \cite{Hager1986}. 
Yao's proof of Reid's conjecture appeared in English in 1989 \cite{Yao1989}.\nevindex{Yao, Tianxing} The comment 
of Q. Li\nevindex{Li, Qiao} on Reid's conjecture and Yao's proof was published  in 2006 \cite{Li2006}.
The construction of a new special tournament 
with a prescribed score set is due to Pirzada and Naikoo \cite{PirzadaN2006}. The score structure 
for 1-tournaments was introduced by H. G. Landau \cite{Landau1953} and extended for $k$-tournaments 
by J. W. Moon in 1963. This result of Moon later was reproved by Avery for $k = 2$ \cite{Avery1991} 
and for arbitrary $k$ by Kemnitz and Dolff \cite{KemnitzD1997}. Score sets of oriented graphs were investigated 
by Pirzada and Naikoo in 2008 \cite{PirzadaN2008}.\nevindex{Naikoo, Tariq A.}\nevindex{Pirzada, Shariefuddin} 

Authors of a lot of papers investigated the score sets of different generalized tournament, among others Pirzada, 
Naikoo and Chisthi\nevindex{Chisthi, T. A.} in 2006 (bipartite graphs),\index{bipartite graph} 
Pirzada and Naikoo in 2006 \cite{PirzadaN2006AKCE} ($k$-partite graphs),\index{kpartite graph@$k$-partite graph} 
Pirzada and Naikoo in 2006 \cite{PirzadaN2006App} 
($k$-partite graphs).\index{kpartite tournaments@$k$-partite tournaments} Pirzada, 
Naikoo and Dar\nevindex{Dar, F. A.} analyzed signed degree sets\index{signed degree set} 
of signed bipartite graphs\index{signed bipartite graph} \cite{PirzadaND2008}. 

The basic results on kings are due to K. Brooks Reid\nevindex{Reid, K. Brooks} 
\cite{Reid1980,Reid1982,Reid1996,Reid2004} and Vojislav Petrovi\'c\nevindex{Petrovi\'c, Vojislav} 
\cite{BrcanovP2010,Petrovic1995,Petrovic1997,PetrovicT1991,PetrovicT1998}.

The problem of the unicity of score sequences was posed and studied by Antal Iványi\nevindex{Iványi, Antal Miklós} 
and Bui Minh Phong\nevindex{Phong, Bui Minh} \cite{IvanyiB2004}. Another unicity results connected with 
tournaments was published e.g. by P.\nevindex{Tetali, Prasad} Tetali, J. W. Moon\nevindex{Moon, John W.} 
and recently by Chen\nevindex{Chen, An-Hang} et al. \cite{Chen2007,ChenCCW2008,Moon1982,Tetali1998}.

The term king in tournaments was first used by Maurer\nevindex{Maurer, Stephen B.} \cite{Maurer1980}. Strong kings 
were introduced by Ho\nevindex{Ho, Ting-Yem} and Chang\nevindex{Chang, Jou-Ming} 
\cite{HoC2003} and studied later by Chen et al.\nevindex{Chen, An-Hang} \cite{Chen2007,ChenCCW2008}, 
while Pirzada and Shah\nevindex{Shah, N. A.} \cite{PirzadaS2008} introduced 
weak kings in oriented graphs. The problems connected with 3-kings\index{threeking@3-king} 
and 4-kings\index{fourking@4-king} were discussed by Tan in \cite{Tan2006} and 
the construction of tournaments with given number of strong kings by Chen et al. in \cite{ChenCCW2008}. 
 
The difference of the out-degree and of the in-degree of a given vertex is called 
\textit{the imbalance} of the given vertex. The imbalance set\index{imbalance set} 
of directed multigraphs were studied 
by Pirzada, Naikoo, Samee\nevindex{Samee, U.} and Iványi\nevindex{Iványi, Antal Miklós} 
in \cite{PirzadaNSI2010}, while the imbalance sets of multipartite oriented graphs by Pirzada, 
Al-Assaf\nevindex{Al-Assaf, Abdulaziz M.} and Kayibi \cite{PirzadaAK2011}.\nevindex{Kayibi, Koko K.} 

In connection with Problem \ref{Optimalscoreset} see \cite{Ivanyi2009,Ivanyi2010}\nevindex{Iványi, Antal Miklós}

Problem 2

Problem 3

Problem 4 

Problem 5

Problem 6

An interesting new direction is proposed by "L. B. Beasley,\nevindex{Beasley, LeRoy B.}  
D. E. Brown,\nevindex{Brown, David E.} and. K. B. Reid\nevindex{Reid, K. Brooks} 
in \cite{BeasleyBR2009}: the problem 
is the reconstruction of tournaments on the base of the partially given out-degree matrix.  
\end{fejmegj}

\bibliography{AlgofInf3-11February}
This bibliography is made by HBib\TeX. First key of the sorting is the name of 
the authors (first author, second author etc.), second key is the year of publication, 
third key is the title of the document.

Underlying shows that the electronic version of the bibliography on the home page of the book 
contains a link to the corresponding address.
\bibliographystyle{algofinf}


\begin{printindex}
This index uses the following conventions. Numbers are alphabetised as if spelled out; for example, 
``2-3-4-tree'' is indexed as if were ``two-three-four-tree''. 
When an entry refers to a place other than the main text, the page number is followed by a tag: 
\textit{exe} for exercise, \textit{exa} for example, \textit{fig} for figure, \textit{pr} 
for problem and \textit{fn} for footnote.

The numbers of pages containing a definition are printed in \textit{italic} font, e.g. \\

time complexity, \underline{\textit{583}}.  
\end{printindex}

\begin{printnevindex}
This index uses the following conventions. If we know the full name of a cited person, then 
we print it. If the cited person is not living, and we know the correct data, then we print also the 
year of her/his birth and death.
\end{printnevindex}
\end{document}
