\documentclass[reqno,12pt]{amsart}

\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
%\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}


\numberwithin{theorem}{section}
\numberwithin{lemma}{section}
\numberwithin{equation}{theorem}

\textwidth15.6cm
\textheight22.8cm
\hoffset-2truecm
\voffset-.5truecm

\begin{document}
\newbox\Adr
\setbox\Adr\vbox{
\centerline{\sc S. Pirzada$^{1}$ and U. Samee$^{2}$}
\vskip18pt
\centerline{$^{1}$Department of Mathematics,}
\centerline{University of Kashmir, Srinagar, India}
\centerline{Email: {\tt sdpirzada@yahoo.co.in}}
\vskip18pt
\centerline{$^{2}$Department of Applied Mathematics,}
\centerline{AMU, Aligarh, India}
}

\title{Mark sequences in digraphs}

\author[S. Pirzada and U. Samee]{\box\Adr}

\subjclass[2000]{05C20}

\begin{abstract}
A $k$-digraph is an orientation of a multi-graph that is
without loops and contains at most $k$ edges between any pair of distinct
vertices. We obtain necessary and sufficient conditions for a sequence of
non-negative integers in non-decreasing order to be a sequence of numbers,
called marks ($k$-scores), attached to vertices of a $k$-digraph. We characterize
irreducible and uniquely realizable mark sequences in $k$-digraphs.
\end{abstract}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 55 \rms (2006), Article~B55c\hfill}
\def\thepage{}
%
%

\section{Introduction} 
Let $D$ be a $k$-digraph with vertex set $V = \{ v_{1}
,v_{2} ,\dots, v_{n}\}$, and let $d^{+}(v_{i})$ and $d^{-}(v_{i})$ denote
the outdegree and indegree, respectively, of a vertex $v_{i}$. Define
$p_{v_{i}}$ (or $p_{i}$) ${}= k(n-1)+d^{+}(v_{i})-d^{-}(v_{i})$, as the
{\it mark\/} of $v_{i}$, so that $0\leq p_{v_{i}}\leq2k(n-1).$ The sequence $P =
[p_{i}]_{1}^{n}$ in non-decreasing order is called the 
{\it mark sequence} of $D$.

A $k$-digraph can be interpreted as the result of a competition in which the
participants play each other at most $k$ times, with an arc from $u$ to $v$ if and
only if $u$ defeats $v$. A player receives two points for each win, and one point
for each tie (draw), that is the case in which the two players do not play one
another or the competition between the players yields no result. With this
marking system, player $v$ obtains a total of $p_{v}$ points.

A sequence $P$ of non-negative integers in non-decreasing order is said to be
{\it realizable} if there exists a $k$-digraph with mark sequence P.

Any undefined terms are found in [3,5], and one should also take into account
the non-standard definitions and notations introduced in this paper.

In a $k$-digraph, if there are $x_{1}$ arcs directed from vertex $u$ to vertex $v$,
and $x_{2}$ arcs directed from vertex $v$ to vertex $u$, with $0 \leq x_{1} ,
x_{2}\leq k$ and $0 \leq x_{1} + x_{2}\leq k$, we denote this by
$u(x_{1}-x_{2})v$.

We have one of the following six possibilities between any two vertices $u$ and
$v$ in a 2-digraph:

\begin{enumerate} 
\item[(i)] exactly two arcs directed from $u$ to $v$, and no arc directed from $v$ to $u$;
this is denoted by $u(2 - 0)v$;

\item[(ii)] exactly two arcs directed from $v$ to $u$, and no arc directed from $u$ to $v$;
this is denoted by $u(0-2)v$;

\item[(iii)] exactly one arc from $u$ to $v$, and exactly one arc from $v$ to $u$; this
is denoted by $u(1 - 1)v$;

\item[(iv)] exactly one arc from $u$ to $v$, and no arc from $v$ to 
$u$; this is denoted by
$u(1 - 0)v$;

\item[(v)] exactly one arc from $v$ to $u$, and no arc from $u$ to $v$; this is denoted by $u(0
- 1)v$;

\item[(vi)] no arc from $u$ to $v$, and no arc from $v$ to $u$; 
this is denoted by $u(0-0)v$.
\end{enumerate}

We note that a 1-digraph is an oriented graph, and a complete 1-digraph is a
tournament. A $k$-digraph $D$ is said to be {\it complete} if there are exactly $k$ arcs
between any pair of vertices of $D$.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL S. PIRZADA AND U. SAMEE}{\SMALL MARK SEQUENCES IN DIGRAPHS}
%
%

A {\it $k$-triple} in a $k$-digraph is an induced $k$-subdigraph with three vertices, and
is of the form $u(x_{1}-x_{2})v(y_{1}-y_{2})w(z_{1}-z_{2})u$, where,
for $i = 1 , 2$, we have $0 \leq x_{i} , y_{i}, z_{i}\leq k$ and
$0\leq\sum_{i=1}^{2}x_{i},\sum_{i=1}^{2}y_{i},\sum_{i=1}^{2}z_{i}\leq k$.
Also, in a $k$-digraph a 1-triple is an induced 1-subdigraph with three
vertices. A 1-triple is said to be {\it transitive} if it is of the form
$u(1-0)v(1-0)w(0-1)u$, or $u(1-0)v(0-1)w(0-0)u$, or 
$u(1-0)v(0-0)w(0-1)u$, or
$u(1-0)v(0-0)w(0-0)u$, or $u(0-0)v(0-0)w(0-0)u$, otherwise it is said to be
{\it intransitive}. A $k$-triple is said to be {\it transitive} if it contains only
transitive 1-triples, and a $k$-digraph is said to be {\it transitive} if every of its
$k$-triples is transitive.

A {\it tournament\/} is an irreflexive, complete, asymmetric digraph.
The {\it score}
s$_{v}$ of a vertex $v$ in a tournament is the number of arcs directed away from
that vertex, and the {\it score sequence} $S(T)$ of a tournament $T$ is formed by
listing the vertex scores in non-decreasing order. The following criterion is
given by Landau [4].

\begin{theorem}[{[4]}]A sequence $[s_{i}]_{1}^{n}$ of non-negative
integers in non-decreasing order is the score sequence of a tournament if and
only if
$$\sum_{i=1}^{k}s_{i}\geq\binom k2,\quad \quad 
\text{for }1\leq k\leq n,
$$
with equality for $k = n$.
\end{theorem}

With the marking system, the mark $p_{v}$ of a vertex $v$ in a tournament is
given by $p_{v} = 2s_{v} + n - 1$, and Landau's conditions become
$$
\sum_{i=1}^{k}p_{i}\geq k(n+k-2),\quad \quad 
\text{for } 1\leq k\leq n,
$$
with equality for $k = n$.\bigskip

An {\it oriented graph} is a digraph with no symmetric pairs of directed arcs and
without self-loops. Avery [2] defined $a_{v}= n-1+d^{+}(v)-d^{-}(v)$, $0
\leq a_{v}\leq 2n - 2$, as the score of a vertex $v$ in an oriented graph $D$,
and $A = [a_{1}, a_{2},\dots,a_{n}]$ in non-decreasing order is the score
sequence of $D$. The following result is due to Avery, and a constructive proof
can be found in [8].

\begin{theorem}[{[2]}] A sequence $A = [a_{i}]_{1}^{n}$ of non-negative
integers in non-decreasing order is the score sequence of an oriented graph if
and only if
$$
\sum_{i=1}^{k}a_{i}\geq k(k-1),\quad \quad 
\text{for }1\leq k\leq n,
$$
with equality for $k = n$.
\end{theorem}

Once again, with the marking system, the mark $p_{v}$ of a vertex $v$ in an
oriented graph is given by $p_{v} = a_{v} + n - 1$, and Avery's conditions become
$$
\sum_{i=1}^{k}p_{i}\geq k(n+k-2),\quad \quad 
\text{for }1\leq k\leq n,
$$
with equality for $k = n$.\bigskip


\section{Mark sequences in digraphs}


A $k$-digraph $D$ is said to be {\it complete} if there are exactly $k$ arcs between every
pair of vertices of $D$. If in a $k$-digraph $D$ there are exactly $k$ arcs, which are
parallel, between every pair of vertices of $D$, then $D$ is called a
{\it$k$ tournament}. A double tournament can be treated as a tournament whose arcs have
been duplicated.

The following result can be easily established, and is analogous to
Theorem~2.2 of Avery [2].

\begin{lemma} If $D$ and $D'$ are two $k$-digraphs with the same mark
sequence, then $D$ can be transformed to $D'$ 

\begin{enumerate}
\item[]\leavevmode\kern-26pt
{\em(i)} by successively
transforming 1-triples in one of the following ways:
\item[]\leavevmode\kern-10pt
either {\em(a)} by changing the intransitive 1-triple $u(1-0) v(1-0) w(1-0)u$ to a
transitive 1-triple $u(0-0) v(0-0) w(0-0)u$, which has the same mark sequence,
or vice versa,
\item[]\leavevmode\kern-10pt
or {\em(b)} by changing an intransitive 1-triple $u(1-0) v(1-0) w(0-0)u$ to a
transitive 1-triple $u(0-0) v(0-0) w(0-1)u$, which has the same mark sequence,
or vice versa.
\item[]\leavevmode\kern-26pt
or {\em(ii)} by changing a double $u(1-1)v$ to a double $u(0-0)v$ which has the same
mark sequence, or vice versa.
\end{enumerate}
\end{lemma}

We note here that, in a transitive tournament $T$, all its 1-triples are of the
form $u(1- 0)v(1- 0)w(0- 1)u$, for all vertices $u$, $v$ and $w$ in $T$. Similarly, in a
transitive oriented graph, all the 1-triples are of the form 
$u(1 - 0)v(1 -
0)w(0 - 1)u$, $u(1 - 0)v(0 - 1)w(0 - 0)u$, $u(1 - 0)v(0 - 0)w(0 - 1)u$, $u(1 - 0)v(0
- 0)w(0 - 0)u$, $u(0 - 0)v(0 - 0)w(0 - 0)u$. Clearly, in the transitive double
tournament $D$, we have $u(2-0)v(2-0)w(0-2)u$ for all vertices $u$, $v$ and $w$ in $D$.\bigskip

Now, we have the following observation.

\begin{theorem}Among all $k$-digraphs with a given mark sequence those
with the fewest arcs are transitive.
\end{theorem}
\begin{proof} Let $P$ be a mark sequence, and let $D$ be a realization of $P$ that
is not transitive. Then $D$ contains an intransitive 1-triple. If it is of the
form $u(1-0) v(1-0) w(1-0)u$, it can be transformed by operation (i)(a)
of Lemma~2.1 to a transitive 1-triple $u(0-0) v(0-0) w(0-0)u$ with the same mark sequence
and three arcs fewer. If $D$ contains an intransitive 1-triple of the form
$u(1-0) v(1-0) w(0-0)u$, it can be transformed by operation (i)(b) of Lemma~2.1 to
a transitive 1-triple of the form $u(0-0) v(0-0) w(0-1)u$ with the same mark
sequence and one arc fewer. If $D$ contains both types of intransitive
1-triples, then again they can be transformed to transitive 1-triples, and
certainly with lesser arcs. In case $D$ contains a double $u(1-1)v$, it can be
transformed to $u(0-0)v$ by operation (ii) of Lemma~2.1 with the same mark sequence
and two arcs fewer.
\end{proof}

The following result is the existence criteria for realizability of mark
sequences in $k$-digraphs.

\begin{theorem} A sequence $[p_{i}]_{1}^{n}$ of non-negative
integers in non-decreasing order is the mark sequence of a $k$-digraph if and
only if
$$
\sum_{i=1}^{t}p_{i}\geq kt(t-1),\quad \quad 
\text{for }1\leq t\leq n,
$$
with equality for $t = n$.
\end{theorem}
\begin{proof} (i) {\sc Sufficiency.} Let $q_{i}= p_{i}-k(n-1)$. Then
$\sum_{i=1}^{n}q_{i}=0$, and we may assume that $q_{1}\leq q_{2}
\leq\dots\leq q_{r}<0\leq q_{r+1}\leq\dots\leq q_{n}.$

Construct a network with vertex set $\{s, v_{1}, v_{2},\dots, v_{n}, t\}$ of
cardinality $n+2$ as follows.

\begin{enumerate} 
\item There are arcs $(s, v_{i})$, $1\leq i\leq r$ from the source s to vertex
$v_{i}$. The arc $(s, v_{i})$ has capacity $-q_{i}$, $1\leq i\leq r.$
\item Arcs $(v_{i}, t)$ from $v_{i}$ to the sink $t$, $r+1\leq i\leq n.$ The arc
$(v_{i}, t)$ has capacity $-q_{i}.$
\item For each pair $v_{i}, v_{j}$ of distinct vertices ($i \neq j$), we have
one arc from $v_{i}$ to $v_{j}$ and one arc from $v_{j}$ to $v_{i}$, each with
capacity $k$.
\end{enumerate}

It is easy to check that a $k$-digraph with mark sequence $[p_{i}]_{i}^{n}$
can be obtained from an integral flow of value $-\sum_{i=1}^{r}q_{i}%
=\sum_{i=r+1}^{n}q_{i}$ by reducing the flow on cycles of length 2 until one
of the two edges has flow value zero.

In view of the max-flow-min-cut-Theorem, it suffices to check that each cut has
capacity at least $\sum_{i=r+1}^{n}q_{i}.$

We thus assume that $\{s\}\cup C$ is a cut, $C \subseteq \{v_{1}, v_{2}%
,\dots, v_{n}\}$, $\left|  C\right|   = t$, and that $\left|  C\cap
\{v_{1},v_{2},\dots,v_{r}\}\right|  =a$ and
$ \left|  C\cap\{v_{r+1},v_{r+2}%
,\dots,v_{n}\}\right|  =b=t-a.$

For its capacity, we have the following estimate.
\begin{align*}
\text{cap} (\{s\}\cup C) &=\sum_{i:i\leq r,v_{i}\notin C}-q_{i}+\sum_{i:i>r,v_{i}%
\in C}q_{i}+t(n-t)\cdot k\\
&\geq-\sum_{i=a+1}^{r}q_{i}%
+\sum_{i=r+1}^{r+b}q_{i}+t(n-t)\cdot k\smallskip.
\end{align*}
This expression is bounded from below by $-\sum_{i=1}^{r}q_{i}=\sum
_{i=r+1}^{n}q_{i}$
if and only if 
$$\sum_{i=1}^{a}q_{i}+\sum_{i=r+1}^{r+b}q_{i}%
+t(n-t)\cdot k\geq0,$$
if and only if 
$$\sum_{i=1}^{a}p_{i}+\sum_{i=r+1}^{r+b}p_{i}%
+t(n-t)\cdot k\geq t\cdot k(n-1)$$
(since $p_{i} = k(n-1)+q_{i}$),
if and only if 
$$\sum_{i=1}^{a}p_{i}+\sum_{i=r+1}^{r+b}p_{i}\geq kt(t-1).$$
This latter inequality is certainly implied by the inequality
$$
\sum_{i=1}^{t}p_{i}\geq kt(t-1),
$$
since the $p_{i}$ are non-decreasing.

\medskip
{(ii) \sc Necessity.} Follows from the construction in (i) if we use the cuts\linebreak
$\{s\}\cup\{v_{1}, v_{2},\dots, v_{t}\}$, $1\leq t\leq n$.
\end{proof}

The following result is the existence criteria for realizability of mark
sequences in 2-digraphs.\bigskip\ The proof follows from Theorem 2.2. Here we
give a different proof.

\begin{theorem} A sequence $[p_{i}]_{1}^{n}$ of non-negative
integers in non-decreasing order is the mark sequence of a 2-digraph if and
only if
\begin{equation} \label{2.3.1} 
\sum_{i=1}^{k}p_{i}\geq2k(k-1),\quad \quad 
\text{for }1\leq k\leq n,
\end{equation}
with equality for $k = n$.
\end{theorem}
\begin{proof}{\sc Necessity.} Let $D$ be a 2-digraph with mark sequence $[p_{i}%
]_{1}^{n}$. Let $W$ be the 2-subdigraph induced by any set of $k$ vertices
$w_{1}, w_{2}, \dots, w_{k}$ of $D$. Let $\alpha$ denote the number of arcs of $D$
that start in $W$ and end outside $W$, and let $\beta$ denote the number of arcs of $D$
that start outside of $W$ and end in $W$. Note that each vertex $w$ in $W$, and for
every vertex $v$ of $D$ not in $W$, there are at most two arcs from $v$ to $w$, so that
$\beta\leq 2k(n - k)$. Therefore, we have $\beta\leq 2nk - 2k^{2}$. Then,
\begin{align} \notag
\sum_{i=1}^{k}p_{w_{i}}&=\sum_{i=1}^{k}(2n-2+d_{D}^{+}(w_{i})-d_{D}^{-}%
(w_{i}))\\
\notag
&=2nk-2k+\sum_{i=1}^{k}d_{D}^{+}(w_{i})-\sum_{i=1}^{k}%
d_{D}^{-}(w_{i})\\
\notag
&=2nk-2k+\left[  \sum_{i=1}^{k}d_{W}^{+}(w_{i}%
)+\alpha\right]  -\left[  \sum_{i=1}^{k}d_{W}^{-}(w_{i})
+\beta\right]  \\
\notag
&=2nk-2k+ (\text{number of arcs of }W) + \alpha - (\text{number of
arcs of }W) - \beta\\
\label{2.3.2}
&=2nk-2k+\alpha-\beta\\
\notag
&\geq2nk-2k-\beta\\
\notag
&\geq2nk-2k-2nk+2k^{2}=2k(k-1).
\end{align}
Applying this result to the $k$ vertices with marks $p_{1}, p_{2},\dots,
p_{k}$ yields the desired inequality. If $k = n$, then 
$\alpha=\beta=0$, and
the required equality follows from Equation~(2.3.2).

\medskip
{\sc Sufficiency.} This is proved by contradiction. Assume all sequences of
non-negative integers in non-decreasing order of length fewer than $n$
satisfying conditions (2.3.1) be the mark sequences. Let $n$ be the smallest and
with this choice of $n$, $p_{1}$ be the smallest possible such that $P = [p_{i}%
]_{1}^{n}$ is not a mark sequence. Two cases arise,

\begin{enumerate} 
\item[(a)] equality in (2.3.1) holds for some $k
<n$, and
\item[(b)] each inequality in (2.3.1) is strict for all $k
<n$.
\end{enumerate}

\medskip
{\sc Case} (a). Assume $k$ ($k
<n$) is the smallest such that
$$
\sum_{i=1}^{k}p_{i}=2k(k-1).
$$
Clearly, the sequence $[p_{1}, p_{2},\dots, p_{k}]$ satisfies conditions
(2.3.1), and is a sequence with length less than $n$. So, by assumption,
$[p_{i}]_{1}^{k}$ is a mark sequence of some 2-digraph, say $D_{1}$.
Further,
\begin{align*}
\sum_{i=1}^{m}(p_{k+i}-4k)&=\sum_{i=1}^{m+k}p_{i}-\sum_{i=1}^{k}%
a_{i}-4mk\\
&\geq
2(m+k)(m+k-1)-2k(k-1)-4mk\\
&=2m(m-1),
\end{align*}
for each $m$, $1 \leq m \leq n-k$, with equality when $m = k$. As $m
<n$, thus by the minimality of $n$, the sequence $[p_{k+1}-4k, p_{k+2}-4k,\dots,
p_{n}-4k]$ is the mark sequence of some 2-digraph $D_{2}$. The 2-digraph $D$ of
order $n$ consisting of disjoint copies of $D_{1}$ and $D_{2}$, such that
$u(2-0)v$ for each vertex $u \in D_{2}$ and for each vertex $v \in D_{1}$,
has mark sequence $P = [p_{i}]_{1}^{n}$, which is a contradiction.

\medskip
{\sc Case} (b). Assume that each inequality in condition (2.3.1) is strict
for all $k<n$. Obviously, $p_{1}
>0$. Consider the sequence $P' = [p_{i}']_{1}^{n}$, defined by
$$
p_{i}'=\begin{cases} 
p_{i}-1,& \text{if }i=1,\\
p_{i}+1,& \text{if }i=n,\\
p_{i},&\text{otherwise}.
\end{cases}
$$
Then,
$$
\sum_{i=1}^{k}p_{i}'=\left(  \sum_{i=1}^{k}%
p_{i}\right)  -1>2k(k-1)-1 \geq 2k(k-1),$$ 
for all $k$, $1 \leq k<n$, and
$$
\sum_{i=1}^{n}p_{i}'=\left(  \sum_{i=1}^{n}p_{i}\right)
-1+1=2n(n-1).$$
This shows that the sequence $P' = [p_{i}']_{1}^{n}$ satisfies
condition (2.3.1), and therefore is a mark sequence of some 2-digraph $D$. Let $u$
and $v$ denote the vertices with marks $p_{i}'=p_{i}-1$ and $p_{n}'%
=p_{n}-1$ respectively.

If in $D$, $u(0-2)v$, or $u(1-1)v$, or $u(1-0)v$, or $u(0-1)v$, or $u(0-0)v$, then
transforming them respectively to $u(0-1)v$, or $u(1-0)v$, or $u(2-0)v$, or $u(1-1)v$,
or $u(1-0)v$, we obtain a 2-digraph with mark sequence $P$, a contradiction.

In $D$, let $u(2-0)v$. We have $p_{v}'\geq p_{u}'+2.$ If there exists at
least one vertex $w \in D-\{u , v\}$ such that the 2-triples formed by the
vertices $u$, $v$ and $w$ contain an intransitive 1-triple of the form
$u(1-0)v(1-0)w(1-0)u$, or $u(1-0)v(1-0)w(0-0)u$, or $u(1-0)v(0-0)w(1-0)u$,
transforming them respectively to $u(1-0)v(0-0)w(0-0)u$, or $u(1-0)v(0-0)w(0-1)u$,
or $u(1-0)v(0-1)w(0-0)u$, we obtain a 2-digraph with mark sequence $P$, which is a contradiction.

Assume for each vertex $w \in D-\{u , v\}$, the 2-triples formed by the
vertices $u$, $v$ and $w$ contain only transitive 1-triples of the form

\begin{enumerate} 
\item[(i)] $u(1-0)v(1-0)w(0-1)u$, 
\item[(ii)] $u(1-0)v(0-1)w(1-0)u$, 
\item[(iii)] $u(1-0)v(0-1)w(0-1)u$,
\item[(iv)] $u(1-0)v(0-0)w(0-1)u$, 
\item[(v)] $u(1-0)v(0-1)w(0-0)u$, 
\item[(vi)] $u(1-0)v(0-0)w(0-0)u$.
\end{enumerate}

Then, clearly $p_{v}'<p_{u}'+2$, since $d_{u}^{+}> d_{v}^{+}$ and
$d_{u}^{-}< d_{v}^{-}$, and we get a contradiction.

If (i) appears for every vertex $w \in D-\{u , v\}$, so that the 2-triples
formed by $u$, $v$ and $w$ is of the form $u(2-0)v(2-0)w(0-1)u$, then
$$
p_{v}'=2n-2+d_{v}^{+}- d_{v}^{-}=2n-2+2(n-2)-2=4n-8,$$
and 
$$ p_{u}'=2n-2+d_{u}^{+}- d_{u}^{-}=2n-2+n-2+2=3n-2.$$
Therefore,  $p_{v}'=p_{u}'+n-6.$

For $n<8$, clearly $p_{v}'\leq p_{u}'+1$, a contradiction.

For $n \geq 8$, we do have $p_{v}'\geq p_{u}'+2$, but then
$u(2-0)v(2-0)w(0-1)u$ can be transformed to $u(2-0)v(1-0)w(0-2)u$, and we get a
2-digraph with mark sequence $P$, a contradiction.

If (ii) appears for every vertex $w\in D-\{u , v\}$ such that the 2-triple
formed by $u$, $v$ and $w$ is of the form $u(2-0)v(0-1)w(2-0)u$, then
$$
p_{v}'=2n-2+d_{v}^{+}- d_{v}^{-}=2n-2-(n-2)-2=n-2,$$
and 
$$ p_{u}'=2n-2+d_{u}^{+}- d_{u}^{-}=2n-2-2(n-2)=4.$$
Therefore,  $p_{v}'-p_{u}'=n-6,$ so that $p_{v}'=p_{u}'+n-6.$

For $n<8$, clearly $p_{v}'\leq p_{u}'+1$, a contradiction.

For $n \geq$ 8, we have $p_{v}'\geq p_{u}'+2$. Then, transforming
$u(2-0)v(0-1)w(2-0)u$ to $u(2-0)v(0-2)w(1-0)u$, we obtain a 2-digraph with mark
sequence $P$, again a contradiction.
\end{proof}

Some stronger inequalities on marks in 2-digraphs can be found in [7]. The
next result is the analogue of Havel--Hakimi theorem on degree sequences of
simple graphs.

\begin{theorem} Let $P = [p_{i}]_{1}^{n}$ be a sequence of
non-negative integers in non-decreasing order, where for each $i$, $0 \leq
p_{i}\leq 2k(n-1)$. Let $P'$ be obtained from $P$ by deleting the
greatest entry $p_{n}$ {\em(}$= 2k(n-1)-r$, say{\em)} and 
{\em(a)} if $r \leq n-1$,
reducing the $r$
greatest remaining entries by one each, or {\em(b)} if $r>
n-1$, reducing the $r-(n-1)$ greatest remaining entries by two each,
and the $2n-2-r$
remaining entries by one. Then, $P$ is a mark sequence of some $k$-digraph if and
only if $P'$ (arranged in non-decreasing order) is a mark sequence of some $k$-digraph.
\end{theorem}
\begin{proof} Let $P'$ be a mark sequence of some $k$-digraph $D'$. If
$P'$ is obtained from $P$ as in (a), then a $k$-digraph $D$ with mark sequence $P$
is obtained by adding a vertex $v$ in $D'$ such that $v((k-1)-0)v_{i}$ for
those vertices $v_{i}$ in $D'$ with mark $v_{i} = p_{i}-1$, and
$v(k-0)v_{i}$ for those vertices $v_{i}$ in $D'$ with mark $v_{i}
 =
p_{i}$. If $P'$ is obtained from $P$ as in (b), then again a $k$-digraph $D$
with mark sequence $P$ is obtained by adding a vertex $v$ in $D'$ such that
$v((k-1)-1)v_{i}$ for those vertices $v_{i}$ in $D'$ with mark $v_{i} =
p_{i}-2$ and $v((k-1)-0)v_{i}$ for those vertices $v_{i}$ in $D'$ with
mark $v_{i} = p_{i}-1$.

Conversely, let $P$ be the mark sequence of some $k$-digraph $D$. We assume $D$ is
transitive, if not $D$ becomes transitive by using Lemma~2.1. Let $V = \{v_{1},
v_{2},\dots,v_{n}\}$ be the vertex set of $D$, and let $p_{n} = 2k(n-1)-r$. If
$r \leq n-1$, construct $D$ such that $v_{n}((k-1)-0)v_{i}$ for all $i$, $n-r
\leq i \leq n-1$, and $v_{n}(k-0)v_{j}$ for all $j$, $1 \leq j \leq
n-r-1$. Clearly, $D -v_{n}$ realizes $P'$ (arranged in non-decreasing
order). If $r>
n-1$, construct $D$ such that $v_{n}((k-1)-1)v_{i}$ for all $i$, $2n-r-1 \leq i
\leq n-1$, and $v_{n}((k-1)-0)v_{j}$ for all $j$, $1 \leq j \leq 2n-r-2$.
Then again, $D - v_{n}$ realizes $P'$ (arranged in non-decreasing order).
\end{proof}

Theorem~2.4 provides an algorithm for determining whether a given
non-decreasing sequence $P$ of non-negative integers is a mark sequence, and for
constructing a corresponding $k$-digraph. At each stage, we form $P'$
according to Theorem~2.4 such that $P'$ is in non-decreasing order. If
$p_{n} = 2k(n-1) - r$, deleting $p_{n}$, and performing (a) or (b) of Theorem~2.4 according as $r \leq n - 1$, or $r
>n - 1$, we get $P' = [p_{1}', p_{2}',\dots, p_{n-1}']$. If the
mark of vertex $v_{i}$ was decreased by one in this process, then the
construction yielded $v_{n}((k-1)-0)v_{i}$, and if it was decreased by two,
then the construction yielded $v_{n}((k-1)-1)v_{i}$. For a vertex $v_{j}$
whose mark remained unchanged, the construction yielded $v_{n}(k-0)v_{j}.$
If this procedure is applied recursively, then it tests whether or not $P$ is a
mark sequence, and if $P$ is a mark sequence, then a $k$-digraph with mark
sequence $P$ is constructed.

\begin{theorem}  Let $P = [p_{i}]_{1}^{n}$ be a sequence of
non-negative integers in non-decreasing order, where for each $i$, $0 \leq
p_{i}\leq 2k(n-1)$. Let $P'$ be obtained from $P$ by deleting the
greatest entry $p_{n}$ {\em(}$= 2k(n-1)-r$, say{\em)} and 
{\em(a)} if $r$ is even, say $r = 2t$,
reducing $t$ of the next greatest entries by two, or 
{\em(b)} if $r$ is odd, say $r =
2t+1$, reducing $t$ greatest remaining entries by two, and reducing the greatest
among the remaining entries by one. Then $P$ is a mark sequence if and only if
$P'$ (arranged in non-decreasing order) is a mark sequence.
\end{theorem}

The proof follows by using the arguments as in Theorem~2.4.\bigskip

Theorem~2.5 also provides an algorithm of checking whether or not a given
non-decreasing sequence $P$ of non-negative integers is a mark sequence and for
constructing a corresponding $k$-digraph. At each stage, we form $P'$
according to Theorem~2.5 such that $P'$ is in non-decreasing order. If
$p_{n} = 2k(n-1)-r$, deleting $p_{n}$, and performing (a), or (b), of 
Theorem~2.5 according as $r$ is even or odd, we get $P' = [p_{1}', p_{2}'%
,\dots, p_{n-1}']$. If the mark of the vertex $v_{i}$ was decreased by two
in the process, then the construction yielded $v_{n}((k-1)-1)v_{i}$, and if
it was decreased by one, then the construction yielded $v_{n}((k-1)-0)v_{i}%
$. For a vertex $v_{j}$ whose mark remained unchanged, the construction
yielded $v_{n}(k- 0)v_{j}$. If this procedure is applied recursively, then
it tests whether or not $P$ is a mark sequence, and if $P$ is a mark sequence,
then a $k$-digraph with mark sequence $P$ is constructed.

\section{ Irreducible mark sequences}

A $k$-digraph is {\it reducible} if it is possible to partition its vertices into two
nonempty sets $V_{1}$ and $V_{2}$ in such a way that there are exactly two
arcs directed from every vertex of $V_{2}$ to each vertex of $V_{1}$, and
there is no arc from any vertex of $V_{1}$ to any vertex of $V_{2}$. If
$D_{1}$ and $D_{2}$ are $k$-digraphs having vertex sets $V_{1}$ and $V_{2}$
respectively, then the $k$-digraph $D$ consisting of all the arcs of $D_{1}$, and
all the arcs of $D_{2}$, and exactly $k$ arcs directed from every vertex of
$D_{2}$ to each vertex of $D_{1}$ is denoted by $D = [D_{1}, D_{2}]$. If
this is not possible, the $k$-digraph is said to be {\it irreducible}. Let $D_{1}$,
$D_{2}$, \dots, $D_{h}$ be irreducible $k$-digraphs with disjoint vertex sets. Then
$D = [D_{1}, D_{2},\dots, D_{h}]$ is the $k$-digraph having all arcs of
$D_{i}$, $1\leq i \leq h$, and exactly $k$ arcs from every vertex of $D_{j}$
to each vertex of $D_{i}$, $1 \leq i<
j \leq h$. We call $D_{1}$, $D_{2}$, \dots, $D_{h}$ the {\it irreducible components}
of $D$, and such a decomposition is called the {\it irreducible decomposition} of $D$. A
mark sequence $P$ is said to be {\it irreducible} if all the $k$-digraphs $D$ with mark
sequence $P$ are irreducible.

The following result characterizes irreducible $k$-digraphs.

\begin{theorem} If $D$ is a connected $k$-digraph with mark sequence $P =
[p_{i}]_{1}^{n}$, then $D$ is irreducible if and only if, for $t = 1, 2,\dots,n
- 1$,
\begin{equation} \label{3.1.1} 
\sum_{i=1}^{t}p_{i}>kt(t-1)
\end{equation}
and 
\begin{equation} \label{3.1.2} 
\sum_{i=1}^{n}p_{i}=kn(n-1).
\end{equation}
\end{theorem}
\begin{proof}Let $D$ be a connected, irreducible $k$-digraph having mark
sequence $P = [p_{i}]_{1}^{n}$. Condition~(3.1.2) holds, since 
Theorem~2.2
has already established it for any $k$-digraph. Condition (3.1.2) also implies
that for any integer $t<
n$, the $k$-subdigraph $D'$ induced by any set of $t$ vertices has a sum of
marks in $D'$ equal to $kt(t - 1)$. Since $D$ is irreducible, therefore either
there is an arc from at least one of these $t$ vertices to at least one of the
other $n-t$ vertices, or there is exactly one arc from at least one of the other
$n-t$ vertices to at least one vertex in $D'$. Therefore, for $1 \leq t<n-1$,
$$
\sum_{i=1}^{t}p_{i}\geq kt(t-1)+1>kt(t-1).$$

For the converse, suppose that conditions (3.1.1) and (3.1.2) hold. It follows
from Theorem~2.2 that there exists a $k$-digraph with mark sequence $P = [p_{i}%
]_{1}^{n}$. Assume such a $k$-digraph is reducible, and let $D = [D_{1},
D_{2},\dots, D_{h}]$ be the irreducible component decomposition of $D$. Since
there are exactly $k$ arcs from every vertex of $D_{j}$ to each vertex of
$D_{i}$, $1 \leq\ i<
 j \leq h$, $D$ is evidently connected. If $m$ is the number of vertices in
$D_{1}$, then $m<
n$, and $\sum_{i=1}^{m}p_{i}=km(m-1)$, 
which is a contradiction to the given
hypothesis. Hence, $D$ is irreducible.
\end{proof}

We note that a disconnected $k$-digraph is always irreducible, since if $D_{1}$
and $D_{2}$ are the components of $D$, then there are no arcs between vertices
of $D_{1}$ and vertices of $D_{2}$.\medskip

The following result can be easily established.

\begin{theorem}If $D$ is a $k$-digraph with mark sequence $P = [p_{i}%
]_{1}^{n}$, and $\sum_{i=1}^{r}p_{i}=kr(r-1),$\ $\sum_{i=1}^{t}%
p_{i}=kt(t-1),$ and  $\sum_{i=1}^{q}p_{i}>kq(q-1)$, for $r + 1 \leq q \leq
t-1$, $0\leq r<
t \leq n$, then the $k$-subdigraph induced by the vertices $v_{r+1}$, $v_{r+2}%
$, \dots, $v_{t}$ is an irreducible component of $D$ with mark sequence $[p_{i}%
-kr]_{r+1}^{t}$.
\end{theorem}

The mark sequence $P$ is irreducible if $D$ is irreducible, and the irreducible
components of $P$ are the mark sequences of the irreducible components of $D$.
That is, if $D = [D_{1}, D_{2},\dots, D_{h}]$ is the irreducible component
decomposition of a $k$-digraph $D$ with mark sequence $P$, then the irreducible
components $P_{i}$ of $P$ are the mark sequences of the $k$-subdigraphs induced by
the vertices of $D_{i}$, $1 \leq i \leq h$. Theorem~3.2 shows that the
irreducible components of $P$ are determined by the successive values of $k$ for which
\begin{equation} \label{3.1.3} 
\sum_{i=1}^{t}p_{i}=kt(t-1),\quad \quad 
1 \leq t \leq n.
\end{equation}


This is illustrated by the following examples of 2-digraphs. 

\smallskip
(i) Let $P = [1, 3,
9, 12, 15, 20]$. Equation~(3.2.1) is satisfied for $k = 2, 5, 6$. 
Therefore,
the irreducible components of $P$ are $[0]$, $[1, 4, 7]$, $[0]$ in
ascending order. 

\smallskip
(ii)
Let $P = [0, 5, 8, 11, 17, 19]$. Here Equation~(3.2.1) is satisfied for $k = 1,
4, 6$. Therefore, the irreducible components of $P$ are $[0]$, $[1, 4, 7]$ and $[1, 3]$ in
ascending order.
\medskip

A mark sequence is uniquely realizable if it belongs to exactly one $k$-digraph.
The characterization of uniquely realizable score sequences in tournaments is
given by Avery [1], and that of oriented graphs by S.Pirzada [6]. Now, as an
observation, we have the following result.

\begin{theorem} The mark sequence $P$ of a $k$-digraph $D$ is uniquely
realizable if and only if every irreducible component of $P$ is
uniquely realizable.
\end{theorem}

The next result determines which irreducible mark sequences in 2-digraphs are
uniqu\-ely realizable.

\begin{theorem} The only irreducible mark sequences in 2-digraphs that are uniquely
realizable are $[0]$ and $[1, 3]$.
\end{theorem}

\begin{proof} Let $P$ be an irreducible mark sequence, and let $D$ with vertex
set $V$ be a 2-digraph having mark sequence P. Then $D$ is irreducible. Therefore,
$D$ cannot be partitioned into 2-subdigraphs $D_{1}$, $D_{2}$, \dots, $D_{k}$ such
that there are exactly two arcs from every vertex of $D_{\alpha}$ to each
vertex of $D_{\beta}$, $1 \leq\beta<
\alpha\leq k$. First assume $D$ has $n \geq3$ vertices. Let $W = \{w_{1},
w_{2},\dots, w_{r}\}$ and $U = \{u_{1}, u_{2},\dots,u_{s}\}$ respectively
be any two disjoint subsets of $V$ such that $r + s = n$. Since $D$ is irreducible,
(1) there do not exist exactly two arcs from every $w_{i}$ ($1\leq i \leq
 r$) to each $u_{j}$ ($1 \leq\ j \leq s$), and (2) there do not exist
exactly two arcs from every $u_{j}$ ($1 \leq j \leq s$) to each $w_{i}$
($1
\leq i \leq s$). First of all we consider Case~(1), and then Case~(2)
follows by using the same argument as in (1).

\medskip
{\sc Case} (1). There exists at least one vertex, say $w_{1}$, in $W$, and at
least one vertex, say $u_{1}$, in $U$ such that either (a) $w_{1}(1 - 1)u$, or
(b) $w_{1}(0 - 2)u_{1}$, or (c) $w_{1}(1 - 0)u_{1}$, or (d) $w_{1}(0 -
1)u_{1}$, or (e) $w_{1}(0 - 0)u_{1}.$

Assume $w_{i}(2-0)u_{j}$ for each $i$ ($1 \leq i \leq r$) and $j$ ($1 \leq
\ j \leq s$), except for $i = j = 1$.

\medskip
If in $D$, either (a) $w_{1}(1-1)u_{1}$, or (e) $w_{1}(0 - 0)u_{1}$, then
transforming them respectively to $w_{1}(0 - 0)u_{1}$, or $w_{1}(1 -
1)u_{1}$, gives a 2-digraph $D'$ with the same mark sequence. In both cases, $D$
and $D'$ have different number of arcs, and thus are non-isomorphic.

\medskip
(b) Let $w_{1}(0 - 2)u_{1}$. Since there are only six possibilities between
$w_{1}$ and $w_{i}$, therefore, for any other vertex $w_{i}$ in $W$ we have one
of the following cases:

(i) $w_{1}(2 - 0)w_{i}(2 - 0)u_{1}(2 - 0)w_{1}$, (ii) $w_{1}(1 -
1)w_{i}(2 - 0)u_{1}(2 - 0)w_{1}$, (iii) $w_{1}(1 - 0)w_{i}(2 -
0)u_{1}(2 - 0)w_{1}$, (iv) $w_{1}(0 - 1)w_{i}(2 - 0)u_{1}(2 -
0)w_{1}$, (v) $w_{1}(0 - 0)w_{i}(2 - 0)u_{1}(2 - 0)w_{1}$, (vi) $w_{1}%
(0- 2)w_{i}(2 - 0)u_{1}(2 - 0)w_{1}$.

Transforming (i)--(v) respectively to $w_{1}(1 - 0)w_{i}(1 - 0)u_{1}(1 -
0)w_{1}$, $w_{1}(0 - 1)w_{i}(1 - 0)u_{1}(1 - 0)w_{1}$, $w_{1}(0 -
0)w_{i}(1 - 0)u_{1}(1 - 0)w_{1}$, $w_{1}(0 - 2)w_{i}(1 - 0)u_{1}(1 -
0)w_{1}$, $w_{1}(0 - 1)w_{i}(1 - 0)u_{1}(1 - 0)w_{1}$, gives a
2-digraph with the same mark sequence. In all these five cases, $D$ and $D'$
have different number of arcs, and thus are non-isomorphic.

If (vi) occurs in $D$, and also $w_{q}(2 - 0)w_{i}$ for $1 \leq i
<q \leq r$, then the 2-digraph $D$ is reducible with irreducible components
$D_{1}$, $D_{2}$, \dots, $D_{r}$ respectively having vertex sets $V_{1} =
\{u_{1}, u_{2},\dots,u_{s}, w_{1}\}$, $V_{2} = \{w_{2}\}$, $V_{3} =
\{w_{3}\}$, \dots, $V_{k} =\{w_{r}\}$.

Also for any vertex $u_{j}$ in $U$, since there are only six possibilities
between $u_{1}$ and $u_{j}$, we have one of the following cases:

(vii) $w_{1}(0 - 2)u_{1}(0 - 2)u_{j}(0- 2)w_{1}$, (viii) $w_{1}(0 -
2)u_{1}(1 - 1)u_{j}(0 - 2)w_{1}$, (ix) $w_{1}(0 - 2)u_{1}(1 -
0)u_{j}(0 - 2)w_{1}$, (x) $w_{1}(0 - 2)u_{1}(0 - 1)u_{j}(0 - 2)w_{1}%
$, (xi) $w_{1}(0 - 2)u_{1}(0 - 0)u_{j}(0 - 2)w_{1}$, (xii) $w_{1}(0 -
2)u_{1}(2- 0)u_{j}(0 - 2)w_{1}$.

If any one of (vii)--(xi) appears in $D$, then making respectively the
transformations $w_{1}(0-1)u_{1}(0-1)u_{j}(0-1)w_{1}$, $w_{1}%
(0-1)u_{1}(1-0)u_{j}(0-1)w_{1}$, $w_{1}(0-1)u_{1}(2 - 0)u_{j}(0 -
1)w_{1}$, $w_{1}(0 - 1)u_{1}(1 - 1)u_{j}(0 - 1)w_{1}$, $w_{1}(0 -
1)u_{1}(1 - 0)u_{j}(0 - 1)w_{1}$, we get a 2-digraph with the same mark
sequence, but the numbers of arcs in $D$ and $D'$ are different, and thus $D$ and
$D'$ are non-isomorphic.

If (xii) and any of (i)--(v) appear simultaneously, then there exists a
2-digraph $D'$ with the same mark sequence, but $D$ and $D'$ have
different numbers of arcs. Thus, $D$ and $D'$ are non-isomorphic.

If (vi) and (xii) appear simultaneously, and also $w_{q}(2 - 0)w_{i}$ for
all $1 \leq i<
q \leq r$, then $D$ is reducible with the irreducible components $D_{1}$,
$D_{2}$, \dots, $D_{r}$ having vertex sets $V_{1} = \{u_{1}, u_{2},\dots,
u_{s}, w_{1}\}$, $V_{2} = \{w_{2}\}$, $V_{3} = \{w_{3}\}$, \dots, $V_{r} =
\{w_{r}\}$ respectively.

\medskip
(c) Let $w_{1}(1 - 0)u_{1}$. For any vertex $w_{i}$ in $W$, since there are
only six possibilities between $w_{1}$ and $w_{i}$, we have one of the
following cases:

(i) $w_{1}(2 - 0)w_{i}(2 - 0)u_{1}(0 - 1)w_{1}$, (ii) $w_{1}(1 -
1)w_{i}(2 - 0)u_{1}(0 - 1)w_{1}$, (iii) $w_{1}(1 - 0)w_{i}(2 -
0)u_{1}(0 - 1)w_{1}$, (iv) $w_{1}(0 - 1)w_{i}(2 - 0)u_{1}(0 -
1)w_{1}$, (v) $w_{1}(0 - 0)w_{i}(2 - 0)u_{1}(0- 1)w_{1}$, (vi) $w_{1}%
(0 - 2)w_{i} (2 - 0)u_{1}(0 - 1)w_{1}$.

For (i)--(v) making respectively the transformations
$w_{1}(1 - 0)w_{i}(1 - 0)u_{1}(0 - 2)w_{1}$, $w_{1}(0 - 1)w_{i}(1 -
0)u_{1}(0 - 2)w_{1}$, $w_{1}(0 - 1)w_{i}(1 - 0)u_{1}(0 - 2)w_{1}$,
$w_{1}(1 - 1)w_{i}(1 - 0)u_{1}(2 - 0)w_{1}$, $w_{1}(0 - 1)w_{i}(1 -
0)u_{1}(2 - 1)w_{1}$, we obtain a 2-digraph $D'$ with the same mark
sequence, but the numbers of arcs in $D$ and $D'$ are not equal. Thus, $D$ and
$D'$ are non-isomorphic.

Now, for any other vertex $u_{j}$ in $U$, there are only six possibilities
between $u_{1}$ and $u_{j}$, and we have one of the following cases:

(vii) $w_{1}(1 - 0)u_{1}(0 - 2)u_{j}(0 - 2)w_{1}$, (viii) $w_{1}(1 -
0)u_{1}(1 - 1)u_{j}(0 - 2)w_{1}$, (ix) $w_{1}(1 - 0)u_{1}(1 -
0)u_{j}(0 - 2)w_{1}$, (x) $w_{1}(1 - 0)u_{1}(0 - 1)u_{j}(0 - 2)w_{1}%
$, (xi) $w_{1}(1 - 0)u_{1}(0 - 0)u_{j}(0 - 2)w_{1}$, (xii) $w_{1}(1 -
0)u_{1}(2 - 0)u_{j}(0 - 2)w_{1}$.

If any one of (vii)--(xi) appears, then making respectively the transformations
$w_{1}(2-0)u_{1}(0-1)u_{j}(0-1)w_{1}$, $w_{1}(2-0)u_{1}(1-0)u_{j}%
(0-1)w_{1}$, $w_{1}(2- 0)u_{1} (2 - 0)u_{j}(0 - 1)w_{1}$, $w_{1}(2 -
0)u_{1}(1 - 1)u_{j}(0 - 1)w_{1}$, $w_{1}(2 - 0)u_{1}(1 - 0)u_{j}(0 -
1)w_{1}$, we get a 2-digraph $D'$ with the same mark sequence, but $D$ and
$D'$ have different numbers of arcs. Thus, $D$ and $D'$ are non-isomorphic.

If (xii) and one of (i)-(v) appears simultaneously, we once again arrive to
the conclusion that there exists a 2-digraph $D'$ with the mark sequence $P$,
but $D$ and $D'$ are non-isomorphic.

Thus, we are left with the case when (vi) and (xii) appear simultaneously, and
also $w_{q}(2 - 0)w_{i}$ for all $1 \leq i
<q \leq r$. 
But, then $D$ is reducible having the irreducible components $D_{1}%
$, $D_{2}$, \dots, $D_{r}$ with vertex sets $V_{1} = \{u_{1}, u_{2}%
,\dots,u_{s}, w_{1}\}$, $V_{2} = \{w_{2}\}$, \dots, $V_{r} = \{w_{r}\}$ respectively.

\medskip
(d) Let $w_{1}(0- 1)u_{1}$. Since there are only six possibilities between
$w_{1}$ and $w_{i}$, therefore for any other vertex $w_{i}$ in $W$, we have one
of the following cases:

(i) $w_{1}(2 - 1)w_{i}(2 - 0)u_{1}(1 - 0)w_{1}$, (ii) $w_{1}(1 -
1)w_{i}(2 - 0)u_{1}(1 - 0)w_{1}$, (iii) $w_{1}(1 - 0)w_{i}(2 -
0)u_{1}(1 - 0)w_{1}$, (iv) $w_{1}(0 - 1)w_{i}(2 - 0)u_{1}(1 -
0)w_{1}$, (v) $w_{1}(0 - 0)w_{i}(2 - 0)u_{1}(1 - 0)w_{1}$, (vi) $w_{1}%
(0 - 2)w_{i}(2 - 0)u_{1}(1 - 0)w_{1}$.

If any one of (i)--(v) appears, then making respectively the transformations
$w_{1}(1-0)w_{i}(1-0)u_{1}(0- 0)w_{1}$, $w_{1}(0-1)w_{i}(1-0)u_{1}%
(0-0)w_{1}$, $w_{1}(0-0)w_{i}(1 - 0)u_{1}(0 - 0)w_{1}$, $w_{1}(0 -
2)w_{i}(1 - 0)u_{1}(0 - 0)w_{1}$, $w_{1}(0 - 1)w_{i}(1 - 0)u_{1}(0 -
0)w_{1}$, gives a 2-digraph $D'$ with the same mark sequence, but the numbers
of arcs in $D$ and $D'$ are different so that $D$ and $D'$ are non-isomorphic.

If (vi) appears in $D$, and also if $w_{q}(2 - 0)w_{i}$ for all $1 \leq i<q \leq r$, then $D$ becomes reducible.

Now, for any other vertex $u_{j}$ in $U$, there are only six possibilities
between $u_{1}$ and $u_{j}$, and we have one of the following cases:

(vii) $w_{1}(0 - 1)u_{1}(0 - 2)u_{j}(0 - 2)w_{1}$, (viii) $w_{1}(0 -
1)u_{1}(1 - 1)u_{j}(0 - 2)w_{1}$, (ix) $w_{1}(0 - 1)u_{1}(1 -
0)u_{j}(0 - 2)w_{1}$, (x) $w_{1}(0 - 1)u_{1}(0 - 1)u_{j}(0 - 2)w_{1}%
$, (ix) $w_{1}(0 - 1)u_{1}(0 - 0)u_{j}(0 - 2)w_{1}$, (xii) $w_{1}(0 -
1)u_{1}(2 - 0)u_{j}(0 - 2)w_{1}$.

If any one of (vii)--(xi) appears in $D$, then making respectively the transformations
$w_{1}(0 - 0)u_{1}(0 - 1)u_{j}(0 - 1)w_{1}$, $w_{1}(0 - 0)u_{1}(1 -
0)u_{j}(0 - 1)w_{1}$, $w_{1}(0 - 0)u_{1}(2 - 0)u_{j}(0 - 1)w_{1}$,
$w_{1}(0 - 0)u_{1}(0 - 0)u_{j}(0 - 1)w_{1}$, $w_{1}(0-0)u_{1}%
(1-0)u_{j}(0-1)w_{1}$, gives a 2-digraph $D'$ with the same mark
sequence, but the numbers of arcs in $D$ and $D'$ are different so that $D$ is not
isomorphic to $D'$.

If (xii) and any one of (i)--(v) appear simultaneously, then once again there
exists a 2-digraph $D'$ with the same mark sequence, but $D$ and $D'$ have
different numbers of arcs so that $D$ and $D'$ are non-isomorphic.

If (vi) and (xii) appear simultaneously, and also $w_{q}(2 - 0)w_{i}$ for
all $1 \leq i
<q \leq r$, then $D$ is reducible.

Now, let $D$ have exactly two vertices say $u$ and $v$. The only irreducible mark
sequences realizing $D$ are $[2, 2]$, and $[1, 3]$. 
Obviously the sequence $[2, 2]$
has two non-isomorphic realizations namely $u(0 - 0)v$ and $u(1 - 1)v$, and $[1, 3]$
has the unique realization $u(0 - 1)v$. Thus $P = [1, 3]$ is uniquely realizable.

If $D$ has only one vertex, then $P = [0]$, which evidently is uniquely
realizable.
\end{proof}

Combining Theorem~3.3 and Theorem~3.4, we have the following result for 2-digraphs.

\begin{theorem} The mark sequence $P$ of a 2-digraph is uniquely
realizable if and only if every irreducible component of $P$ is of the form $[0]$
or $[1, 3]$.
\end{theorem}

We observe that in the mark sequence $P = [4i-4]_{1}^{n}$ every irreducible
component is $[0]$, and thus $P$ is uniquely realizable. We note that the mark
sequences of tournaments are not uniquely realizable. To see this, consider
the mark sequence $P = [2, 4, 6]$ realizing the tournament $T$. The other
2-digraph $D$ realized by $P$ has vertex set $\{v_{1}, v_{2}, v_{3}\}$ with
$v_{1}(0-0)v_{2}(0-0)v_{3}(2-0)v_{1}$.

However, we observe that a mark sequence of a tournament $T$ is uniquely
realizable if and only if the mark sequence of the double tournament of $T$ is
uniquely realizable.\bigskip

Now, we have the following generalization of Theorem~3.5, and the proof
follows by using arguments as in Theorem~3.5.

\begin{theorem} The mark sequence $P$ of a $k$-digraph is uniquely
realizable if and only if every irreducible component of $P$ is of the form $[0]$
or $[1, 2k-1]$.
\end{theorem}

\section*{Acknowledgements} 
The authors are thankful to the anonymous referee
for his valuable suggestions and for providing an elegant proof of Theorem
2.2, which improved the presentation of the paper.


\begin{thebibliography}{1}

\bibitem{Av} 
P.Avery, {\em Condition for a tournament score sequence to be simple}, J. Graph
Theory {\bf 4} (1980), 157--164.

\bibitem{Av1} 
 P.Avery, {\em Score sequences of oriented graphs}, J.Graph Theory 
{\bf 15} (1991), 251--257.

\bibitem{Ha} 
 F.Harary, R.Z.Norman and D.Cartwright, {\em Structural Models: An Introduction
to the Theory of Directed Graphs}, John Wiley and Sons, New York (1965).

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

\bibitem{Mo} 
J.W.Moon, {\em Topics on Tournaments}, Holt, Rinehart and Winston, New York (1968).

\bibitem{Pi} 
S.Pirzada, {\em Simple score sequences in oriented graphs}, Novi Sad J.
Mathematics {\bf 33} (2003), 25--29.

\bibitem{PN} 
S.Pirzada and T.A.Naikoo, {\em Inequalities for marks in digraphs}, Mathematical
Inequalities and Applications {\bf 9} (2006), 189--198.

\bibitem{Pi2} 
S.Pirzada, {\em On oriented graph scores}, to appear.

\end{thebibliography}
\end{document}