%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   Sample paper (in LaTeX2e) for Annales Univ. Sci. Budapest., Sect. Comp.  %
%                                                                            %
%                       http://ac.inf.elte.hu                                %
%                        2011. 07. 03                                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                                                          %%
%%                             IMPORTANT:                                   %%
%%                  In case of any problems contact                         %%
%%                        ac@compalg.inf.elte.hu                            %%
%%                                                                          %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[11pt,leqno,twoside]{article}

\usepackage{annal-latex}
\usepackage{fancyhdr}
\usepackage{amssymb,amsbsy}
%\usepackage{graphics}
\usepackage[dvips]{graphicx}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Your numbering system for theorems etc. may be different from the one suggested below. %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newtheorem{theorem}{\indent Theorem}[section]
\newtheorem{proposition}[theorem]{\indent Proposition}
%\newtheorem{lemma}[theorem]{\indent Lemma}
\newtheorem{lemma}{\indent Lemma}[section]
\newtheorem{corollary}{\indent Corollary}[section]


%\theoremstyle{definition}
%\newtheorem{definition}[theorem]{\indent Definition}
\newtheorem{definition}{\indent Definition}[section]
\newtheorem{example}[theorem]{\indent Example}
\newtheorem{remark}{\indent Remark}[section]



%%% An unnumbered object: %%%
\newtheorem*{xrem}{\indent Remark}


\begin{document}
\setcounter{page}{1}
\newcommand\balline{\small S. Pirzada, A. Iv\'anyi, N. A. Shah}
\newcommand\jobbline{\small Imbalances of bipartite multitournaments}

\vspace{-4cm} \fofej{36}{12}{nn}{nnn}

\vspace{.4cm}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Imbalances of bipartite multitournaments}

\author{{\bf Shariefuddin Pirzada} (Srinagar, India)\\[1ex]
{\bf Antal Iv\'anyi} (Budapest, Hungary)\\[1ex]
{\bf Namir A. Shah} (Srinagar, India)}
%% More authors can be given by repeating the \author command)


%
\keywords{multitournament, bipartite tournament, imbalance sequence, imbalance set}
%
\mathclass{05C65}
%
\compclass{G.2.2}

\projsupport{The second author received support 
from The European Union and the European Social Fund  
under the grant agreement no. T\'AMOP 4.2.1/B-09/1/KMR-2010-0003.}
%

\abstract {A bipartite $(a,b,p,q)$-tournament is a bipartite tournament in which the parts of the tournament 
contain $p,$ resp. $q$ vertices and the vertices belonging to 
different parts of the tournament are connected with at least $a$ and at most $b$ arcs. 
The imbalance of a vertex is defined as the difference of its out-degree and in-degree. 
In this paper existence criteria and construction algorithms are presented for    
bipartite $(a,b,p,q)$-tournaments having prescribed imbalance sequences and prescribed imbalance sets.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction\label{sec-section1}}
An actual research topic of graph theory is the characterization of different special graphs (as simple, oriented, 
bipartite, multipartite, signed and semicomplete graphs, see e.g. 
\cite{Avery1991,IvanyiLMS2011,IvanyiP2011,Moon1962,Moon1963,Mubayi2001,Pirzada2012,ReidZ1998}), and 
different generalizations (as hypergraphs, hypertournaments, 
weighted graphs, see e.g. \cite{Pirzada2009,PirzadaZ2010,PirzadaZI2010}) 
having prescribed degree properties.

The classical results, as the theorem published by Landau in 1953 \cite{Landau1953}, 
and the theorem of Erd\H os and Gallai published in 1960 
\cite{Erdos1960} contained necessary and sufficient conditions of the existence 
of a tournament, respectively of a simple graph with prescribed parameters. 
Later also constructive results appeared as the Havel-Hakimi theorem \cite{Hakimi1962,Havel1955} on  
simple graphs and the construction algorithm for optimal $(a,b,n)$-tournaments \cite{Ivanyi2010}. 

The structure of the paper is as follows. Section \ref{sec-section2} contains some preliminary results, while 
Section \ref{sec-section3} deals with imbalances of $(0,\infty,p,q)$-tournaments. In Section \ref{sec-section4} 
the reconstruction results of imbalance sequences are discussed, Section \ref{sec-section5} is devoted to 
imbalance sets.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminary notions and earlier results\label{sec-section2}}
Let $a, \ b$ and $n$ be nonnegative integers $(b \geq a, \ b > 0, \ n \geq 1)$, 
$\mathcal{T}(a,b.n)$ be the set of directed multigraphs $T = (V,E)$, where $|V| = n$, 
and elements of each pair of different vertices $u, \ v \in V$ are connected 
with at least $a$ and at most $b$ arcs \cite{Ivanyi2009}. 
$T \in \mathcal{T}(a,b,n)$ is called $(a,b,n)$\textit{-tournament.} 
$(1,1,n)$-tournaments are the usual tournaments, and $(0,1,n)$-tournaments are also called 
oriented graphs or simple directed graphs \cite{Gross2004}. The set $\mathcal{T}$ is defined by
$$
\mathcal{T} = \bigcup _{b\geq 1, \ n \geq 1} \mathcal{T}(0,b,n).
$$

According to this definition $\mathcal{T}$ is the set of the finite directed loopless multigraphs.

For any vertex $v \in V$ let $d(v)^+$ and
$d(v)^-$ denote the out-degree and in-degree of $x,$ respectively. 
Define $f(v) = d(v)^+ - d(v)^-$ as the imbalance of the vertex $v.$ 
The imbalance sequence of $T \in \mathcal{T}$ is formed by listing the vertex 
imbalances of the vertices in nonincreasing or nondecreasing order. 

The following result due to Avery \cite{Avery1991} and Mubayi, Will and West \cite{Mubayi2001} 
provides a necessary and sufficient condition for a nonincreasing sequence $F$ of integers to be 
the imbalance sequence of a tournament $T \in \mathcal{T}(0,1,n)$.

\begin{theorem}\label{theorem1} A nonincreasing sequence of integers $F=[f_{1},\ldots,f_{n}]$  
is an imbalance sequence of a tournament $T \in \mathcal{T}(0,1,n)$ if and only if 
\begin{equation*}
\sum^{k}_{i=1}f_i\leq k(n-k), 
\end{equation*}
for $1\leq k<n$ with equality when $k=n$.
\end{theorem}

\begin{proof} See \cite{Avery1991,Mubayi2001}. \hfill $\square$ 
\end{proof}

Arranging the sequence $F$ in nondecreasing order, we have the following equivalent assertion.

\begin{corollary}\label{corollary2} A nondecreasing sequence of integers $F=[f_{1},\ldots,f_{n}]$  
 is the imbalance sequence of a $(0,1,n)$-tournament if and only if  
$$
 \sum^{k}_{i=1}f_i\geq k(k-n) 
$$
for $1\leq k<n$, with equality when $k=n$.
 \end{corollary}

The following theorem gives a characterization of imbalance sequences of $(0,b,n)$-tournaments \cite{PirzadaNSI2010}.

\begin{theorem}\label{theorem3} If $b \geq 1,$ then a nonincreasing sequence $F=[f_{1},\ldots,f_{n}]$ of integers  
is the imbalance sequence of an $(0,b,n)$-tournament if and only if
$$
\sum _{i=1}^{k}f_{i}\geq bk(n-k),
$$
for $1\leq k\leq n$ with equality when $k=n$. \hfill $\square$
\end{theorem}
 
\begin{proof} See \cite{PirzadaNSI2010}. \hfill $\square$
\end{proof} 

In \cite{PirzadaNSI2010} also a construction algorithm of a $(0,b,n)$-tournament can be found.
Some other results on imbalances of $(0,b,n)$-tournaments and their special cases can be found in 
 \cite{Pirzada2008,PirzadaNS2011,ReidZ1998,Samee2010}. 
 
Reid in 1978 \cite{Reid1978} introduced the concept of the score set of $(1,1,n)$-tournaments 
as the set of different scores (out-degrees) of the given tournament. At the same time he formulated the conjecture 
that for any set of nonnegative integers $S$ 
there exists a tournament $T$ having $S$ as its score set. In the same paper he proved the conjecture for 
sets containing 1, 2, or 3 elements. Hager in 1986 \cite{Hager1986} proved the conjecture 
for $|S| = 4$ and $|S| = 5$ and Yao in 1989 \cite{Yao1989} published a proof of the whole conjecture.

There are some known results on the imbalance sets of $(0,1,n)$-tournaments 
(see e.g. \cite{PirzadaAK2011,PirzadaN2008,PirzadaNSI2010}). 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Imbalances in $(0,\infty,p,q)$-tournaments\label{sec-section3}}
Let $a, \ b, \ p$ and $q$ be nonnegative integers $(b \geq a, \ b > 0, \ p \geq 1, \ q \geq 1)$, 
$\mathcal{B}(a,b,p,q)$ be the set of directed bipartite multigraphs  $B = (U\cup V,E),$   
where $|U| = p$ and  $|V| = q$, and the elements of each pair of vertices $u \in U$ and $v \in V$ 
are connected with at least $a$ and at most $b$ arcs. Then $B \in \mathcal{B}(a,b,p,q)$ 
is called $(a,b,p,q)$\textit{-tournament.} $B \in \mathcal{B}(0,1,p,q)$ is an oriented bipartite graph and 
a $(1,1,p,q)$-tournament is a bipartite tournament. 

According to this definition $\mathcal{B}$ is the set of the finite directed bipartite multigraphs.

For any vertex $v \in U \cup V$ of $T \in \mathcal{B}(a,b,p,q)$ let $d_{v}^{+}$ and
$d_{v}^{-}$ denote the out-degree and in-degree of $v$, respectively. 
Define $f_(v) = d(v)^+ - d(v)^-$ and $g(v) = d(v)^+ - d(v)^-$ as the imbalances of the vertex $v$ 
for $v \in U,$ resp. $v \in V.$  
Then the nonincreasing or nondecreasing sequences $F=[f_{1},\ldots,f_{p}]$ and $G=[g_{1},\ldots,g_{q}]$ 
are the imbalance sequences of the $(a,b,p,q)$-tournament $T = (U\cup V,E)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Basic properties of imbalance sequences\label{subsec-subsection31}}
If in an $(a,b,p,q)$-tournament $B(U\cup V,E)$ there are $x$ arcs
directed from vertex $u \in U$ to $v \in V$ and $y$ arcs directed
from $v$ to $u,$ with $a \leq x \leq b$, $a \leq y \leq b$ and $a \leq
x + y \leq b,$ then it is denoted by $u(x-y)v.$ We also call $u(i -y)v$ as a \textit{double.} 
A \textit{tetra} in an $(a,b,p,q)$-tournament is an induced $(0,1,2,2)$-tournament. Define tetras of the form
$u_{1}(1-0)v_{1}(1-0)u_{2}(1-0)v_{2}(1-0)u_{1}$ and
$u_{1}(1-0)v_{1}(1-0)u_{2}(1-0)v_{2}(0-0)u_{1}$ to be of
$\alpha$\textit{-type,} and all other tetras to be of $\beta$\textit{-type.} An $(a,b,p,q)$-tournament 
is said to be of $\alpha$\textit{-type} or $\beta$\textit{-type} according
as all of its tetras are of $\alpha$-type or $\beta$-type
respectively. We note that an $\alpha$-type tetra
$u_{1}(1-0)v_{1}(1-0)u_{2}(1-0)v_{2}(1-0)u_{1}$ or
$u_{1}(1-0)v_{1}(1-0)u_{2}(1-0)v_{2}(0-0)u_{1}$ can be respectively
transformed to the $\beta$-type tetra $u_{1}(0-0)v_{1}(0-0)u_{2}(0-0)v_{2}(0-0)u_{1}$ or
$u_{1}(0-0)v_{1}(0-0)u_{2}(0-0)v_{2}(0-1)u_{1}$ and vice-versa with imbalances of the
vertices $u_{1},u_{2}\in U$ and $v_{1}, v_{2}\in V$ remaining
unchanged (see Figure \ref{figure1}). We note that a double of the form $u(x-x)v$ can be transformed to the double 
of the form $u(0-0)v$ making number of arcs lesser by $2x$ while imbalances remaining unchanged.


\begin{figure}[!ht]
\begin{center}
\resizebox{80mm}{!}{
\includegraphics{figure1.eps}}
\caption{Transformation of an $\alpha$-type tetra to a $\beta$-type tetra. \label{figure1}}
\end{center}
\end{figure}


The above facts lead us to the following assertion.
\begin{lemma}\label{lemma-lemma4} Among all $(a,b,p,q)$-tournaments with given imbalance sequences, 
those with the fewest arcs are of $\beta$-type.
\end{lemma}
\begin{proof} Let $B = B(U \cup V,E)$ be an $(a,b,p,q)$-tournament with imbalance sequences $F$ and $G$. 
If $B$ is not of $\beta$-type, it contains an oriented tetra of $\alpha$-type. Thus for $u_{1}, u_{2}\in U$ 
and $v_{1}, v_{2}\in V$, we have $u_{1}(1-0)v_{1}(1-0)u_{2}(1-0)v_{2}(1-0)u_{1}$, or 
$u_{1}(1-0)v_{1}(1-0)u_{2}(1-0)v_{2}(0-0)u_{1}$ as an oriented tetra of $\alpha$-type in $B$. 
Clearly $u_{1}(1-0)v_{1}(1-0)u_{2}(1-0)v_{2}(1-0)u_{1}$ can be changed 
to $u_{1}(0-0)v_{1}(0-0)u_{2}(0-0)v_{2}(0-0)u_{1}$ 
with the same imbalance sequences and four arcs fewer, and $u_{1}(1-0)v_{1}(1-0)u_{2}(1-0)v_{2}(0-0)u_{1}$ 
can be changed to $u_{1}(0-0)v_{1}(0-0)u_{2}(0-0)v_{2}(0-1)u_{1}$ with same imbalance sequences and 
two arcs fewer. Hence in both cases we obtain a realization $B^{\prime}(U\cup V,E)$ of $F$ and $G$ with fewer arcs. 
In case there is a double of the form $u(x-x)v$, it can be transformed to the double of the form $u(0-0)v$ 
making number of arcs lesser by $2x$. \hfill $\square$
\end{proof}

A \textit{transmitter} is a vertex whose in-degree is zero. We have the
following assertion about the transmitter in a $\beta$-type $(0,b,p,q)$-tournament.
\begin{lemma}\label{lemma5} In a $\beta$-type $(0,b,p,q)$-tournament with nondecreasing imbalance sequences 
$F=[f_{1},\ldots,f_{p}]$ and $G=[g_{1},\ldots,g_{q}]$, either a vertex with imbalance $f_{p},$  
or a vertex with imbalance $g_{q}$, or both may act as transmitters.
\end{lemma}
\begin{proof} Let $U=\{u_{1},u_{2},\ldots,u_{p}\}$ and
$V=\{v_{1},v_{2},\ldots,v_{q}\}$ be the parts of a $(0,b,p,q)$-tournament
 $B(U\cup V,E)$, so that $g(u_p)=f_p$ and $g(v_q)=g_q$. Assume
that neither $u_{p}$ nor $v_{q}$ is a transmitter. Then there exist 
some vertices $u_{i}\in U$ and $v_{j}\in V$ such that $u_{i}(1-0)v_{q}$
and $v_{j}(1-0)u_{p}$. Since $g(u_p)\geq g(u_i)$ and $g(v_q)\geq
bg(v_j)$, there exist vertices $u_r\in U$ and $v_s\in V$ such that
$u_p(1-0)v_s$ and $v_q(1-0)u_r$ (see Figure \ref{figure2}(a)). We have the
following possibilities.

\begin{figure}[!ht]
\begin{center}
\resizebox{120mm}{!}{
\includegraphics{figure2.eps}}
\caption{Illustration of the different cases in the proof of Lemma \ref{lemma5}. \label{figure2}}
\end{center}
\end{figure}

\textbf{ Case (i).} $v_{s}(1-0)u_{r}$ and $u_{r}(0-0)v_{j}$. Here
$v_{j}(1-0)u_{p}(1-0)v_{s}(1-0)u_{r}(0-0)v_{j}$ is a tetra of
$\alpha$-type, a contradiction (see Figure \ref{figure2}(b)).

\textbf{Case (ii).} $v_{s}(1-0)u_{r}$ and $u_{r}(1-0)v_{j}$. Here
$v_{j}(1-0)u_{p}(1-0)v_{s}(1-0)u_{r}(1-0)v_{j}$ is a tetra of
$\alpha$-type, a contradiction (see Figure \ref{figure2}(c)).

\textbf{Case (iii).} $u_{r}(1-0)v_{s}$ and $v_{s}(0-0)u_{i}$. In
this case $u_{i}(1-0)v_{q}(1-0)u_{r}(1-0)v_{s}(0-0)u_{i}$ is a tetra
of $\alpha$-type, again a contradiction (Figure 2(d)).

\textbf{Case (iv).} $u_{r}(1-0)v_{s}$ and $v_{s}(1-0)u_{i}$. Clearly $u_{i}(1-0)v_{q}(1-0)u_{r}(1-0)v_{s}(1-0)u_{i}$ 
is a tetra of $\alpha$-type, again a contradiction (Figure 2(e)).

\textbf{Case (v).} If $u_{r}(1-0)v_{s}$ and $u_{i}(1-0)v_{s}$,
then $b(u_{i})>b(u_{p})$, which is a contradiction. Similarly if
$v_{s}(1-0)u_{r}$ and $v_{j}(1-0)u_{r}$, then $b(v_{j})>b(v_{q})$,
again a contradiction.

\textbf{Case (vi).} Finally if $u_{r}(0-0)v_{s}$, $u_{r}(0-0)v_{j}$
and $u_{i}(0-0)v_{s}$, then there is a tetra
$v_{j}(1-0)u_{p}(1-0)v_{s}(0-0)u_{r}(0-0)v_{j}$ and this can be
transformed to the tetra $v_{j}(0-0)u_{p}(0-0)v_{s}(0-1)u_{r}(0-1)v_{j}$ and the imbalances
remain unchanged (see Figure \ref{figure2}(f)). This means there is an $\alpha$-type
tetra $u_{i}(1-0)v_{q}(1-0)u_{r}(1-0)v_{s}(0-)u_{i}$, a contradiction.  \hfill $\square$
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Reconstruction of imbalance sequences \label{sec-section4}}
This section starts with a necessary and sufficient condition for two sequences $F$ and $G$ to be 
imbalance sequences of some $(0,b,p,q)$-tournament. Then we deal with minimal reconstruction of imbalance 
sequences.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Existence of a realization of an imbalance sequence \label{subsec-subsection41}}
The following result is a combinatorial criterion for determining whether 
some prescribed sequences are realizable as 
imbalance sequences of a $(0,b,p,q)$-tournament. 
This is analogous to a result on degree sequences of simple graphs by Erd\H os and Gallai \cite{Erdos1960} 
and a result on bipartite tournaments due to Beineke and Moon \cite{Beineke1981}. 
 
\begin{theorem}\label{theorem6} Let $b, \ p$ and $q$ be positive integers. Two nonincreasing sequences 
$F = [f_1,\ldots,f_p]$ and $G=[g_{1},\ldots,g_{q}]$ of integers are the imbalance sequences of some 
$(0,b,p,q)$-tournament if and only if
\begin{equation}
\sum_{i=1}^{k}f_{i}+\sum_{j=1}^{l}g_{j}\leq bk(q - l) + bl(p - k) \label{eq-ifonlyif}
\end{equation}
for $1\leq k\leq p$, $1\leq l\leq q$, with equality when $k=p$ and $l=q$.
\end{theorem}
\begin{proof} The necessity follows from the fact that a directed bipartite subgraph of a 
$(0,b,p,q)$-tournament induced by $k$ vertices 
from the first part and $l$ vertices from the second part has a sum of imbalances at most $bk(q - l) + bl(p - k)$.

For sufficiency, assume that $F=[f_1,\ldots,f_p]$ and $G=[g_1,\ldots,g_q]$ are the sequences 
of integers in nonincreasing order satisfying conditions \ref{eq-ifonlyif} but are not the imbalance sequences of any  
$(0,b,p,q)$-tournament. Let these sequences be chosen in such a way that 
$p$ is the smallest possible and $q$ is the smallest possible among the tournaments with the smallest $p$, 
and $f_1$ is the least with that choice of $p$ and $q$. We consider the following two cases.

\textbf{Case (i).} Suppose equality in \ref{eq-ifonlyif} holds for some $k\leq p$ and $l < q,$ so that
\begin{equation*}
\sum_{i=1}^{k}f_{i}+\sum_{j=1}^{l}g_{j} = bk(q - l) + bl(p - k).
\end{equation*}

By the minimality of $p$ and $q$, $F=[f_1, \ldots, f_k]$ and $G=[g_1, \ldots, g_l]$ 
are the imbalance sequences of some $(0,b,p,q)$-tournament $B_1(U_1\cup V_1,E_1)$. 
Let $F_{2}=[f_{k+1},\ldots,f_p]$ and $G_{2}=[g_{l+1},\ldots,g_q]$.

Now,
\begin{equation*}
\begin{split}
\sum _{i=1}^{f}a_{k+i}+\sum _{j=1}^{g}b_{l+j}&=\sum _{i=1}^{k+f}a_{i}+\sum _{j=1}^{l+g}b_{j}- 
\left( \sum _{i=1}^{k}a_{i}+ \sum _{j=1}^{l}b_{j} \right) \\
& \geq r[2(k+f)(l+g)-(k+f)q-(l+g)p]-r(2kl+kq+lp)\\&=r(2kl+2kg+2fl+2fg-kq-fq-lp-gp-2kl+kq+lp)\\
&=r(2fg-fq-gp+2kg+2fl)\\&\geq r(2fg-fq-gp),
\end{split}
\end{equation*}
for $1\leq f\leq p-k$ and $1\leq g\leq q-l$, with equality when $f=p-k$ and $g=q-l$. 
So, by the minimality for $p$ and $q$, the sequences $F_2$ and $G_2$ form the imbalance sequences of 
the $(0,b,p-k,q-l)$-tournament $B_{2}(U_{2}\cup V_{2},E_2)$. Now construct a 
$(0,b,p,q)$-tournament $B(U\cup V,E)$ as follows.

Let $U=U_1\cup U_2$, $V=V_1\cup V_2$ with $U_1\cap U_2=\emptyset $, $V_1\cap V_2=\emptyset                                                                                            $ and 
the arc set containing those arcs which are between $U_1$ and $V_1$ and between $U_2$ and $V_2$. 
Then we obtain a $(0,b,p,q)$-tournament $B(U\cup V,E)$ with the imbalance sequences $F$ and $G,$ 
which is a contradiction.

\textbf{Case (ii).} Suppose that the strict inequality holds in \ref{eq-ifonlyif} 
for all $k\not= p$ and $l\not= q.$ That is,
\begin{equation*}
\sum_{i=1}^{k}f_{i}+\sum_{j=1}^{l}g_{j}> bk(q - l) + bl(p - k)
\end{equation*}
for $1\leq k< p$, $1\leq l< q$.

Let $F_1=[f_{1}-1,f_{2},\ldots,f_{p-1},f_{p}+1]$ and $G_1=[g_{1},\ldots,g_{q}]$, so that $F_1$ and $G_1$ 
satisfy the conditions \ref{eq-ifonlyif}. Thus, by the minimality of $f_1,$ the sequences $F_1$ and $G_1$ 
are the imbalances sequences of some $(0,b,p,q)$-tournament $B_{1}(U_1\cup V_1)$. 
Let $f_{u_{1}}=f_{1}-1$ and  $f_{u_{p}}=f_{p}+1$. Since $f_{u_{p}}>f_{u_{1}}+1$, 
therefore there exists a vertex $v_1\in V_1$ such that $u_{p}(0-0)v_{1}(1-0)u_1$, or $u_{p}(1-0)v_{1}(0-0)u_1$, 
or $u_{p}(1-0)v_{1}(1-0)u_1$, or $u_{p}(0-0)v_{1}(0-0)u_1$, in $D_{1}(U_1\cup V_1,E_1)$ and if these are changed 
to $u_{p}(0-1)v_{1}(0-0)u_1$, or $u_{p}(0-0)v_{1}(0-1)u_1$, or $u_{p}(0-0)v_{1}(0-0)u_1$, or $u_{p}(0-1)v_{1}(0-1)u_1$ 
respectively, the result is a $(0,b,p,q)$-tournament with imbalances sequences $F$ and $G$, 
which is a contradiction proving the result. \hfill $\square$ 
\end{proof}

Since $(0,1,p,q)$-tournaments (oriented graphs) are special $(a,b,p,q)$-tournaments, the following corollary 
of Theorem \ref{theorem6} gives a necessary and sufficient condition for nonincreasing sequences of integers 
to be imbalance sequences of some $(0,1,p,q)$-tournament.

\begin{corollary}\label{corollary7} Two nonincreasing sequences $F=[f_1,\ldots,f_p]$ 
and \linebreak 
\noindent $G=[g_1,\ldots,g_q]$ of integers are the imbalance sequences of some  
$(0,1,p,q)$-tournament if and only if 
\begin{equation}
\sum_{i=1}^{k}f_{i}+\sum_{j=1}^{l}g_{j}\leq k(q - l) + l(p - k),\label{equation2}
\end{equation}
for $1\leq k\leq p,$ $1\leq l\leq q$ with equality when $k=p$ and $l=q$.
\end{corollary}

\begin{proof} Let us substitute $b = 1$ into \eqref{eq-ifonlyif}. \hfill $\square$
\end{proof}

Another simple consequence of Theorem \ref{theorem6} is the following assertion: if  
$F=[f_{1},\ldots,f_{p}]$ and $G = [g_{1},\ldots,g_{q}]$ are imbalance sequences of a $(0,b,p,q)$-tournament, 
then 
\begin{equation}
\sum _{i=1}^{p} f_i + \sum _{j=1}^q g_j = 0. \label{eq-zerosum}
\end{equation}

From the other side, for arbitrary sequences of integer numbers $F$ and $G$ satisfying \eqref{eq-zerosum} 
one can find such a $b$, that $F$ and $G$ are imbalance sequences of some $(0,b,p,q)$-tournament. 

Let $F_{\emph{max}},$ $G_{\emph{max}},$ and $z$ be defined as follows:
$$
F_{max} = \max _{1 \leq i \leq p} |f_i|, 
$$
$$
G_{\emph{max}} = \max _{1 \leq j \leq p} |g_j|,
$$
and
$$
z = \max (F_{\emph{max}},G_{\emph{max}}).
$$

The following assertion gives lower and upper bound for $b_{\emph{min}}.$

\begin{lemma} If\label{lemma-bbounds} $p \geq 1$ and $q \geq 1,$ then
\begin{equation}
\max \left ( \left \lceil \frac{F_{\emph{max}}}{q} \right \rceil, \left \lceil \frac{G_{\emph{max}}}{p} 
 \right \rceil \right ) \leq b_{\emph{min}} \leq \max(F_{\emph{max}},G_{\emph{max}}).
\end{equation}
\end{lemma}
\begin{proof} From one side it is easy to write a program which constructs a $(0,z,p,q)$-tournament, and even the 
uniform allocation of the degrees requires  
\begin{equation}
b_{\emph{min}} \geq \max \left ( \left \lceil \frac{F_{\emph{max}}}{q} \right \rceil,
\left \lceil \frac{G_{\emph{max}}}{p} \right \rceil \right ).
\end{equation} \hfill $\square$
\end{proof}

We are interested in the least possible $b$ allowing the realization of $F$ and $G.$  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Computation of $b_{min}$ \label{subsec-subsection42}}

We are interested in the computation of the minimal value of $b,$ satisfying \eqref{eq-ifonlyif}
Using Theorem \ref{theorem6} we can compute $b_{min}.$  

Let 
$$
\alpha(k,l) = \sum _{i=1}^k f_i + \sum _{j=1}^l g_j 
$$
and 
$$
\beta(k,l) = bk(q - l) + bl(p - k) 
$$
for $1 \leq i \leq p$ and $1 \leq j \leq q.$ 

The following theorem allows quickly to compute $b_{min}.$

\begin{theorem}\label{theorem8} Two nonincreasing sequences $F=[f_{1},\ldots,f_{p}]$ 
and $G=[g_{1},\ldots,g_{q}]$ of integers are the imbalance sequences of some  $(0,b,p,q)$-tournament $B$ 
if and only if $b \geq b_{min}$, where
\begin{equation}
b_{min} = \min _{1\leq k \leq p, 1 \leq l \leq q} \{b \ | \ \alpha(k,l) \leq \beta(k,l) \}. \label{eq-bmin}
\end{equation}
\end{theorem}

\begin{proof} If $k = p$ and $l = q,$ then both sides of \eqref{eq-ifonlyif} equal to zero, otherwise 
the right side is positive and a multiple of $b,$ therefore \eqref{eq-bmin} holds, if $b$ is sufficiently large. 
\end{proof}



The following program \textsc{Minimal} is based on Theorem \ref{theorem8}. The pseudocode uses the conventions 
described in \cite{CormenLRS2009}.

\textit{Inputs}. $p$ and $q$: the numbers of the elements in the prescribed imbalance sequences; \\
$b$: maximum number of permitted arcs between two vertices $u \in U$ and $v \in V$; \\
$F = [f_1, \ldots, f_p]$ and $G = [g_1, \ldots, g_q]$: given nonincreasing sequences of integers.

\textit{Output}. $b_{min}$: the minimal number of allowed arcs between two vertices belonging to different 
parts of $B$.

\textit{Working variables.} $i, \ j$: cycle variables; \\
$S$: actual sum of the imbalances; \\
$L = \alpha(k,l)$: the actual value of the left side of (\ref{equation2}); \\
$R = \alpha(k,l)$: the actual value of the right side of (\ref{equation2}).

\bigskip
\noindent \textsc{Minimal}$(b,p,q,F,G,b_{\emph{min}})$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $S \leftarrow 0$ \\
\hspace{-7mm}02 $F_{\mbox{max}} \leftarrow \max(|f_1|, |f_p|)$ \\
\hspace{-7mm}03 $G_{\mbox{max}} \leftarrow \max(|g_1|,|g_q|)$ \\
\hspace{-7mm}04 $b_{min} \leftarrow \max(\lceil \frac{F_{\mbox{max}}}{q} \rceil, \lceil \frac{G_{\mbox{max}}}{p} \rceil )$ \\
\hspace{-7mm}05 \textbf{for} \= $i \leftarrow 1$ \textbf{to} $p$ \\
\hspace{-7mm}06              \> $S \leftarrow S + f_i$ \\  
\hspace{-7mm}07              \> $L \leftarrow S$ \\            
\hspace{-7mm}08              \> \textbf{for} \= $j \leftarrow 1$ \textbf{to} $q$ \\
\hspace{-7mm}09              \>              \> $L \leftarrow S + g_j$ \\
\hspace{-7mm}10              \>              \> $R \leftarrow b_{\emph{min}}[i(q - j) + j(p - i)]$ \\
\hspace{-7mm}11              \>              \> \textbf{if} \= $L > R$  \\
\hspace{-7mm}12              \>              \>             \> $b_{\emph{min}} \leftarrow b_{\emph{min}} + 1$ \\
\hspace{-7mm}13              \>              \> \textbf{if} \> $b_{\emph{min}} == \max(F_{\mbox{max}},G_{\mbox{max}})$ \\
\hspace{-7mm}14              \>              \>             \> \textbf{return} $b_{\emph{min}}$ \\            
\hspace{-7mm}13 \textbf{return} $b_{min}$
\end{tabbing}

\textsc{Minimal} computes $b_{min}$ in all cases in $\Theta(pq)$ time. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Reconstruction of imbalance sequences \label{subsec-subsection43}}
The next result provides a useful recursive test whether given sequences of integers in nondecreasing order 
are the imbalance sequences of some $(0,b,p,q)$-tournament.

\begin{theorem} Let\label{th-imbreal} $F = [f_1,\ldots,f_p]$ and $G = [g_1,\ldots,g_q]$ 
be nondecreasing sequences of integers satisfying \eqref{eq-ifonlyif}, further either $f_p > 0$ 
$f_p \leq bq,$ $g_q \leq bp$ or $g_p > 0,$ $g_q \leq bp,$ $f_p \leq bq$ Let $F'$ be obtained from $F$ by deleting 
$f_p,$ and $G'$ be obtained as follows. Choose $h,$ $1 \leq h \leq b$, such that $(h - 1)q < f_p \leq hq$ and 
increase $f_p - (h - 1)q$ smallest elements of $G$ by $h$ each, and $q - (f_p - (h - 1)q) = hq - f_p$ 
remaining elements by $(h - 1)$ each. Then $F$ and $G$ are imbalance sequences of some $(0,b,p,q)$-tournament 
if and only if $F'$ and $G'$ are imbalance sequences of some $(0,b,p,q)$-tournament. 
\end{theorem}

\begin{proof} Due to the symmetry it is sufficient to prove the theorem for the case when $f_p > 0.$

Let  $F'$ and $G'$ be the imbalance sequences of some $(0,b,p,q)$-tournament $D'$ with parts
$U'$ and $V'.$ Then a $(0,b,p,q)$-tournament $D$ with imbalance sequences $F$ and $G$ can be obtained by adding a
transmitter $u_p$ to $U'$ such that $u_{p}(h-0)v_{i}$ for those vertices $v_i$ in $V'$ whose imbalances were 
increased by $h$ and $u_{p}((h - 1)-0)v_{j}$ for those vertices $v_j$ in $V'$ 
whose imbalances were increased by $h - 1$ in going from $F$ and $G$ to $F'$ and $G'.$ 

Conversely, suppose $F$ and $G$ are the imbalance sequences of a $(0,b,p,q)$-tournament $D$ with parts 
$U$ and $V.$ By Lemma \ref{lemma-lemma4}, assume $D$ to be of $\beta$-type. Then there is a vertex $u_p$ in $U$ 
with imbalance $f_{p}$ (or a vertex $v_q$ in $V$ with imbalance $g_q,$ or both $u_p$ and $v_q$) 
which is a transmitter. Let the vertex $u_p$ in $U$ with imbalance $f_p$ be a transmitter. Clearly, 
$f_{p} > 0$ so $d_{u_p}^+ > 0$ and $d_{u_p}^- = 0.$  

Let $V_1$ be the set of $f_p - (h-1)q$ vertices of smallest imbalances in $V,$ and let $V_{2} = V - V_1.$. 
Construct $D$ such that $u_{p}(h - 0)v_i$ for all $v_{i}\in V_1$ and $u_{p}((h - 1)-0)v_j$ for all
vertices $v_{j}\in V_2.$ This construction is possible since if there there are less than $h$ arcs say $h - t$ 
arcs from $u_{p}$ to any vertex in $V_{1},$ then these $t$ arcs from $u_{p}$ will be directed towards
vertices in $V_{2}$, and by transformations will be made directed to
$v_{i}$ in $V_{1}.$ Clearly $D - \{u_p\}$ realizes $F'$ and $G'.$ \hfill $\square$
\end{proof}


As a consequence of Theorem \ref{th-imbreal}, we have the following recursive and constructive criteria 
for $(0,1,p,q)$-tournaments.

\begin{corollary} Let\label{cor01} $F = [f_1, \cdots, f_p]$ and $G = [g_1, \cdots, g_q]$ be nondecreasing sequences 
of integers $f_p > 0,$ $f_p \leq q$ and $g_q \leq p$. Let $F'$ be obtained from $F$ by deleting one element 
$f_p,$ and $G'$ be obtained from $G$ by increasing $g_p$ smallest elements of $G$ by 1 each. Then $F$ and $G$ 
are the imbalance sequences of some $(0,1,p,q)$-tournament if and only if $F'$ and $G'$ are 
imbalance sequences.
\end{corollary}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
\subsection{Examples  \label{subsec-subsection44}}

\textbf{Example 1.} The first example illustrates the application of Theorem \ref{th-imbreal}. Let $p = 4,$ 
$F_1 = [-2,-2,3,4],$ $q = 3,$ and $G_1 = [-5,-1,3].$ Then according to Lemma \label{lemma-bbounds} we have
$$
2 \leq b_{\emph{min}} \leq 5. 
$$

Theorem \ref{theorem8} results $b_{\emph{min}} = 2.$ 

The steps of the reconstruction using Theorem \ref{th-imbreal} are as follows. In $f_p > 0$ and $h = 2,$ 
implying $F_2 = [-2,-2,3]$ and $G_2 = [-3,0,4],$ and the constructed arcs are $u_4(2--0)v_1,$ $u_4(1--0)v_2,$ 
and $u_4(1--0)v_3.$ Now $f_3 > 0$ and $g_3 > 0,$ therefore we can choose. Let us choose $g_3,$ then $h = 2,$ 
implying $G_3 = [-3,0]$ and after sorting $F_3 = [-1,0,4]$ and the constructed arcs are $v_3(2--0)u_1,$ 
$v_3(1--0)u_2$ and $v_3(1--0)u_3.$ Now $f_3 > 0$ and $h = 2,$ implying $F_4 = [-1,0]$ and after sorting 
$G_4 = [-1,2]$ and the constructed arcs 
are $u_3(2--0)v_1$ and $u_3(2--0)v_2.$  Now $g_2 > 0$ and $h = 1$ implying $G_5 = [-1]$ and $F_5 = [0,1]$ 
and the constructed arcs are $v_2(1--0)u_1$ and $v_2(1--0)u_2.$ Now $f_1 > 0,$ so $h = 1,$ implying $F_6 = [0]$ 
and $G_6 = [0].$ The constructed arcs are $u_1(1--0)v_1.$

The constructed $(0,2,4,3)$-undigraph having imbalance sequences $F = (-2,-2,3,4)$ and $(-5,-1,3)$ is shown 
in Figure \ref{fig3}.    

\begin{figure}[!ht]
\begin{center}
\resizebox{80mm}{!}{
\includegraphics{figure3}}
\caption{Result of the reconstruction of the imbalance sequences in Example 1. \label{fig3}}
\end{center}
\end{figure}

\textbf{Example 2.} The second example illustrates the application of Theorem \ref{cor01}. Let $p = 4$ and $q = 5,$ 
$F_1 = [-3,1,2,2]$ and $G_1 = [-3,-1,0,1,1].$  In this case Lemma \ref{lemma-bbounds} results 
$$
1 \leq b_{\emph{min}} \leq 3. 
$$

Theorem \ref{theorem8} gives the precise value $b_{\emph{min}} = 1.$ 

The steps of the recursive reconstruction using Theorem \ref{cor01} are as follows.

We choose $f_4 > 0,$ implying $F_2 = [-3,1,2],$ $G_2 = [-2,0,0,1,1]$ and $u_4(1--0)v_1,$ $u_4(1--0)v_2.$ Now 
$f_3 > 0,$ implying $F_3 = [-3,1],$ after sorting $G_3 = [-1,0,1,1,1]$ and $u-3(1--0)v_1,$ $u_3(1--0)v_2.$ 
Now $f_2 > 0,$ implying $F_4 = [-3],$ $G_4 = [0,0,1,1,1]$ and $u_2(1--0)v_1.$ Now $g_4 > 1,$ implying 
$G_5 = [0,0,1,1],$ $F_5 = [-2]$ and $v_5(1--0)u_1.$ Now $g_4 > 0,$ implying $G_6 = [0,0,1],$ $F_6 = [-1]$ and 
$v_4(1--0)u_1.$ Now $g_6 =1,$ implying $G_7 = [0,0],$ $F_7 = [0],$ and $v_2(1--0)u_1.$

The constructed $(0,1,4,5)$-undigraph having imbalance sequences $F = (-3,1,2,2)$ and $G = [-3,-1,0,1,1)$ is shown 
in Figure \ref{fig4}.  
 
\begin{figure}[!ht]
\begin{center}
\resizebox{80mm}{!}{
\includegraphics{figure4}}
\caption{Result of the reconstruction of the imbalance sequences in Example 2. \label{fig4}}
\end{center}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Imbalance sets in bipartite multidigraphs\label{sec-section5}}
K. B. Reid in 1978 \cite{Reid1978} introduced the concept of the score set of tournaments as the set of different 
scores (out-degrees) of a tournament. At the same time he formulated the conjecture 
that for any set of nonnegative integers $S$ 
there exists a tournament $T$ having $S$ as its score set. At the same time he proved the conjecture for 
sets containing 1, 2, or 3 elements. Hager in 1986 \cite{Hager1986} 
proved the conjecture for $|S| = 4$ and $|S| = 5$ and Yao \cite{Yao1989} published a proof of the conjecture

In an analogous manner we define the imbalance set of a bipartite multigraph $B = (U \cup V, E)$ as the union 
of the sets of different imbalances of the vertices in $U$ and $V.$  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Existence of a $(0,1,p,q)$-tournament with prescribed imbalance sets \label{subsec-subsection51}}
First we show the existence of a $(0,1,p,q)$-tournament with given set of integers as imbalance sets.

\begin{theorem}\label{theorem11} Let $F=[f_{1},\ldots,f_{p}]$ and $G=[-g_{1},\ldots,-g_{p}],$ 
where $f_{1},\ldots,f_{p},g_{1},\ldots,g_{p}$ are positive integers with $f_{1}< \cdots < f_{p}$ 
and $g_{1} < \cdots < g_{p}.$ Then there exists a connected $(0,1,p,p)$-tournament with imbalance set $F\cup G$.
\end{theorem}
\begin{proof} Construct a $(0,1,p,q)$-tournament $B(U\cup V,E)$ as follows. Let $U = U_1 \cup \cdots \cup U_p,$  
$V = V_1 \cup \cdots \cup V_p$ with $U_i \cap U_j = \emptyset \ (i\not= j),$  
$V_i \cap V_j =\emptyset \ (i \not= j),$ $|U_i|= b_i$ 
for all $i,$ $1 \leq i \leq p$ and $|V_j| = a_j$ for all $j,$ $1 \leq j \leq p$. Let there be an arc 
from every vertex of $U_i$ to each vertex of $V_i$ for all $i,$ $1\leq i\leq p,$ so that we obtain the 
$(0,1,p,q)$-tournament $B(U\cup V,E)$ with the given imbalance sets of vertices as follows.

For $1 \leq i,j \leq p,$ $f_{u_{i}} = |V_i|-0=f_{i},$ for all $u_{i}\in U_{i}$ and 
$g_{v_{j}}=0-|U_{j}|=-g_{j},$ for all $v_{i}\in V_{i}.$ 

Therefore, the imbalance set of $B(U\cup V,E)$ is $F\cup G.$

The oriented bipartite graph constructed above is not connected. In order to see the existence of oriented 
bipartite graph, whose underlying graph is connected, we proceed as follows.

Taking $U_{i}=\{u_1, \ldots, u_{b_{i}}\}$ and $V_{j}=\{v_1, \ldots, v_{a_{j}}\}$, and let there be an arc 
from each vertex of $U_{i}$ to every vertex of $V_{j}$ except the arcs  between $u_{g_{i}}$ and $v_{f_{j}}$, 
that is $u_{b_{i}}(0-0)g_{a_{j}}$, $1\leq i\leq p$ and $1\leq j\leq p$. We take $u_{g_{1}}(0-0)g_{f_{2}}$, 
$u_{g_{2}}(0-0)v_{f_{3}},$ and so on $u_{g_{(n-1)}}(0-0)v_{f_{n}}$, $u_{g_{n}}(0-0)v_{f_{1}}$. 
The underlying graph of this $(0,1,p,p)$-tournament is connected.  
\end{proof} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Existence of a $(0,b,p,q)$-tournament with prescribed imbalances \label{subsec-subsection52}}
Finally, we prove the existence of a $(0,b,p,q)$-tournament with prescribed sets  
of positive integers as its imbalance set.

Let $(f_{1},\ldots,f_{p},g_{1},\ldots,g_{q})$ 
denote the greatest common divisor of \linebreak 
\noindent $f_{1}, \ldots, f_{p}, g_{1}, \ldots, g_{q}.$

\begin{theorem}\label{theorem12} Let $b \geq 1$ a positive integer, 
$F = [f_{1},\ldots, f_{p}]$ and $Q = [-g_{1}, \ldots, -g_{q} ],$  
where $f_{1}, \ldots, f_{p},g_{1}, \ldots, g_{q}$ are positive integers with $f_{1} < \cdots < f_{p},$  
$g_{1} < \cdots < g_{q}$ and $(f_{1},\ldots, f_{p}, g_{1}, \ldots, g_{q}) = t \leq b_{min}.$  
Then there exists a connected $(0,b,p,q)$-tournament with imbalance set $P\cup Q.$  
\end{theorem}
\begin{proof} Since $(f_{1}, \ldots, f_{p}, g_{1}, \ldots, g_{q}) = t,$ where $1\leq t\leq b,$  
there exist positive integers $x_{1}, \ldots, x_{p}, y_{1}, \ldots, y_{q}$ with $x_{1} <  \cdots < x_{p},$  
$y_{1} < \cdots < y_{q}$ such that $f_{i} = tx_{i}$ for $1 \leq i \leq p$ and $g_{j} = ty_{j}$ for $1 \leq j \leq q.$ 

Construct a $(0,b,p,q)$-tournament $B(U\cup V,E)$ as follows. Let 
$U = U_1 \cup \cdots \cup U_p \cup U^1 \cup \cdots \cup U^p,$  
$V = V_1 \cup \cdots \cup V_p \cup V^1 \cup \cdots \cup V^p$ 
with $U_i \cap U_j = \emptyset,$ $U_i \cap U^j = \emptyset,$ $U^i \cap U^j =\emptyset,$ $V_i \cap V_j = \emptyset),$  
$V_i \cap V^j = \emptyset,$ $V^i \cap V^j = \emptyset,$ $i\not= j,$ $|U_i|=x_i$ for all $i,$ $1 \leq i \leq p$ and 
$|U^i| = g_i$ for all $i,$ $1 \leq i \leq p,$ $|V_i| = x_i$ for all $i,$ $1 \leq i \leq p$ and $|V^i| = g_i$ 
for all $i,$ $1 \leq i \leq q.$ Let there be $t$ arcs directed from every vertex  of $U_i$ to each vertex of $V_i$ 
for all $i,$ $1 \leq i \leq p$ and let there be $t$ arcs directed from every vertex of $U^i$ to each vertex of 
$V^i$ for all $i,$ $1\leq i\leq q$, so that we obtain the $(0,b,p,q)$-tournament  
$B(U\cup V,E)$ with the imbalances of vertices as follows.

For $1 \leq i \leq p,$ 
\begin{equation*}
f_{u_{i}} = t | V_i | - 0 = tx_{i}=f_{i}, \hbox{ for all } u_{i}\in U_{i},
\end{equation*}
\begin{equation*}
 g_{v_{i}}=0-t|U_{i}|=-ty_{1}=-g_{1}, \hbox{for all } v_{i}\in V_{i},
\end{equation*}
for $1\leq i\leq q$,
\begin{equation*}
f_{u^{i}}=t|V^i|-0=tf_{1}=g_{1}, \hbox{ for all } u^{i}\in U^{i},
\end{equation*}
\begin{equation*}
g_{v^{i}}=0-t|U^{i}|=-ty_{i}=-g_{i}, \hbox{ for all } v^{i}\in V^{i}.
\end{equation*}

Therefore the imbalance set of $B(U\cup V,E)$ is $P\cup Q.$ 

The $(0,b,p,q)$-tournament constructed above is not connected. In order to see the existence 
of a $(0,b,p,q)$-tournament, whose underlying graph is connected, we proceed as follows.

Let $U_{i}=\{u_1, \ldots, u_{g_{i}}\}$ and $V_{j}=\{v_1, \ldots, v_{f_{j}}\}$, and let there be an arc 
from each vertex of $U_{i}$ to every vertex of $V_{j}$ except the arcs  between $u_{g_{i}}$ and $v_{f_{j}}$, 
that is $u_{g_{i}}(0-0)v_{f_{j}}$, $1 \leq i \leq q$ and $1 \leq j \leq q.$ We take $u_{g_{1}}(0-0)v_{f_{2}}$, 
$u_{b_{2}}(0-0)v_{a_{3}}$, and so on $u_{b_{(n-1)}}(0-0)v_{a_{n}}$, $u_{b_{n}}(0-0)v_{a_{1}}$. 
The underlying graph of this $(0,b,p,q)$-tournament  is connected.
\end{proof}

An overview of the results on score sets can be found in \cite{PirzadaIK2011}.

\begin{thebibliography}{0}

\bibitem{Avery1991} \textbf{Avery P.,} Score sequences of oriented graphs, 
\textit{J. Graph Theory} \textbf{15(3)} (1991), 251--257.

\bibitem{Beineke1981} \textbf{Beineke, L. W. and J. W. Moon,} On bipartite tournaments and scores, in  
\textit{The Theory of Applications of Graphs,} John Wiley and Sons, Inc., 
New York, 1981, pp. 55--71. 

\bibitem{Cormen2009} \textbf{Cormen, T. H.,  C. E. Leiserson, R. L. Rivest and C. Stein,}   
\textit{Introduction to Algorithms,} Third edition, MIT Press/McGraw Hill, Cambridge/New 
York, 2009.

\bibitem{Erdos1960} \textbf{Erd\H os, P. and T. Gallai,} Graphs with prescribed degrees of 
vertices, (Hungarian). \textit{Mat. Lapok} \textbf{11} (1960), 264--274. 

\bibitem{Gross2004} \textbf{Gross, J. L. and J. Yellen,} 
\textit{Handbook of Graph Theory,} CRC Press, Boca Raton, 2004. 

\bibitem{Hager1986} \textbf{Hager, M.,} On score sets for tournaments, \textit{Discrete Math.}   
\textbf{58(1)} (1986), 25--34.

\bibitem{Hakimi1962} \textbf{Hakimi, S. L.} On realizability of a set of integers as degrees of the vertices 
of a simple graph, \textit{J. SIAM Appl. Math.} \textbf{10} (1962), 496--506. 

\bibitem{Havel1955} \textbf{Havel, V.} A remark on the existence of finite graphs, (Czech) 
\textit{\u{C}asopis P\u{e}st. Mat.} \textbf{80} (1955), 477--480. 

\bibitem{Ivanyi2009} \textbf{Iv\'anyi, A.,} Reconstruction of complete interval tournaments, \textit{Acta Univ.  
Sapientiae, Inform.} \textbf{1(1)} (2009), 71--88.

\bibitem{Ivanyi2010} \textbf{Iv\'anyi, A.,} Reconstruction of complete interval tournaments II,  
\textit{Acta Univ. Sapientiae, Math.} \textbf{2(1)} (2010), 47--71. 

\bibitem{IvanyiLMS2011} \textbf{Iv\'anyi, A., L. Lucz, F. T. M\'ori and P. S\'ot\'er,} 
On Erd\H os-Gallai and Havel-Hakimi algorithms,   
\textit{Acta Univ. Sapientiae, Inform.} \textbf{3(2)} (2011), 230--269.  

\bibitem{IvanyiP2011} \textbf{Iv\'anyi, A., S. Pirzada,} Comparison based ranking, in (ed. A. Iv\'anyi) 
\textit{Algorithms of Informatics, Vol. 3,} AnTonCom, Budapest, 2011, pp. 1262--1311,     

\bibitem{Landau1953} \textbf{Landau, H. G.} On dominance relations and the structure of animal societies. 
III. The condition for a score structure, \textit{Bull. Math. Biophys.}  
\textbf{15} (1953), 143--148.

\bibitem{Moon1962} \textbf{Moon, J. W.} On the score sequence of an $n$-partite tournament,   
\textit{Can. Math. Bull.} \textbf{5} (1962), 51--58.  

\bibitem{Moon1963} \textbf{Moon, J. W.} An extension of Landau's theorem, \textit{Pacific J. Math.}  
\textbf{13} (1963), 1343--1345.

\bibitem{Mubayi2001} \textbf{Mubayi, D., T. G. Will and D. B. West,}    
Realizing degree imbalances in directed graphs, \textit{Discrete Math.}  
\textbf{239(1--3)} (2001), 147--153. 

\bibitem{Pirzada2008} \textbf{Pirzada S.,} On imbalances in digraphs, \textit{Kragujevac J. Math.}   
\textbf{31} (2008), 143--146.

\bibitem{Pirzada2009} \textbf{Pirzada, S.,} Degree sequences of $k$-multi-hypertournaments. 
\textit{Appl. Math. J.} \textit{Chinese Univ. Ser. B.,} \textbf{24(3)} (2009), 350-354. 

\bibitem{Pirzada2012} \textbf{Pirzada, S.,} \textit{Graph Theory,} Orient BlackSwan, Hyderabad, 2012.
  
\bibitem{PirzadaAK2011} \textbf{Pirzada, S., A. M. Al-Assaf and  K. K. Kayibi,}    
On imbalances in oriented multipartite graphs,  
\textit{Acta Univ. Sapientiae, Math.} \textbf{3(1)} (2011), 34--42.

\bibitem{PirzadaIK2011} \textbf{Pirzada, S., A. Iv\'anyi and M. A. Khan,} Score sets and kings, in (ed. A. Iv\'anyi) 
\textit{Algorithms of Informatics, Vol. 3,} AnTonCom, Budapest, 2011, pp. 1451--1490.   

\bibitem{PirzadaMJ2000} \textbf{Pirzada, S.,  Merajuddin and Y. Jainhua,} On the scores of oriented bipartite 
graphs, \textit{J. Math. Study} \textbf{33(4)} (2000), 354--359.

\bibitem{PirzadaN2008} \textbf{Pirzada, S. and T. A. Naikoo,} Score sets in oriented graphs.   
\textit{Appl. Anal. Discrete Math.} \textbf{2(1)} (2008), 107--113.  

\bibitem{PirzadaNC2006} \textbf{Pirzada, S., T. A. Naikoo and T. A. Chishti,} Score sets in oriented 
bipartite graphs, \textit{Novi Sad J. Math.} \textbf{36(1)} (2006), 35--45.

\bibitem{PirzadaNSI2010} \textbf{Pirzada, S., T. A. Naikoo, U. Samee and A. Iv\'anyi,}    
Imbalances in directed multigraphs, \textit{Acta Univ. Sapientiae, Inform.} \textbf{2(2)} (2010), 137--145.
		
\bibitem{PirzadaNS2011} \textbf{Pirzada, S., T. A. Naikoo and N. A. Shah,} Imbalances in oriented 
tripartite graphs, \textit{Acta Math. Sinica} \textbf{27(5)} (2011), 927--932. 

\bibitem{PirzadaZ2010} \textbf{Pirzada, S. and G. Zhou,} On $k$-hypertournament losing scores, 
\textit{Acta Univ. Sapientiae, Inform.} \textbf{2(1)} (2010), 5--9.

\bibitem{PirzadaZI2010} \textbf{Pirzada, S., G. Zhou and A. Iv\'anyi,} 
Score lists of multipartite hypertournaments, \textit{Acta Univ. Sapientiae, Inform.} \textbf{2(2)} (2010), 184--193.
	
\bibitem{Reid1978} \textbf{Reid, K. B.,} Score sets for tournaments. \textit{Proc. Ninth Southeastern Conf. 
Comb., Graph Theory, Computing} (Florida Atlantic Univ., Boca Raton, FL, 1978), 
pp. 607--618, \textit{Congress. Numer.}, \textbf{XXI}, 1978. 
 
\bibitem{ReidZ1998} \textbf{Reid, K. B. and C. Q. Zhang,} Score sequences of semicomplete digraphs, 
\textit{Bull. Inst. Combin. Appl.} \textbf{24} (1998), 27--32.

\bibitem{Samee2010} \textbf{Samee, W. and T. A. Chishti,} Imbalances in oriented bipartite graphs, 
\textit{Eurasian Math. Journal} \textbf{1(2)} (2010), 136--141. 

\bibitem{Yao1989} \textbf{Yao, T. X.,} On Reid conjecture of score sets for tournaments. 
\textit{Chinese Sci. Bull.} \textbf{34} (10) (1989), 804--808.

\end{thebibliography}

\bigskip
\bigskip
\noindent \textbf{Shariefuddin Pirzada} 

\noindent University of Kashmir, Department of Mathematics

\noindent Srinagar

\noindent India

\noindent \texttt{sdpirzada@yahoo.co.in}

\bigskip
\bigskip
\noindent \textbf{Antal Iv\'anyi} 

\noindent E\"otv\"os Lor\'and University, Department of Computer Algebra

\noindent Budapest

\noindent Hungary

\noindent \texttt{tony@compalg.inf.elte.hu}

\bigskip
\bigskip
\noindent \textbf{Namir A. Shah} 

\noindent University of Kashmir, Department of Mathematics

\noindent Srinagar

\noindent India

\noindent \texttt{wmshah@rediffmail.com.in}

\end{document}

