%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   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[10pt,leqno,twoside]{article}

\usepackage{annal-latex}
%%%\usepackage{acta-info}
\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}{\indent Lemma}[section]
\newtheorem{corollary}{\indent Corollary}[section]


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

\newtheorem*{xrem}{\indent Remark}


\begin{document}
\setcounter{page}{1}
\newcommand\balline{\small A. Iv\'anyi}
\newcommand\jobbline{\small Degree sequences of multigraphs}

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

\vspace{.4cm}

\title{DEGREE SEQUENCES OF MULTIGRAPHS}

\author{{\bf Antal Iv\'anyi} (Budapest, Hungary)\\ [1ex]
}



%
\keywords{degree sequence, graphical sequence, $(a,b,n)$-graph, tournament}
%
\mathclass{05C65, 68R10}
%
\compclass{G.2.2 [Graph Theory]: Subtopic: Network problems}

\projsupport{The 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{Let $a, \ b$ and $n$ be integers, $n \geq 1$ and $b \geq a \geq 0$. Let an $(a,b,n)$\textit{-graph} defined as a loopless 
graph $G(a,b,n)$ on $n$ vertices $\{V_1, \ldots, V_n \}$, in which $V_i$ and $V_j$ are connected with at least $a$ and at most 
$b$ (directed or undirected) edges. If $G(a,b,n)$ is directed, then it is called $(a,b,n)$\textit{-digraph} and if it is undirected,  
then it is called $(a,b,n)$\textit{-undigraph}. Landau in 1953 published an algorithm deciding whether a nondecreasing sequence of nonnegative integers is the 
out-degree sequence of a $(1,1,n)$-digraph. Moon in 1963 published a similar condition for $(0,b,n)$-digraphs, and in 2009 
Iv\'anyi did for $(a,b,n)$-digraphs. Havel in 1955, Erd\H os and Gallai in 1960   
proposed an algorithm to decide the same question for  $(0,1,n)$\textit{-undigraphs}. Their theorem were extended 
to $(0,b,n)$-undigraphs by Chungphaisan in 1974. In 2011 \"Ozkan \cite{Ozkan2011} proved a stronger version. The aim 
of this paper is to summarize and extend the known results and to propose quicker algorithms than the known ones.}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction\label{sec-intro}}
One of the classical problems of the graph theory is the characterization of the set of degree sequences of  
different graph classes.

Let $a, \ b$ and $n$ be integers, $n \geq 1$ and $b \geq a \geq 0$. Let $(a,b,n)$\textit{-graphs} defined 
as loopless graphs on $n$ vertices, in which different vertices are connected with at least $a$ and at most 
$b$ edges. For the clarity we call directed $(a,b,n)$-graphs as $(a,b,n)$\textit{-digraphs}  
and undirected $(a,b,n)$-graphs as $(a,b,n)$\textit{-undigraphs}.

Our aim is to investigate the conditions and algorithms which decide whether a monotone sequence  
$s = (s_1, \ldots, s_n)$ of integers is the degree sequence of an $(a,b,n)$-undigraph or the out-degree sequence of an  
$(a,b,n)$-digraph. 

The first results belong to Landau \cite{Landau1953}, who published in 1953 a necessary and sufficient condition for 
$(1,1,n)$-digraphs, and Havel \cite{Havel1955}, who gave a necessary and sufficient condition in 1955 for $(0,1,n)$-undigraphs. 
The later result was independently reproved in 1962 by Hakimi \cite{Hakimi1962}.

The conditions for $(b,b,n)$-digraphs were given in 1962 by Moon \cite{Moon1963} and for $(0,b,n)$-undigraphs by 
Chungphaisan \cite{Chungphaisan1974} in 1974.
The conditions for $(a,b,n)$-digraphs were published in 2009 \cite{Ivanyi2009,Ivanyi2010}. 

In this paper we summarize the results of testing of potential degree sequences of $(a,b,n)$-graphs including the analysis 
of their efficiency. The structure of the paper is as follows. After the introductory Section \ref{sec-intro} in Section 
\ref{sec-abdi} we present the known results connected with directed graphs. Section \ref{sec-01undi} contains the algorithms 
proposed to test the potential degree sequences of $(0,1,n)$-undigraphs, while Section \ref{sec-0bundi} the results connected with 
$(0,b,n)$-undigraphs. In Section \ref{sec-abundi} the results on $(a,b,n)$-undigraphs are presented while Section \ref{sec-summary} 
contains the summary of the results.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conditions and algorithms for $(a,b,n)$-digraphs \label{sec-abdi}}
Let $l, \ m$ and $u$ be nonnegative integers, further $l \leq u$ and $m \geq 1$.  The sequence $s = (s_1,\ldots,s_m)$ of integers  
is called $(l,u,m)$\textit{-bounded}, if $l \leq s_i \leq u$ hold for all $1 \leq i \leq m$ indices.   
An $s = (s_1,\ldots,s_m)$ $(l,u,m)$-bounded sequence is called $(l,u,m)$\textit{-regular}, if    
$u \geq s_1 \geq \cdots \geq s_m \geq l$ or $l \leq s_1 \leq \cdots \leq s_m \leq u$ (according to references we use 
nondecreasing sequences for digraphs and nonincreasing ones for undigraphs). An $(l,u,m)$-regular sequences is 
called $(l,u,m)$-\textit{digraphic,} if there exists a $(l,u,m)$-digraph, having $s$ as its out-degree sequence. 
In a similar manner an $(l,u,m)$-regular sequence  
is called $(l,u,m)$-\textit{undigraphic,} if there exists a $(l,u,m)$-undigraph, having $s$ as its degree sequence 
\cite{GrossY2004,Weisstein2011DS,Weisstein2011GS}.

The first testing theorem for $(1,1,n)$-digraphs belongs to Landau.

\begin{theorem} \emph{(Landau \cite{Landau1953})} A sequence $(s_1, \ldots, s_n)$ satisfying 
$0 \leq s_1 \leq \cdots \leq s_n$ is the out-degree sequence of some $(1,1,n)$-digraph if and only if
\begin{equation}
\sum_{i = 1}^k s_i \geq \binom{k}{2} \quad \textit{for} \ \ \ 1 \leq k \leq n,\label{equation-1}
\end{equation}
with equality when $k = n$.
\end{theorem} 

In 1963 Moon proved the following generalization of the Landau's theorem.

\begin{theorem} \emph{(Moon \cite{Moon1963})} A sequence\label{th-bbndi} $(s_1, \ldots, s_n)$ satisfying 
$0 \leq s_1 \leq \cdots \leq s_n$ is the out-degree sequence of some $(b,b,n)$-digraph if and only if 
\begin{equation}
\sum_{i = 1}^k s_i \geq b\binom{k}{2}, \ 1 \leq k \leq n,\label{equation-2}
\end{equation}
\textit{with equality when} $k = n$. 
\end{theorem}


In 2009 Iv\'anyi gave the following necessary and sufficient condition for $(a,b,n)$-digraphs. Let the loss function 
$L_n$ defined as $L_0 = 0$ and 
$$L_k = \max \left (L_{k-1},b\binom{k}{2} - \sum _{i=1}^k s_i \right)  \quad \mbox{for}\ 1 \leq k \leq n.$$

\begin{theorem} \emph{(Iv\'anyi \cite{Ivanyi2009,IvanyiP2011})} An $(a,b,n)$-regular nondecreasing sequence\label{th-abndi} 
$s = (s_1, \ldots, s_n)$ is the out-degree sequence of some $(a,b,n)$-digraph if and only if
\[ a\binom{k}{2} \leq \sum_{i = 1}^k s_i \leq b\binom{n}{2} - L_k - (n - k)s_i \quad (1 \leq k \leq n). \]
\end{theorem}

\begin{proof} See \cite{Ivanyi2009}.
\end{proof}

Landau's theorem is the special case $a = b = 1$ of Theorem \ref{th-abndi}, while Moon's theorem 
is the special case $a = b$.

The following algorithm is based on Theorem \ref{th-abndi}. In the programs of this paper the pseodocode conventions 
described in \cite{CormenL2009} are used.

\textit{Input}. $n$: the length of $s$ $(n \geq 1)$; \\
\textit{a}: minimal number of the arcs between two vertices;\\
\textit{b}: maximal number of the arcs between two vertices;\\
\textbf{s} $= (s_1, \ldots, s_n)$: a nondecreasing sequence of integers. 


\textit{Output}. One of the following messages: \\
$i$"-th score is too small"; \\
$i$"-th score is too large"; \\
"the sequence is ("$a$","$b$","$n$")-digraphical".

\textit{Working variable}. $i$: cycle variable;\\
$B = (B_0,\ldots,B_n)$: the sequence of the binomial coefficients$\binom{n}{k}$ for $k = 0,\ldots,n$; \\
$L = (L_0,\ldots,L_n)$: the sequence of the values of the loss function; \\
$H = (H_0,\ldots,H_n)$: the sequence of the sums of the $i$ smallest elements of $s$.

\bigskip
\noindent \textsc{Digraph-Test}$(n,a,b,s)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill 
\hspace{-7mm}\textbf{01} $L_0 \leftarrow 0$  \` \textbf{//} lines 01--03: initialization \\ 
\hspace{-7mm}\textbf{02} $H_0 \leftarrow 0$ \\
\hspace{-7mm}\textbf{03} $B_0 \leftarrow 0$ \\
\hspace{-7mm}\textbf{04} \textbf{for} \= $i \leftarrow 1$ \textbf{to} $n$   \` \textbf{//} lines 04--07: computation of $H_i, \ B_i, \ L_i$ \\
\hspace{-7mm}\textbf{05}              \> $H_i \leftarrow H_{i - 1} + s_i$ \\
\hspace{-7mm}\textbf{06}              \> $B_i \leftarrow B_{i - 1} + i - 1$  \\
\hspace{-7mm}\textbf{07}              \> $L_i \leftarrow \max(L_{i - 1}, \ bB_i - S_i)$ \\
\hspace{-7mm}\textbf{08}              \> \textbf{if} \= $H_i < aB_i$    \` \textbf{//} lines 08--09: exclusion of small $s$'s  \\ 
\hspace{-7mm}\textbf{09}              \>             \> \textbf{return} $i$"-th score is too small" \\
\hspace{-7mm}\textbf{10}              \> \textbf{if} \= $H_i > bB_n - L_i - s_i(n - i)$ \` \textbf{//} lines 10--11: exclusion of large $s$'  \\
\hspace{-7mm}\textbf{11}              \>             \> \textbf{return} $i$"-th score is too large" \\
\hspace{-7mm}\textbf{12} \textbf{return} \textit{s} "is digraphical" \\
\end{tabbing}

It is easy to show that the running time of \textsc{Digraph-Test} changes between the best $\Theta(1)$ and the worst $\Theta(n)$. 

Using formula (22) of \cite{IvanyiLMS2011Acta} we have that the number $Q(a,b,n)$ of $(a,b,n)$-diregular sequences is 
\begin{equation}
Q(a,b,n) = \binom{b(n - 1) + n}{n}. \label{eq-Qabn}
\end{equation}

Table \ref{tab-di-reg-graph} contains $Q(a,b,n)$ and the number $D(a,b,n)$ of $(a,b,n)$-digraphical 
sequences for $a = b = 1$ (that is for individual tennis tournaments), for $a = b = 2$ (that is for individual chess tournaments),  
and for $a = 2, \ b = 3$ (that is for a \textit{complete} 
\cite{IvanyiLMS2011Acta} football tournament for $n = 1, \ \ldots, \ 11$ vertices.

\begin{table}[!ht]
\begin{centering}
\begin{small}
$\begin{array}{||r||r|r|r|r|r|r||} \hline \hline
  n & Q(1,1,n)& D(1,1,n)& Q(2,2,n) & D(2,2,n)& Q(2,3,n) & D(2,3,n) \\ \hline
1	&	1	&	1	&	1	&	1	&	1	&	1	\\ \hline
2	&	3	&	1	&	6	&	2	&	10	&	4	\\ \hline
3	&	10	&	2	&	35	&	5	&	84	&	27	\\ \hline
4	&	35	&	4	&	210	&	16	&	715	&	208	\\ \hline
5	&	126	&	9	&	1 287	&	59	&	6 188	&	1 709	\\ \hline
6	&	462	&	22	&	8 008	&	247	&	54 264	&	14 513	\\ \hline
7	&	1 716	&	59	&	50 388	&	1 111	&	480 700	&	125 658	\\ \hline
8	&	6 435	&	167	&	319 770	&	5 302	&	4 292 145	&	1 102 081	\\ \hline
9	&	24 310	&	490	&	2 042 975	&	26 376	&	38 567 100	&	9 756 399	\\ \hline
10	&	92 378	&	1 486	&	13 123 110	&	135 670	&	348 330 136	&	86 989 413	\\ \hline
11	&	352 716	&	4 639	&	84 672 315	&	716 542	&	3 159 461 968	&	780 019 710	\\ \hline
12	&	1 352 078	&	14 805	&	548 354 040	&	3 868 142	&	28 760 021 745	&	7 026 788 895	\\ \hline
13	&	5 200 300	&	48 107	&	3 562 467 300	&	21 265 884	&		&		\\ \hline
14	&	20 058 300	&	158 808	&	23 206 929 840	&	118 741 369	&		&		\\ \hline \hline
\end{array}$
\end{small}
\caption{The number of $(a,b,n)$-diregular and $(a,b,n)$-digraphical sequences for $a = b = 1$, $a = b = 2$,  
$a = 2$ and $b = 3,$ and $n = 1, \ \ldots, \ 14$ vertices.\label{tab-di-reg-graph}}
\end{centering}
\end{table}

Tables \ref{tab-degreetest11a} and \ref{tab-degreetest11b}  characterize the efficiency of the rounds of 
\textsc{Digraph-Test} showing the ratio of the filtered and investigated sequences in the $i$-th round  for $a = b = 1$, 
that is for individual tennis tournaments for $n = 1, \ \ldots, \ 14$ vertices and for the rounds $i = 1, \ \ldots \ 7,$ 
resp. $i = 8, \ \ldots, \ 14.$

\begin{table}[!ht]
\centering
\begin{small}
$\begin{array}{||r|r|r|r|r|r|r|r||} \hline \hline
n/i &   1   &   2   &    3  & 4     &   5   &   6   &   7   \\ \hline
1	&	0	&	    &		&		&		&		&				\\ \hline
2	&	1	&	1   &		&		&		&		&						\\ \hline
3	&	1	&   5	&	2	&		&		&		&					\\ \hline
4	&	5	&15	    &	6	&	5	&		&		&						\\ \hline
5	&	6	&50	    &	27	&	21	&	13	&		&					\\ \hline
6	&	28	&174    &	75	&	73	&	55	&	35	&						\\ \hline
7	&36	    &574    &	300	&	276	&	209	&	160	&	102					\\ \hline
8	&165	&2 112  &	854	&950	&	763	&	637	&	478			\\ \hline
9	& 220   &7 260  &3 312	&3 396	&2 817	&2 398	&1 961			\\ \hline
10	&1 001  &27 390 &10 230	&11 487	&10 006	&8 994	&7 659			\\ \hline
11	&1365   &98 384 &38 115	&41 800	&35 277	&32 663	&29 216				\\ \hline
12	& 6188  &375921 &125411	&142296	&124839	&118882	&108638				\\ \hline
13	& 8568  &1395394&467649	&521885	&436744	&420695	&398979				\\ \hline
14	&38760  &5371660&1636726&1817088&1549067&1507705&1446577  	\\ \hline \hline
\end{array} $
\end{small}
\caption{The number of the filtered non $(1,1,n)$-digraphical sequences in the $i$-th round of \textsc{Digraph-Test}
for $n = 1, \ \ldots, \ 14$ and $i = 1, \ \ldots, \ 7$. \label{tab-degreetest11a}}
\end{table}

\begin{table}[!ht]
\centering
\begin{small}
$\begin{array}{||r|r|r|r|r|r|r|r||} \hline \hline
 n/i&   8   &   9   & 10    & 11    & 12    &  13   &  14 \\ \hline
8	&	309	&		&		&		&		&		&		\\ \hline
9	& 1 495	&	961	&		&		&		&		&		\\ \hline
10	&6 283	&4 786	&3 056	&		&		&		&		\\ \hline
11	&25 101	&20 603	&15 614	&9 939	&		&		&		\\ \hline
12	& 97930	&83956	&68564	&51781	& 32867	&		&		\\ \hline
13	&369968	&332660	&284099	&231195	&174209	&110148	&		\\ \hline
14	&1381068&1279513&1142585&972793	&789234	&593114	& 373602	\\ \hline \hline
\end{array} $
\end{small}
\caption{The number of the filtered non $(0,1,n)$-digraphical sequences in the $i$-th round of \textsc{Digraph-Test}
for $n = 8, \ \ldots, \ 14$ and $i = 8, \ \ldots, \ 14.$ \label{tab-degreetest11b}}
\end{table}

Tables \ref{tab-degreetest22a} and \ref{tab-degreetest22b} characterize the efficiency of the rounds of 
\textsc{Digraph-Test} showing the number of the filtered and investigated non $(2,2,n)$-graphical sequences (that is 
for a chess tournaments) for $n = 1, \ \ldots, \ 14$ vertices and for $i = 1, \ \ldots, 7,$ resp. for $i = 8, \ \ldots, \ 14.$ 

\begin{table}[!ht]
\centering
\begin{small}
$\begin{array}{||r||r|r|r|r|r|r|r||} \hline \hline
n/i &   1   &   2     &  3      &   4    & 5        &  6     &  \\ \hline
1	&	0	&		  &		    &		 &		    &		 & 		\\ \hline
2	&	1	&	3	  &		    &		 &		    &		 & 				\\ \hline
3	&	4	&	16	  &	10	    &	     &		    &		 & 			\\ \hline
4	&	15	&	83	  &	58	    &	38	 &		    &		 & 				\\ \hline
5	&	56	&	440	  &	330	    &	241	 &	161	    &		 & 				\\ \hline
6	&	210	&	2402  &	1825	&1458	 &	1119	&	747	 & 				\\ \hline
7	&	792	&	13538 &	10194	&8498	 &	7125	&5480	 & 			\\ \hline
8	&3003	&	78696 &	57078	&48872	 &	43461	&36597	 & 			\\ \hline
9	&11440	&	470184&	325920	&277644	 &	258475	&231593	 & 			\\ \hline
10	&43758	&2874080  &	1891989	&1585782 &	1506392	&1418825 & 			\\ \hline
11	&167960	&17889443 &11232210	&9100652 &	8715762	&8482480 & 		\\ \hline \hline
\end{array} $
\end{small}
\caption{The number of the filtered non $(2,2,n)$-digraphical sequences in the $i$-th round of \textsc{Digraph-Test}
for $n = 1, \ldots, 11$ vertices and $i = 1, \ldots, 6.$ \label{tab-degreetest22a}}
\end{table}

\begin{table}[!ht]
\centering
\begin{small}
$\begin{array}{||r||r|r|r|r|r||} \hline \hline
n/i &   7     &     8   &   9       &   10      &   11    \\ \hline
7	&  3650	  & 		&		    &		    &		  \\ \hline
8	&	28160 &	18601	&		    &		    &		  \\ \hline
9	&  194715 &	148944	&	97684	&		    &		  \\ \hline
10	& 1272721 &	1061218	&	807032	&	525643	&		   \\ \hline
11	& 8011380 &	7120660	&	5894122	&	4456457	&	2884647	\\ \hline \hline
\end{array} $
\end{small}
\caption{The number of the filtered non $(2,2,n)$-digraphical sequences in the $i$-th round of \textsc{Digraph-Test}
$n = 7,\ldots,11$ vertices and $i = 7, \ldots, 11.$\label{tab-degreetest22b}}
\end{table}
 
Tables \ref{tab-degreetest23an} and \ref{tab-degreetest23bn}contain the number of filtered in the $i$-th round of non 
$(2,3,n)$-graphical sequences, when \textsc{Degree-Test} tested all $(2,3,n)$-regular sequences for  
$i = 1, \ldots, 6$-th resp. $i = 7, \ldots, 12$ and $n = 1, \ \ldots, \ 11$ vertices We remark, that $a = 2$ and 
$b = 3$ are characteristic for Davis Cup tennis tournaments. 

 \begin{table}[!ht]
\centering
\begin{small}
$\begin{array}{||r||r|r|r|r|r|r||} \hline \hline
n/i &   1     &   2       & 3          & 4         &     5      &  6  \\ \hline
1	&	0	  &		      &		       &	       &		    &		\\ \hline
2	&	3	  &	3	      &		       &	       &		    &			\\ \hline
3	&	10	  &	31	      &	16	       &	       &		    &			\\ \hline
4	&	70	  &	205    	  &	150	       &	82	   &		    &			\\ \hline
5	&	252	  &	1533	  &	1235	   &	957	   &	502	    &				\\ \hline
6	&1716	  &	11082	  &	9088	   &	7930   &	6555	&	3380		\\ \hline
7	&6435	  &	84865	  &	69441	   &	64368  &	57655	&	47811			\\ \hline
8	&43758	  &	671099	  &	507199	   &	494226 &	486820	&	436009			\\ \hline
9	&167960	  &	5488821	  &	3931096	   &3751501    &	3890421	&	3828202	 		\\ \hline
10	&1144066  &	46495034  &	30199434   &28218140   &30349772	&	31590048	\\ \hline
11	&4457400  &	401403728 &	244025820  &214372994  &232279669	&	253892909		\\ \hline
12	&30421755 &	3543412391&	1995894197 &1645568584 &1765504146	&	1988106381		\\ \hline \hline
\end{array} $
\end{small}
\caption{The number of the filtered non $(2,3,n)$-digraphical sequences in the $i$-th $(i = 1, \ldots, 6)$ round 
of \textsc{Digraph-Test} for $n = 1, \ \ldots, \ 11$ vertices.\label{tab-degreetest23an}}
\end{table}

\begin{table}[!ht]
\centering
\begin{small}
$\begin{array}{||r||r|r|r|r|r|r||} \hline \hline
n/i &   7       &  8            &   9           &  10           & 11            & 12 \\ \hline
7	&  24467	&		        &		        &		        &		        &		\\ \hline
8	&365510	    &	185443	    &		        &		        &		        &		\\ \hline
9	&3409023	&	2887763	    &	1455914	    &		        &		        &		\\ \hline
10	&30871440	&	27322172	&	23404704	&	11745913	&		        &		\\ \hline
11	&262074711	&	253295635	&	223318920	&	193530773	&	96789699	&		\\ \hline
12	&2164167153	&	2200747000	&	2107880874	&	1854248627	&	1626229074	&	811052668	\\ \hline \hline
\end{array} $
\end{small}
\caption{The number of the filtered non $(2,3,n)$-digraphical sequences in the $i$-th $(i = 7, \ldots, 12)$ round 
of \textsc{Digraph-Test} for $n = 7, \ \ldots, \ 11$ vertices.\label{tab-degreetest23bn}}
\end{table}

The values $Q(a,b,n)$ are computed using \eqref{eq-Qabn}, the values of $D(1,1,n)$ in Table \ref{tab-di-reg-graph} 
are taken from \cite{PecsySz2000}, while the values of Tables \ref{tab-degreetest22a}, \ref{tab-degreetest22b},  
\ref{tab-degreetest23an} and \ref{tab-degreetest23bn} were determined by \textsc{Digraph-Test-Enumerative} 
(the enumerative version of \textsc{Digraphh-Test}).
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conditions and algorithms for $(0,1,n)$-undigraphs \label{sec-01undi}}
Our aim is to find quick algorithms which decide whether a given regular sequence is graphical or not. 
The classical algorithms are based on the theorems Havel \cite{Havel1955} and Hakimi \cite{Hakimi1962}, resp. Erd\H os and Gallai \cite{ErdosG1960}. 
In worst case the running time of these algorithms is $\Theta(n^2)$. It is worth to remark that Erd\H os-Gallai algorithm 
only tests the input sequences while the Havel-Hakimi algorithm produces also a corresponding graph 
(if the input sequence is graphical). Tripathi, Vijay and West \cite{TripathiVW2010} 
gave a constructive proof of Erd\H os-Gallai theorem in 2010. 

In 2011 in the paper \cite{IvanyiLMS2011Acta} we presented quicker algorithms HHZ (zerofree Havel-Hakimi), HHP (parity checking 
Havel-Hakimi), HHQ (quick Havel-Hakimi), EGS (shortened Erd\H os-Gallai), EGL (linear Erd\H os-Gallai), and  
EGJ (jumping Erd\H os-Gallai). 

In this section we present the classical Havel-Hakimi and Erd\H os-Gallai algorithms, further HHL, the linear version 
of the Havel-Hakimi algorithm.

We remark that the testing of $(0,1,n)$-regular sequences is an important subproblem when we try to answer the question 
on the complexity of the testing of potential football sequences \cite[Research problem 2.3.1]{Frank2011}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Havel-Hakimi algorithm (HH)\label{subsec-HH}}
If $n = 1$, then there exists one $(0,1,n)$-graphical sequence: $(0).$ If $n \geq 2,$ 
then the following Havel-Hakimi theorem 
gives a necessary and sufficient condition.
\begin{theorem}{\emph{(Havel, Hakimi \cite{Hakimi1962, Havel1955})}\label{th-HH}}
Let $n \geq 2$. An $n$-regular sequence $s=(s_1,\ldots,s_n)$ is graphical if and only if the sequence 
$s'=(s_2-1, s_3-1,\ldots,s_{s_1}-1,s_{s_1+1}-1,s_{s_1+2},\ldots,s_{n-1},s_n )$ sequence is $(n - 1)$-graphical.
\end{theorem}

\begin{proof} See \cite{Hakimi1962, Havel1955}.
\end{proof}

The algorithm \textsc{Havel-Hakimi} is based on Theorem \ref{th-HH}. In this and the following algorithms $L$ 
is a logical variable: if the investigated sequence is graphical, then $L = 1,$ otherwise $L = 0.$ 

\textit{Input.} $n$: the length of the sequence $s$ $(n \geq 2)$; \\
$s = (s_1,\ldots,s_n)$: the investigated $n$-regular sequence.

\textit{Output.} $L$: logical variable.

\textit{Working variable.} $i$: cycle variables.

\bigskip
\noindent \textsc{Havel-Hakimi}$(n, s, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= x\=x\=x\=x\=x\=x\=x\=x \+ \kill
\hspace{-7mm}01 $L = 0$ \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n - 1$  \` \textbf{//} line 02--07: test of the elements of $s$\\
\hspace{-7mm}03              \> \textbf{if} \= $s_{s_i + i} == 0$  \` \textbf{//} lines 02--03: $s$ is not undigraphical \\
\hspace{-7mm}04              \>             \> \textbf{return} $L$ \\
\hspace{-7mm}05              \> \textbf{for} \= $j = i + 1$ \textbf{to} $s_i + i$ \\
\hspace{-7mm}06              \>               \> $s_j = s_j - 1$ \\ 
\hspace{-7mm}07              \> sort \= $(s_{i+1},\ldots,s_n)$ in decreasing order \\
\hspace{-7mm}08  $L = 1$                \` \textbf{//} lines 08--09: $s$ is undigraphical \\
\hspace{-7mm}09  \textbf{return} $L$
\end{tabbing}

\subsection{Erd\H os-Gallai algorithm (EG)\label{subsec-EG}}
Let the elements $s_1, \ \ldots, s_n$ of the sequence $s$ called \textit{the head} of $s$ belonging to $s_i$, and let 
the remaining elements called \textit{the tail} of $s$ belonging to $s_i$.

Paul Erd\H os and Tibor Gallai in 1960 published the following necessary and sufficient condition.

\begin{theorem}{\emph{(Erd\H os, Gallai \cite{ErdosG1960})}\label{th-EG}}
Let $n \geq 1$. An $s=(s_1, \ldots, s_n)$ $(0,1,n)$-regular sequence is $(0,1,n)$-graphical if and only if 
\begin{equation}
\sum _{i=1}^n s_i \quad  \textit{is even}
\label{eq-EG0} 
\end{equation}
and
\begin{equation}\label{eq-EG1} 
\sum_{i=1}^j s_i - j(j-1) \leq \sum _{k = j  + 1}^n \min(j, s_k) \quad (j=1, \ldots, n-1). 
\end{equation}
\end{theorem}

\begin{proof}
See \cite{Choudum1986,ErdosG1960,TripathiVW2010}.
\end{proof}

The following algorithm is based on Theorem \cite{ErdosG1960}.

\textit{Input.} $n$: the length of $s$; \\
$s = (s_1,\ldots,s_n)$: the investigated $n$-regular sequence.

\textit{Output.} $L$: logical variable.

\textit{Working variable}. $i$: cycle variable; \\
$R$: estimated capacity of the actual tail.

\medskip
\noindent \textsc{Erd\H os-Gallai}$(n,s,L)$
\vspace{-2mm}
\begin{tabbing}
199 \= x\=x\=x\=x\=x\=x\=x\=x \+ \kill
\hspace{-7mm}01 $L = 0$                              \` \textbf{//} line 01: setting of the probable value \\
\hspace{-7mm}02 $H_1 = s_1$                              \` \textbf{//} line 02: computing of $H_1$ \\
\hspace{-7mm}03 \textbf{for} \= $i = 2$ \textbf{to} $n$ \` \textbf{//} lines 02--03: computing of the further $H_i$'s\\
\hspace{-7mm}04              \> $H_i = H_{i-1} + s_i$\\
\hspace{-7mm}05 \textbf{if} \= $H_n$ \textit{is odd} \`   \textbf{//} lines 04--07: test of the parity\\
\hspace{-7mm}06             \> \textbf{return} $L$\\
\hspace{-7mm}07 \textbf{for} $i = 1$ \= \textbf{to} $n - 1$ \` \textbf{//} line 07--15: test of $s$ \\
\hspace{-7mm}08                    \> $R = 0$               \` \textbf{//} line 08: initialization \\
\hspace{-7mm}09                    \> \textbf{for} \= $k=j+1$ \textbf{to} $n$ \` \textbf{//} lines 09--10: tail capacity\\
\hspace{-7mm}10                    \>              \>  $R = R + \min(j, s_k)$\\
\hspace{-7mm}11                    \> \textbf{if} \= $H_j - j (j-1) > R$ \` \textbf{//} line 11: test of $s$\\
\hspace{-7mm}12                    \>             \>  \textbf{return} $L$  \` \textbf{//} line 12: $s$ is non graphical\\
\hspace{-7mm}13 $L = 1$            \` \textbf{//}  lines 13--14: $s$ is graphical \\
\hspace{-7mm}14 \textbf{return} $L$\\
\end{tabbing}  

Table \ref{tab-undi-reg-graph} contains the number of $(a,b,n)$-undiregular and $(a,b,n)$-undigraphical sequences 
for $a = 0$ and $ b = 1$, $a = 0$ and $b = 2$,  $a = 2$ and $b = 5$ and $n = 1, \ \ldots, \ 11$.

\begin{table}[!ht]
\begin{centering}
\begin{small}
$\begin{array}{||r||r|r|r|r|r|r||} \hline \hline
n	&	R(0,1,n)&G(0,1,n) &	R(0,2,n)   & G(0,2,n)  &	R(2,3,n)	&	G(2,3,n)	\\ \hline 
1	&	1	    &	1	  &	1	       &	1      &	1	        &	1	\\ \hline 
2	&	3	    &	2	  &	6	       &	3      &	10	        &	4	\\ \hline 
3	&	10	    &	4	  &	35	       &	10     &	84	        &	23	\\ \hline 
4	&	35	    &	11	  &	210	       &	52     &	715	        &	189	\\ \hline 
5	&	126	    &	31	  &1 287	   &	283	   &	6 188	    &	1 582	\\ \hline 
6	&	462	    &	102	  &8 008	   &	1 706  &	54 264	    &	13 583	\\ \hline 
7	&	1 716	&342	  &	50 388	   &10 436	   &	480 700	    &	122 345	\\ \hline 
8	&	6 435	&1 213	  &	319 770    &65 370	   &	4 292 145	&	1 092 573	\\ \hline 
9	&	24 310	&4 361	  &	2 042 975  &413 111	   &	38 567 100	&	9 816 598	\\ \hline 
10	&	92 378	&16 016	  &	13 123 110 &2 633 537  &	348 330 136	&	88 680 716	\\ \hline 
11	&	352 716	&59 348	  &	84 672 315 &16 882 153 & 3 159 461 968	&	804 480 107	\\ \hline \hline
\end{array}$
\end{small}
\caption{The number of $(a,b,n)$-undiregular and $(a,b,n)$-undigraphical sequences for $a = 0$ and $ b = 1$, $a = 0$ and 
$b = 2$,  $a = 2$ and $b = 3$ and for $n = 1,\ldots,11$ vertices.\label{tab-undi-reg-graph}}
\end{centering}
\end{table}

Table \ref{tab-undi-test01n} presents the number of the  filtered non $(0,1,n)$-graphical sequences in the $i$-th round of HHT  
for $n = 1, \ldots, 11$ vertices.


\begin{table}[!ht]
\centering
\begin{small}
$\begin{array}{||r||r|r|r|r|r|r|r|r|r|r|r||} \hline \hline
n/i & 1     &   2   & 3       & 4   & 5     &  6  &   7   &  8    &   9   &  10 & 11\\ \hline
  1	&	0	&       &         &      &      &     &       &       &       &     &   \\ \hline 
2	&	1	&	0	&         &      &      &     &       &       &       &     &\\ \hline 
3	&	6	&	0	&	0	  &      &      &     &       &       &       &     &\\\hline 
4	&	22	&	2	&	0	  &	0	 &      &     &       &       &       &     &\\ \hline 
5	&	85	&	8	&	2	  &	0	 &0	    &     &       &       &       &     &\\ \hline 
6	&	311	&	35	&	12	  &	2	 &0	    &	0  &       &       &       &     &\\ \hline 
7	&1169	&	128	&	58	  &	17	 &2	    &	0  &	0  &       &       &     &	\\ \hline 
8	&4369	&	488	&	239	  &	100	 &24    &	2  &	0  &	0  &       &     &\\ \hline 
9	&16524	&1805	&	942	  &	471	 &173   &32    &    2  &	0  &	0  &      &     \\ \hline 
10	&62650	&6800	&3601	  &2021	 &956   &289   &	43 &	2  &0	   &0	 & \\ \hline 
11	&239008	&25571	&13677	  &8147	 &4561	 &1877 &470	   &	55 &2	   &0	 &	0	\\ \hline \hline
\end{array}$
\end{small}
\caption{The number of the filtered non $(0,1,n)$-graphical sequences in the $i$-th round of HH  
for $n = 1, \ \ldots, \ 11$ vertices and $i = 1, \ \ldots, \ 10$.\label{tab-undi-test01n}}
\end{table}

Table \ref{tab-undi-test01g} presents the number of the  filtered graphical sequences in the $i$-th round of HHT  
for $a = 0, \ b = 1,$ $n = 1, \ \ldots, \ 11$ vertices and for $i = 1, \ldots, 11.$

\begin{table}[!ht]
\centering
\begin{small}
$\begin{array}{||r||r|r|r|r|r|r|r|r|r|r|r||} \hline \hline
  n/i   & 1    &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10 & 11\\ \hline
1	&	0	&		&		&		&		&		&		&		&		&		&		\\ \hline  
2	&	1	&	0	&		&		&		&		&		&		&		&		&		\\ \hline  
3	&	1	&	2	&	0	&		&		&		&		&		&		&		&		\\ \hline 
4	&	1	&	8	&	1	&	0	&		&		&		&		&		&		&		\\ \hline 
5	&	1	&	16	&	12	&	1	&	0	&		&		&		&		&		&		\\ \hline 
6	&	1	&	29	&	48	&	22	&	1	&	0	&		&		&		&		&		\\ \hline 
7	&	1	&	47	&	130	&	127	&	35	&	1	&	0	&		&		&		&		\\ \hline 
8	&	1	&	72	&	306	&	488	&	290	&	54	&	1	&	0	&		&		&		\\ \hline 
9	&	1	&	104	&	618	&	1492	&	1475	&	591	&	78	&	1	&	0	&		&		\\ \hline 
10	&	1	&	145	&	1158	&	3863	&	5757	&	3868	&	1112	&	110	&	1	&	0	&		\\ \hline 
11	&	1	&	195	&	1998	&	8890	&	18440	&	18662	&	9053	&	1958	&	149	&	1	&	0 
\\ \hline \hline
\end{array}$
\end{small}
\caption{The number of the filtered $(0,1,n)$-graphical sequences in the $i$-th round of HH 
for $n = 1, \ \ldots, \ 11$ vertices and $i = 1, \ \ldots, \ 10$.\label{tab-undi-test01g}}
\end{table}

Let $n_i(a,b,n,\emph{A}),$ resp. $m_i(a,b,n,\emph{A})$ denote the number of filtered by algorithm A  non $(a,b,n)$-graphical, 
resp. $(a,b,n)$-graphical sequences in the $i$th round of the testing of all $(a,b,n)$-regular sequences, further let  

\begin{equation}
N = \sum _{i=1}^{n-1} n_i \quad   \emph{\mbox{�s}} \quad  M = \sum _{i = 1}^{n-1} m_i, \label{eq-NM}
\end{equation} 
\begin{equation}
X(a,b,n,\emph{A}) = \frac{\sum _{i=1}^{n-1} in_i}{N},  \label{eq-X}
\end{equation}
\begin{equation}
Y(a,b,n,\emph{A}) = \frac{\sum _{i=1}^{n-1} im_i}{M},  \label{eq-Y}
\end{equation}
\begin{equation}
Z(a,b,n,\emph{A}) = \frac{\sum _{i=1}^{n-1} i(m_i + n_i)}{N + M}, \label{eq-Zp}
\end{equation}
\begin{equation}
X'(a,b,n,\emph{A}) = \frac{\sum _{i=1}^{n-1} in_i}{N(n-1)},  \label{eq-Xp}
\end{equation}
\begin{equation}
Y'(a,b,n,\emph{A}) = \frac{\sum _{i=1}^{n-1} im_i}{M(n-1)},   \label{eq-Yp}   
\end{equation}
\begin{equation}
Z'(a,b,n,\emph{A}) = \frac{\sum _{i=1}^{n-1} i(m_i + n_i)}{(N + M)(n-1)}.  \label{eq-Zp}
\end{equation}

Table \ref{tab-HHL02eff} characterizes the efficiency of algorithm HHL during the testing of $(0,1,n)$-regular sequences  
for $n = 1, \ \ldots, \ 11$ vertices.
In line 11 of Table \ref{tab-HHL02eff} we see $X'(0,1,11) = 0.136887459$ and $Y'(0,1,11) = 0.615705668.$ According to these 
data in the case of 11 vertices the filtering of \textit{all} nongraphical sequences needs in average the 
14 $\%$ of the rounds, while the filtering of the graphical sequences requires $62$ $\%$ of the rounds implying that 
the complete filtering requires in average 22 $\%$ of the rounds.

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||r|r|r|r|r|r||} \hline \hline
\frac{n}{\mbox{jellemz\H o}}& X & Y &         Z     &       X'      &      Y'       &    Z'  \\ \hline
2	&	1.000000000	&	1.000000000	&	1.000000000	&	1.000000000	&	1.000000000	&	1.000000000	\\ \hline
3	&	1.000000000	&	1.750000000	&	1.300000000	&	0.500000000	&	0.875000000	&	0.650000000	\\ \hline
4	&	1.083333333	&	2.454545455	&	1.514285714	&	0.361111111	&	0.818181818	&	0.504761905	\\ \hline
5	&	1.126315789	&	3.032258065	&	1.595238095	&	0.281578947	&	0.758064516	&	0.398809524	\\ \hline
6	&	1.180555556	&	3.588235294	&	1.712121212	&	0.236111111	&	0.717647059	&	0.342424242	\\ \hline
7	&	1.220524017	&	4.111111111	&	1.796620047	&	0.203420670	&	0.685185185	&	0.299436674	\\ \hline
8	&	1.262734584	&	4.629843364	&	1.897435897	&	0.180390655	&	0.661406195	&	0.271062271	\\ \hline
9	&	1.299062610	&	5.140793396	&	1.988235294	&	0.162382826	&	0.642599175	&	0.248529412	\\ \hline
10	&	1.335323852	&	5.650162338	&	2.083407305	&	0.148369317	&	0.627795815	&	0.231489701	\\ \hline
11	&	1.368874588	&	6.157056683	&	2.174534186	&	0.136887459	&	0.615705668	&	0.217453419	\\ \hline
\hline \hline
\end{array}$
\end{scriptsize}
\caption{Efficiency of HH for the testing of all $(0,1,n)$-regular sequences for $n = 2, \ \ldots, \ 11$ 
vertices.\label{tab-HHL02eff}}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Havel-Hakimi linear testing algorithm (HHL)\label{subsec-HHT}}
The original Havel-Hakimi algorithm in worst case requires quadratic time to test the $(0,1,n)$-regular sequences. 
Using the new concepts weight pont and reserve we reduced the worst running time to $O(n).$

The definition of the \textit{weight point} $w_i$ belonging to $s_i$ was introduced in \cite{IvanyiLMS2011Acta} 
in connection with \textsc{Erd\H os-Gallai-Linear} and it is as follows. If $s_1 \geq i,$ then $w_i$ is the 
largest $k \ (1 \leq k \leq n)$ having the property $s_k \geq i.$ But if $s_1 < i,$ then $w_i = 0.$  
EGL exploits the property $w_i$ ensuring that if $i \leq w_i,$ them the key expression $\min{j,s_k}$ 
in the Erd\H os-Gallai theorem equals to $i,$ otherwise equals to $s_k.$ 

Here we extend the definition to be applicable also in the proof of the linearity of 
\textsc{Chungphaisan-Erd\H os-Gallai}. Now let $w_i$ the largest $k \ (1 \leq k \leq n)$ having the property 
$s_k \geq bi.$ But if $s_1 < bi,$ then let $w_i = 0.$ 
In the case $b = 1$ the new definition results the old one. 

In HHL the weight point $w_i$ determines the increment of the tail capacity when we switch to the investigation 
of the next element of $s.$

The remainder $r_i$ belonging to $s_i$ is defined as the unused part of the actual tail capacity and can be 
computed by the formulas 
\begin{equation}
r_i = w_1 - 1 - s_1 \label{eq-r1}
\end{equation}
and
\begin{equation}
r_i = w_i - r_{i-1} - s_i \quad \mbox{for} 1 \leq i \leq n - 1.
\end{equation}

The programs of this paper are written using the pseudocode descibed in \cite{CormenLRS2009}.

\textit{Input.} $n$: number of vertices $(n \geq 1)$; \\ 
$s = (s_1,\ldots,s_n)$: the investigated $n$-regular sequence.

\textit{Output.} $L$: logical variable. 

\textit{Work variable.} $i$: cycle variable; \\
$r = (r_1,\ldots,r_n)$: $r_i$ the reserve belonging to $s_i$; \\
$w = (w_1,\ldots,w_n)$: $w_i$ the weight point belonging to $s_i$; \\
$H = (H_1, \ldots,H_n)$: $H_i$ is the sum of the first $i$ elements of $s.$

\bigskip
\noindent \textsc{Havel-Hakimi-Linear}$(n, s, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $L = 0$                  \` \textbf{//} lines 01: set the probable value \\
\hspace{-7mm}02 \textbf{if} \= $s_1 == 0$   \` \textbf{//} lines 02--04: test of the sequence consisting of only zeros \\ 
\hspace{-7mm}03             \> $L = 1$ \\
\hspace{-7mm}04             \> \textbf{return} $L$ \\
\hspace{-7mm}05 \textbf{if} \= $s_{s_1 + 1} == 0$   \` \textbf{//} lines 05--07: test of $s_1$ in constant time \\ 
\hspace{-7mm}06             \> \textbf{return} $L$ \\
\hspace{-7mm}07 $H_1 = s_1$                             \` \textbf{//} line 07: initialization of $H$ \\
\hspace{-7mm}08 \textbf{for} \= $i = 2$ \textbf{to} $n$ \` \textbf{//} lines 09--09: further $H_i$'s\\
\hspace{-7mm}09              \> $H_i = H_{i-1} + s_i$   \\
\hspace{-7mm}10 \textbf{if} \= $H_n$ is odd \`   \textbf{//} lines 10--11: test of the parity\\
\hspace{-7mm}11             \> \textbf{return} $L$\\
\hspace{-7mm}12 $w_1 = n$                   \`  \textbf{//} lines 12--15: computation of the first weight point and reserve\\
\hspace{-7mm}13 \textbf{while} \= $s_{w_1} < 1$      \`  \textbf{//} lines 13--24: testing of $s$ \\
\hspace{-7mm}14                \> $w_1 = w_1 - 1$            \\
\hspace{-7mm}15 $r_1 = w_1 - 1 - s_1$ \\ 
\hspace{-7mm}16 $s_{n+1} = 0$ \\
\hspace{-7mm}17 \textbf{for} \= $i = 2$ \textbf{to} $n - 1 $         \\ 
\hspace{-7mm}18              \> \textbf{if} \= $s_i \leq i$ or $s_{i+1} = 0$  \\
\hspace{-7mm}19              \>             \> $L = 1$ \\
\hspace{-7mm}20              \>             \> \textbf{return} $L$ \\ 
\hspace{-7mm}21              \> $w_i = w_{i-1}$ \\
\hspace{-7mm}22              \> \textbf{while} \= $s_{w_i} < i$ and $w_i > 0$ \\
\hspace{-7mm}23              \>                \> $w_i = w_i - 1$ \\
\hspace{-7mm}24              \> \textbf{if} \= $s_i > w_i - 1 + r_{i-1}$\`\textbf{//} line 24: Is $s$ graphical?  \\
\hspace{-7mm}25              \>             \> \textbf{return} $L$  \`  \textbf{//} line 25: $s$ is not graphical \\
\hspace{-7mm}26              \> $r_i = w_i + r_{i-1} - s_i$         \`  \textbf{//} line 26: updating of the reserve \\
\hspace{-7mm}27 $L = 1$                          \`  \textbf{//} lines 27--28: $s$ is graphical  \\
\hspace{-7mm}28 \textbf{return}
\end{tabbing}

\begin{theorem} The running time of \textsc{Havel-Hakimi-Linear} is in best case $\Theta(1)$, 
and in worst case $\Theta(n).$ 
\end{theorem} 

\begin{proof} If the condition in line 2 holds, then the running time is $\Theta(1).$ If not, then we reduce the actual $w$ 
at most $n$ times and the remaining operations require $O(1)$ operations for all reductions.
\end{proof}

Now let us consider a few examples. 

\textbf{Example 1.} Let our first example $s = (3^3,1)$. According to lines 01--15 $r_1 = 0$. For $i = 2$ we get  
$w_i = 3$ and the condition of line 22 is not satisfied, therefore $s$ is \textit{not} 
$(0,1,4)$-\textit{undigraphical.} 

\textbf{Example 2.} Let our next example $s = (5,3^2,2,1^3)$. In lines 01--15 we get $w_1 = 7$ and $r_1 = 1.$ For $i = 2$ 
according to lines $w_i = 3$, the condition of line 22 does not hold and according to line 25 $r_2 = 1.$  
When $i = 3$, then $s_i \geq i$ and so according to line 16 $s$ is $(0,1,7)$\textit{-undigraphical.}
 
\textbf{Example 3.} Now let $s = (5, 4, 1^5)$. At first get $r_1 = 1,$ then for $i = 2$ we have $w_i = 2,$ therefore 
the conditions in line 22 holds, so $s$ is  \textit{not} $(0,1,7)$-\textit{undigraphical.} 

\textbf{Example 4.} Let our last example $s = (5^2,4,3^4).$ According to the first 15 lines $r_1 = 1.$ When $i = 2,$ then 
we get $w_i = 7$ and $r_2 = 2.$ Then $w_3 = 7$ and $r_3 = 4.$ If $i = 4,$ then according to $i \geq s_i$ in line 16  
$s$ \textit{is} $(0,1,7)$\textit{-undigraphical.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Degree sequences of $(0,b,n)$-graphs \label{sec-0bundi}}
In this section we use the theorem due to Chungphaisan to get a linear time algorithm for the testing of 
$(0,b,n)$-regular sequences.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Theorem of Chungphaisan and ChEGl algorithm}
In 1974 Chungphaisan extended Erd\H os-Gallai theorem for $(0,b,n)$-undigraphs, proving the 
following assertion. 

\begin{theorem}{\emph{(Chungphaisan \cite{Chungphaisan1974})}\label{th-Chung}}
Let $n \geq 1$. An $s = (s_1, \ldots, s_n)$ $(0,b,n)$-regular sequence is $(0,b,n)$-graphical if and only if 
\begin{equation}
\sum _{i=1}^n s_i \quad  \textit{is even}
\label{eq-EG0} 
\end{equation}
and
\begin{equation}\label{eq-EG1} 
\sum_{i=1}^j s_i - bj(j-1) \leq \sum _{k = j  + 1}^n \min(jb, s_k) \quad (j=1, \ldots, n-1). 
\end{equation}
\end{theorem}

\begin{proof} See \cite{Chungphaisan1974}.  \hfill $\square$
\end{proof}


In worst case the algorithm based on this theorem requires quadratic time, but the 
following assertion allows to test the sequences in linear time.

\begin{theorem} If\label{th-Chungcorr} $n \geq 1$, then an $s = (s_1,\ldots,s_n)$ $(0,b,n)$-regular sequence 
is $(0,b,n)$-graphical if and only if 
\begin{equation}
\sum _{i=1}^n s_i \quad  \textit{is even}\label{eq-Chcorr0} 
\end{equation}
and
\begin{equation}
H_i > bi(y_i - 1) + H_n - H_y    \quad (i = 1, \ldots, n - 1),\label{eq-Chcorr1} 
\end{equation}
where 
\begin{equation}
y_i = \max(i,w_i)   \quad (i = 1, \ldots, n - 1).\label{eq-Chcorr2}
\end{equation}
\end{theorem}

\begin{proof} This proof is an improved version of the proof of linearity of EGL in \cite{IvanyiL2012Comb}. 

We exploit, that $s$ is monotone and determine the capacity estimations $c_k = \min(jb, s_k)$ appearing 
in \eqref{eq-EG1}  in constant time. The base of the quick computation is again the sequence of the weight 
points $w(s) = (w_1,\ldots,w_{n-1})$ containing the \textit{weight points} belonging to of the elements of $s,$ 
and the sequence $y(s) = (y_1,\ldots,y_n)$ containing  
the \textit{cutting points} of the elements of $s$. For given $s_i$ let the weight point $w_i$ was defined in Section 
\ref{sec-01undi}. The cutting point $y_i$ be the maximum of $i$ and $w_i$, see \eqref{eq-Chcorr2}.

During the testing of the elements of $s$  there are two cases: 

 a) if $i > w_i,$ then the maximal contribution $C_i =\sum_{k=i+1}^n \min(i,s_k)$ of the actual tail of $s$ is at most  
$H_n - H_i,$ since the maximal contribution $c_k = \min(i,s_k)$ of the element $s_k$ is only $s_k$, and so  
\begin{equation}
C_i = \sum _{k=i+1}^n c_k = H_n - H_i,\label{eq-ChEGileq1}
\end{equation}  
implying the requirement
\begin{equation}
H_i \leq bi(i - 1) + H_n - H_i; \label{eq-ChEGileq2}
\end{equation}

b) if $i \leq w_i$, then the maximal contribution $C_i$ of the actual tail of $s$ consists of contributions of two types: 
$c_{i+1},\ldots,c_{w_i}$ are equal to $bi,$ while $c_j = s_j$ for $j = w_{i} + 1, \ldots, n$, therefore we have
\begin{equation}
C_i = bi(w_i - i) + H_n - H_{w_i}, \label{eq-ChEGigr1}
\end{equation} 
implying the requirement
\begin{equation}
H_i = bi(i - 1) + bi(w_i - i) + H_n - H_{w_i}.  \label{eq-ChEGigr2}
\end{equation}

Transforming \eqref{eq-ChEGigr2} we get
\begin{equation}
H_i = bi(w_i -1) + H_n - H_{w_i}.  \label{eq-ChEGigr3}
\end{equation} 

Considering the definition of $y_i$ given in \eqref{eq-Chcorr2}, further \eqref{eq-ChEGileq2} and \eqref{eq-ChEGigr2} 
we get the required \eqref{eq-Chcorr1}. \hfill $\square$ 
\end{proof}

The following algorithm tests the potential degree sequences of $(0,b,n)$-undigraphs.

\textit{Input.} $n$: number of vertices $(n \geq 1)$; \\ 
$s = (s_1, \ldots, s_n)$: a $(0,b,n)$-regular sequence;
$b$: the maximal permitted number of arcs between two vertices. 

\textit{Output.} $L$: logical variable. 

\textit{Work variable.} $i$: cycle variable; \\
$r = (r_1, \ldots, r_n)$: $r_i$ is the reserve belonging to $s_i$; \\
$w = (w_1, \ldots, w_n)$: $w_i$ is the weightpoint belonging to $s_i.$


\bigskip
\noindent \textsc{Chungphaisan-Erd\H os-Gallai-Linear}$(n, s, b, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_{1} = s_1$                                   \` \textbf{//} line 01: initialization of $H_1$\\
\hspace{-7mm}02 \textbf{for} \= $i = 2$ \textbf{to} $n - 1$      \` \textbf{//} line 02--03: computation of the elements of $H$\\
\hspace{-7mm}03              \> $H_{i} = H_{i-1} + s_{i}$    \\
\hspace{-7mm}04 \textbf{if} \= $H_n$ is odd                \` \textbf{//} line 04--05: test of the parity   \\
\hspace{-7mm}05             \>  \textbf{return}\\
\hspace{-7mm}06 $w = n$                                      \` \textbf{//} lines 06: initialization of the first weight point \\
\hspace{-7mm}07 \textbf{for} \= $i = 1$ \textbf{to} $n - 1$    \`  \textbf{//} lines 07--14: test of $s$    \\ 
\hspace{-7mm}08              \> \textbf{while} \= $s_w < ib$ and $w > 0$       \\ 
\hspace{-7mm}09              \>                \> $w = w - 1$             \\ 
\hspace{-7mm}10              \> $y = \max(i,w)$ \\              
\hspace{-7mm}11              \> \textbf{if} \= $H_i > bi(y - 1) + H_n - H_y$  \\
\hspace{-7mm}12              \>             \> \textbf{return} $L$    \` \textbf{//} lines 12:  acceptance of $s$ \\
\hspace{-7mm}13 $L = 1$                         \` \textbf{//} lines 13--14:  acceptance of $b$\\
\hspace{-7mm}14 \textbf{return} $L$
\end{tabbing}  
  
  
\begin{theorem} The running time of \textsc{Chungphaisan-Erd\H os-Gallai-Linear} is $\Theta(n)$ in all cases.
\end{theorem}

\begin{proof} Lines 01--06 require $\Theta(n)$ time. Since the value of $w$ is strictly decreasing, lines 07--14 require 
$O(n)$ time, therefore the running time is $\Theta(n)$ in all cases.
\end{proof}    

Let us consider two examples. Let $b = 3$ and $s' = (13,10,5,5,4,1).$  $H_6 = 38$ is even. If $i = 1,$ then $w_i = y = 5$ 
and the condition in line 18 is not satisfied $(13 \leq 3 \cdot 1 \cdot (5 - 1)).$ If $i = 2,$ then $w_i = y = 2$ and the condition 
in line 18 holds $(23 > 3 \cdot 2 \cdot (2 - 1)) + 5 + 5 + 4 + 1,$ therefore $s$ is \textit{not} $(0,3,6)$-\textit{graphical.} 

Let $b$ remain $3,$ but change $s$ to $s' = (13,10,5,5,4,3).$ The first difference comparing with the previous example comes when 
$i = 2.$ Now $23 \leq 3 \cdot 2 \cdot (2 - 1)) + 5 + 5 + 4 + 3,$ and the condition in line 18 holds for $i = 3, \ 4$ and $5$ too, 
therefore $s'$ is $(0,3,6)$-graphical.   

Table \ref{tab-ChEGL02n} contains the number of the excluded in the $i$-th $(i = 1, \ldots, 10)$ non 
$(0,2,n)$-undigraphical sequences for $n = 1, \ \ldots, \ 11$ vertices.

\begin{table}[!ht]
\centering
\begin{tiny}
$\begin{array}{||r||r|r|r|r|r|r|r|r|r|r||} \hline \hline
  n/i &  1   &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10  \\ \hline
1	&	0	&				&		&		&		&		&		&		&		&		\\ \hline
2	&	3	&	0	&				&		&		&		&		&		&		&		\\ \hline
3	&	22	&	3	&	0	&		&				&		&		&		&		&		\\ \hline
4	&	132	&	26	&	2	&	0	&				&		&		&		&		&		\\ \hline
5	&	824	&	164	&	31	&	4	&	0	&				&		&		&		&		\\ \hline
6	&	5 084	&	1 026	&	276	&	75	&	3	&	0			&		&		&		&		\\ \hline
7	&	31 902	&	6 288	&	2 018	&	829	&	111	&	5		0	&		&		&		&		\\ \hline
8	&	201 366	&	39 090	&	13 282	&	7 231	&	1 837	&	203	&	4	&	0	&				&		\\ \hline
9	&	1 281 918	&	244 833	&	84 340	&	53 594	&	20 681	&	4 259	&	298	&	6	&	0	&				\\ \hline
10	&	8 207 232	&	1 548 774	&	529 578	&	365 461	&	183 262	&	59 726	&	8 709	&	470	&	5	&	0			\\ \hline
11	&	52 819 163	&	9 866 545	&	3 331 910	&	2 385 963	&	1 404 590	&	632 058	&	155 070	&	17 213	&	660	&	7	\\ \hline\hline
\end{array}$ 
\end{tiny}
\caption{The number of the excluded in the $i$th $(i = 1, \ldots, 10)$ by ChEGL non $(0,2,n)$-undigraphical 
sequences for $a = 0,$ $b = 2$ and $n = 1, \ \ldots, \ 11$ vertices.\label{tab-ChEGL02n}}
\end{table}

Table \ref{tab-ChEGl02g} contains the number of the excluded in the $i$th $(i = 1, \ldots, n)$ 
round $(0,2,n)$-graphical sequences for $n = 1, \ \ldots, \ 11$ vertices. 

\begin{table}[!ht]
\centering
\begin{scriptsize}
$\begin{array}{||r||r|r|r|r|r|r|r|r|r|r||} \hline \hline
n/i &  1   &   2   & 3       & 4   & 5  &  6  &   7   &  8    &   9   &  10 \\ \hline \hline
1	&	1	&		&		&		&		&		&		&		&		&				\\ \hline
2	&	2	&	0	&		&		&		&		&		&		&		&				\\ \hline
3	&	1	&	9	&	0	&		&		&		&		&		&		&				\\ \hline
4	&	1	&	7	&	42	&	0	&		&		&		&		&		&				\\ \hline
5	&	1	&	10	&	29	&	224	&	0	&		&		&		&		&				\\ \hline
6	&	1	&	14	&	49	&	183	&	1 297	&	0	&		&		&		&				\\ \hline
7	&	1	&	18	&	70	&	345	&	1 143	&	7 658	&	0	&		&			&		\\ \hline
8	&	1	&	23	&	97	&	559	&	2 326	&	7 262	&	46 489	&	0	&		&				\\ \hline
9	&	1	&	28	&	125	&	846	&	4 038	&	15 927	&	46 074	&	286 007	&	0	&				\\ \hline
10	&	1	&	34	&	159	&	1 191	&	6 520	&	29 629	&	107 724	&	295 609	&	1 779 026	&	0			\\ \hline
11	&	1	&	40	&	193	&	1 624	&	9 668	&	50 663	&	213 399	&	728 610	&	1 900 061	&	11 154 877		\\ \hline
\hline 
\end{array}$
\end{scriptsize}
\caption{The number of the filtered $(0,2,n)$-undigraphical sequences in the $i$th $(i = 1, \ldots, 10)$ round 
of ChEGL for $n = 1, \ \ldots, \ 11$ vertices.\label{tab-ChEGl02g}}
\end{table}

Table \ref{tab-ChEGL02eff} characterizes the efficiency of algorithm ChEGL for the testing of $(0,2,n)$-regular sequences and 
$n = 1, \ \ldots, \ 11$ vertices.

\begin{table}[!t]
\centering
\begin{scriptsize}
$\begin{array}{||r||r|r|r|r|r|r||} \hline \hline
\frac{n}{\mbox{jellemz\H o}}& X & Y &    Z          &   X'          &         Y'     &    Z'  \\ \hline
2	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	&	1,000000000	\\ \hline
3	&	1,120000000	&	1,900000000	&	1,342857143	&	0,560000000	&	0,950000000	&	0,671428571	\\ \hline
4	&	1,187500000	&	2,820000000	&	1,576190476	&	0,395833333	&	0,940000000	&	0,525396825	\\ \hline
5	&	1,232649071	&	3,803030303	&	1,759906760	&	0,308162268	&	0,950757576	&	0,439976690	\\ \hline
6	&	1,280785891	&	4,788212435	&	1,957042957	&	0,256157178	&	0,957642487	&	0,391408591	\\ \hline
7	&	1,322698224	&	5,770438549	&	2,137870128	&	0,220449704	&	0,961739758	&	0,356311688	\\ \hline
8	&	1,363989613	&	6,751572493	&	2,320248929	&	0,194855659	&	0,964510356	&	0,331464133	\\ \hline
9	&	1,402468979	&	7,733105601	&	2,496464714	&	0,175308622	&	0,966638200	&	0,312058089	\\ \hline
10	&	1,439464334	&	8,714770487	&	2,670148311	&	0,159940482	&	0,968307832	&	0,296683146	\\ \hline
11	&	1,474743645	&	9,697001722	&	2,839981439	&	0,147474365	&	0,969700172	&	0,283998144	\\ 
\hline \hline
\end{array}$ 
\end{scriptsize}
\caption{The efficiency of ChEGL during the testing of  $(0,2,n)$-regular sequences for  
$n = 1, \ \ldots, \ 11$ vertices.\label{tab-ChEGL02eff}}
\end{table}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Degree sequences of $(a,b,n)$-undigraphs \label{sec-abundi}}
Theorem \ref{th-Chung} due to Chungphaisan has the following straightforward consequence. 

\begin{corollary} Let\label{cor-abnundi} $n \geq 2$. An $s=(s_1, \ldots, s_n)$ 
$(a,b,n)$-undiregular sequence is $(a,b,n)$-undigraphical 
if and only if the sequence $s' = (s_1 - a(n - 1), \ldots, s_n - a(n - 1))$ is $(0, b-a,n)$-undigraphical.
\end{corollary} 

\begin{proof} In an $(a,b,n)$-undigraph the elements of every pair of vertices is connected with at least $a$ arcs. 
Therefore if we remove $a$ arcs, then we get a $(0,b-a,n)$-undigraph.
\end{proof}

Using Corollary \ref{cor-abnundi} it is easy to test an $(a,b,n)$-regular sequence: we use ChEG with input sequence 
$s' = (s_1 - a(n - 1), \ldots, s_n - a(n - 1)).$

\section{Summary\label{sec-summary}}
The paper contains an overview on the known algorithms of testing of the potential degree sequences of $(a,b,n)$-graphs. 
The known methods for $(a,b,n)$-digraphs in worst case require only linear time but for $(a,b,n)$-undigraphs 
in worst case at least quadratic time. We proposed new linear time algorithms for $(0,b,n)$-undigraphs which can be applied 
for $(a,b,n)$-undigraphs too. 

\textbf{Acknowledgement.} The author thanks Lor\'and Lucz, student of Faculty of Informatics of E\"otv\"os Lor\'and 
University for the computer experiments. 

\begin{thebibliography}{0}

\bibitem{Burns2007} \textbf{Burns, J. M.,} The number of degree sequences of graphs,  
PhD Dissertation, MIT, 2007.

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

\bibitem{Chungphaisan1974} \textbf{Chungphaisan, V.,} Conditions for sequences to be $r$-graphical,  
\textit{Discrete Math.} \textbf{7} (1974), 31--39. 

\bibitem{Choudum1986} \textbf{Choudum, S. A.,} A simple proof of the Erd\H os-Gallai theorem on graph sequences, 
\textit{Bull. Austral. Math. Soc.} \textbf{33} (1986),  67--70.

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

\bibitem{ErdosMT2010} \textbf{Erd\H os, P. L., I. Mikl\'os and T. Toroczkai,}     
A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs, 
\textit{Electron. J. Combin.} \textbf{17(1)} (2010), R66, 10 pp.

\bibitem{Frank2011} \textbf{Frank, A.,} \textit{Connections in Combinatorial Optimization}, 
Oxford University Press, Oxford, 2011.

\bibitem{GrossY2004} \textbf{Gross, J. L. and J. Yellen} (Eds.), \textit{Handbook of Graph Theory}, CRC Press, 
Boca Raton, FL, 1994.

\bibitem{Hakimi1962} \textbf{Hakimi, S. L.,} On the 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{IvanyiL2012Comb}  \textbf{Iv\'anyi, A. and L. Lucz,} Erd\H os-Gallai test in linear time, 
\textit{Combinatorica} (submitted).

\bibitem{IvanyiLMS2011Acta} \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--268.
 
\bibitem{IvanyiP2011} \textbf{Iv\'anyi, A. and S. Pirzada,} \textit{Comparison based ranking,} 
in A. Iv\'anyi (Ed.) \textit{Algorithms of Informatics, Vol. 3} (electronic book).  AnTonCom, Budapest 2011, 1262--1311. 

\bibitem{KimTME2009} \textbf{Kim, H., T. Toroczkai, I. Mikl\'os, P. L. Erd\H os and L. A. Sz\'ekely,}     
Degree-based graph construction, \textit{J. Physics: Math. Theor. A} \textbf{42(39)} (2009), 392--401. 

\bibitem{KleitmanW1973} \textbf{Kleitman, D. J. and Wang, D. L.,} Algorithms for constructing graphs and 
digraphs with given valencies and factors. \textit{Discrete Math.} \textbf{6} (1973), 79--88.

\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{Moon1963} \textbf{Moon, J. W.,} An extension of Landau's theorem,
\textit{Pacific J. Math.} \textbf{13} (1963), 1343--1345.

\bibitem{NarayanaB1964} \textbf{Narayana, T. V. and D. H. Bent,} Computation of the number of score sequences in 
round-robin tournaments, \textit{Canad. Math. Bull.} \textbf{7(1)}  (1964), 133--136.

\bibitem{Ozkan2011} \textbf{\"Ozkan, S.,} Generalization of the Erd\H os-Gallai inequality, \textit{Ars Combin.}   
\textbf{98} (2011), 295--302.

\bibitem{PecsySz2000} \textbf{P\'ecsy, G. and L. Sz\H ucs,}     
Parallel verification and enumeration of tournaments,  
\textit{Stud. Univ. Babe\c s-Bolyai, Inform.} \textbf{45(2)} (2000), 11--26. 

\bibitem{Sloane2011A004251} 
\textbf{Sloane N. J. A.,} The number of degree-vectors for simple graphs, in:  
N. J. A. Sloane (Ed.) \textit{The On-Line Encyclopedia of Integer Sequences,} 2011. http://oeis.org/Seis.html 

\bibitem{TripathiVW2010} \textbf{Tripathi, A., S. Venugopalan and D. B. West,}   
A short constructive proof of the Erd\H os-Gallai characterization of graphic lists, 
\textit{Discrete Math.} \textbf{310(4)} (2010), 833--834. 

\bibitem{TripathiV2003} \textbf{Tripathi, A. and S. Vijay,}   
A note on a theorem of Erd\H os \& Gallai, \textit{Discrete Math.} \textbf{265(1--3)} (2003), 417--420.

\bibitem{Weisstein2011DS} \textbf{Weisstein, E. W.,} \textit{Degree sequence,} 
From MathWorld---Wolfram Web Resource, 2012. http://mathworld.wolfram.com/DegreeSequence.html 
 
\bibitem{Weisstein2011GS} \textbf{Weisstein, E. W.,} \textit{Graphic sequence,}
From MathWorld---Wolfram Web Resource, 2012. http://mathworld.wolfram.com/GraphicSequence.html 

\end{thebibliography}

\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}

\end{document}

