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




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


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

\usepackage{Combi-Compu}
\usepackage{fancyhdr}
\usepackage{amssymb,amsbsy}
%\usepackage{graphics}
\usepackage[dvips]{graphicx}
\usepackage{hyperref}

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


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


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



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


\begin{document}
\setcounter{page}{1}
\newcommand\balline{\small A. Iv\'anyi, L. Lucz}
\newcommand\jobbline{\small Erd\H os-Gallai test in linear time}

\vspace{-4cm} \fofej{??}{??}{???}{???}

\vspace{.4cm}

\title{ERD\H OS-GALLAI TEST IN LINEAR TIME}


\author{{ ANTAL IV\'ANYI, LOR\'AND LUCZ}}
%% More authors can be given by repeating the \author command)


%
\keywords{degree sequence, Erd\H os-Gallai theorem, Havel-Hakimi theorem, simple graph}
%
\mathclass{05C65}
%
\compclass{G.2.2}

\projsupport{The authors 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 {Havel in 1955 \cite{Havel1955}, Erd\H os and Gallai in 1960 \cite{ErdosG1960}, Hakimi in 1962 \cite{Hakimi1962},  
Tripathi et al. in 2010 \cite{TripathiVW2010} proposed an algorithm to decide, 
whether a sequence of nonnegative integers is the degree sequence of a simple graph. 
The running time of their algorithms in worst case is $\Omega(n^2).$ In this paper we propose a new algorithm called 
\textsc{Erd\H os-Gallai-Linear}, whose worst running time is $\Theta(n).$ As an application of the new algorithm 
we determined the number of the degree sequences of simple graphs for $n = 24, \ \ldots, \ 29$ vertices \cite{Sloane2011A004251}.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\normalsize
\section{Introduction\label{sec-intro}}
A classical problem of graph theory is the characterization of the degree sequences of different graph classes. 
In 1953 Landau \cite{Landau1953} gave a necessary and sufficient condition, allowing the linear time test of 
score sequences of tournaments. Landau's theorem recently was extended for $(a,b)$-tournaments \cite{Ivanyi2009,Ivanyi2010} 
containing at least $a$ and at most $b$ edges between any two vertices. 
Havel \cite{Havel1955} and Hakimi \cite{Hakimi1962} proposed the same algorithm allowing quadratic time test and 
reconstruction of simple graphs. 

Erd\H os and Gallai published in 1960 \cite{ErdosG1960} a necessary and sufficient condition, 
allowing to test the degree sequences of simple graphs in quadratic time. Recently Tripathi, Venugopalanb and West 
\cite{TripathiVW2010} gave a constructive proof of Erd\H os-Gallai theorem. Chungphaisan in 1974 \cite{Chungphaisan1974} and 
\"Ozkan in 2011 \cite{Ozkan2011} extended Erd\H os-Gallai and Havel-Hakimi theorems to loopless multigraphs containing at most 
$b$ edges between any two vertices.   

Since  in worst case the testing algorithms of simple graphs have to investigate all elements of the
input sequence, therefore every testing algorithm based on the RAM model of computations requires at least $\Omega(n)$ time. 
But all the known testing algorithms require $\Omega(n^2)$ time.

Our aim was to decrease the gap between the trivial lower bound and the time complexity of the known algorithms. Although this 
problem is interesting in itself, for us the main motivation was our wish to answer the question formulated in the 
recent monograph \cite[Research problem 2.3.1]{Frank2011} of Andr\'as Frank: "\textit{Decide if a sequence of n integers 
can be the final score of a football tournament of n teams.}" During testing and reconstructing of potential football 
sequences important subproblem is the handling of sequences of draws. And the problems "Is this sequence graphical?" and 
"Is this sequence a football draw sequence?" are equivalent, therefore the quick answer is vital for us.

Let $n$ be a positive integer.  A sequence of integer numbers  $b = (b_1,\ldots,b_n)$ is called $n$\textit{-bounded}, 
if $0 \leq b_i \leq n - 1$ for $i = 1,\ldots, n$. An $n$\textit{-bounded} sequence $b$ is called $n$\textit{-regular,} 
if $b_n \geq b_{n-1} \geq \cdots \geq b_1$. An $n$-regular sequence is called $n$\textit{-even}, if the sum of its elements 
is even. An $n$-regular sequence $b$ is called $n$\textit{-zerofree}, if $b_n > 0$.  
An $n$\textit{-regular} sequence $b$ is called $n$\textit{-graphical,} if there exists a simple graph $G$ 
whose degree sequence is $b$. Instead of $n$-bounded, $n$-regular, $n$-even, $n$-zerofree and $n$-graphical 
we use the simpler bounded, regular, even, zerofree and graphical expression too. 

At first we tried to use different linear time filtering algorithms hoping to get quickly the graphical/nongraphical 
quality of many investigated sequences and so to decrease the expected running time of the 
testing. In \cite{IvanyiLMS2011Acta} we reported on some successes of this approach. While we were seeking linear 
approximating testing algorithms, we have found an improvement of Erd\H os-Gallai theorem allowing to test regular 
sequences in $O(n)$ time even in the worst case.  
 
As a side product we extended OEIS \cite{Sloane2011A004251} with the continuation of some sequences. 
The most interesting extensions are the new elements of degree sequences  
of simple graphs. 

The aim of this paper is to give a short description of the new algorithm.

The paper consists of four parts. After the introductory Section \ref{sec-intro}, in Section \ref{sec-classical} 
we describe the classical algorithms of the testing of degree sequences of simple graphs.  
Section \ref{sec-EGL} contains the description of the new linear time testing algorithm (EGL), while in  
Section \ref{sec-EGEP} we briefly describe the enumerative (EGE) and parallel (EGP) versions of EGL and the results 
of the corresponding program. 

Approximate algorithms, further precise algorithms and detailed simulation results can be found in 
\cite{IvanyiLMS2011Acta}, while the parallel results are presented in \cite{IvanyiL2011CEJOR}.
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Classical precise algorithms\label{sec-classical}}
If given a decreasing sequence $b = (b_1,\ldots,b_n)$ of nonnegative integers then the first $i$ elements of the sequence 
are called \textit{the head} of the sequence belonging to the index $i$, while the last $n - i$ elements of the sequence 
\textit{the tail} of the sequence belonging to the index $i$. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Havel-Hakimi algorithm (HH) \label{sec-HH}}
The first solution of the testing of the degree sequences of simple graphs was given by V\'aclav Havel Czech mathematician 
in 1955 \cite{Havel1955,Lovasz2007}. Louis Hakimi published the same method in 1962 \cite{Hakimi1962}. Their theorem and 
algorithm today are called usually \textit{Havel-Hakimi theorem}, resp. \textit{Havel-Hakimi algorithm}. 

\begin{theorem} \emph{(Havel \cite{Havel1955}, Hakimi \cite{Hakimi1962})} If\label{th-HH} $n \geq 3$, then the $n$-regular sequence 
$b = (b_1,\ldots,b_n)$ is $n$-graphical if and only if the sequence $b' = (b_2 - 1, b_3 - 1, \ldots,  
b_{b_1} - 1, b_{b_1 + 1} - 1, b_{b_1 + 2}, \ldots, b_n)$ is $(n - 1)$-graphical. \qed
\end{theorem}

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

If we write a recursive RAM algorithm based on this theorem then its worst running time will be $\Omega(n^2)$, since 
the sum of the degrees is $\Theta(n^2)$ in a complete graph. It is worth 
to remark, that the proof of the theorem is constructive, therefore the algorithm based on this theorem not only tests 
the input sequence, but if the sequence is graphical, then the algorithm constructs a corresponding simple graph.   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Erd\H os-Gallai algorithm (EG) \label{subsec-EG}}
In chronological order the next result was the following necessary and sufficient condition due to Paul Erd\H os 
and Tibor Gallai \cite{ErdosG1960}. 

\begin{theorem} \emph{(Erd\H os, Gallai \cite{ErdosG1960})} Let $n \geq 2.$ The $n$-regular sequence $b = (b_1, \ldots, b_n)$ 
is $n$-graphical if and only if 
\begin{equation}
\sum _{i=1}^n b_i \quad \mbox{even }\label{eq-EGparity}
\end{equation}
and
\begin{equation}
\sum_{i=1}^j b_i - j(j - 1) \leq \sum _{k=j+1}^n \min(j,b_k) \quad (j = 1,\ldots,n-1).\label{eq-EGbinom}
\end{equation}
\end{theorem}

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

Although the algorithm based on this theorem never produces a corresponding graph, in worst case the systematic application of 
(\ref{eq-EGbinom}) requires $\Theta(n^2)$ time. Recently Tripathi, Venogupalanb and West \cite{TripathiVW2010} published 
a constructive proof of Erd\H os-Gallai theorem, but the worst running time of their algorithm is $\Theta(n^3)$. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Linear time Erd\H os-Gallai algorithm (EGL) \label{sec-EGL}}
The new algorithm \textsc{Erd\H os-Gallai-Linear} exploits, that $b$ is monotone. It determines the capacities 
$c_k = \min(i,b_k)$ in constant time. The base of the quick computation is the sequence $w(b) = (w_1,\ldots,w_{n-1})$ 
containing the \textit{weight points} of the elements of $b$, and the sequence $y(b) = (y_1,\ldots,y_n)$ containing  
the \textit{cutting points} of the elements of $b$. For given sequence $b$ let the weight point $w_i$ the index of $b_k$ 
having the maximal index among such elements of $b$ which are greater or equal to $i$, that is
\begin{equation}
w_i(b) = w_i = \max(k \ | \ b_k \geq i)  \label{eq-wib},
\end{equation}
and let the cutting point $y_i$ be the maximum of $i$ and $w_i$, that is
\begin{equation}
y_i(b) = y_i = \max(i,w_i) \quad (i = 1,\ldots,n). \label{eq-yib} 
\end{equation}

\begin{theorem} \emph{(Iv\'anyi, Lucz, M\'ori, S\'ot\'er \cite{IvanyiLMS2011Acta})} 
If  $n \geq 1,$\label{theorem-EGL} then the $n$-regular sequence $(b_1, \ldots, b_n)$ is $n$-graphical if and only if
\begin{equation}
H_n \quad \mbox{is even}\label{eq-EGLeven}
\end{equation}
and
\begin{equation}
H_i \leq i(y_i - 1) + H_n - H_{y_i} \quad (i = 1, \ldots, n). \label{eq-EGLH}
\end{equation}
\end{theorem}

\begin{proof}
(\ref{eq-EGLeven}) is the same as (\ref{eq-EGparity}). 

During the testing of the elements of $b$ by \textsc{Erd\H os-Gallai-Linear} there are two cases: 
\begin{itemize}
\item if $i > w_i,$ then the maximal contribution $C_i =\sum_{k=i+1}^n \min(i,b_k)$ of the actual tail of $b$ is at most  
$H_n - H_i,$ since the maximal contribution $c_k = \min(i,b_k)$ of the element $b_k$ is only $b_k$, and so  
\begin{equation}
C_i = \sum _{k=i+1}^n c_k = H_n - H_i,\label{eq-EGileq1}
\end{equation}  
implying the requirement
\begin{equation}
H_i \leq i(i - 1) + H_n - H_i; \label{eq-EGileq2}
\end{equation}
\item if $i \leq w_i$, then the maximal contribution $C_i$ of the actual tail of $b$ consists of contributions of two types: 
$c_{i+1},\ldots,c_{w_i}$ are equal to $i,$ while $c_j = b_j$ for $j = w_{i} + 1, \ldots, n$, therefore we have
\begin{equation}
C_i = i(w_i - i) + H_n - H_{w_i}, \label{eq-EGigr1}
\end{equation} 
implying the requirement
\begin{equation}
H_i = i(i - 1) + i(w_i - i) + H_n - H_{w_i}.  \label{eq-EGigr2}
\end{equation}
\end{itemize}

Transforming \eqref{eq-EGigr2} we get
\begin{equation}
H_i = i(w_i -1) + H_n - H_{w_i}.  \label{eq-EGigr3}
\end{equation} 

Considering the definition of $y_i$ given in \eqref{eq-yib}, further \eqref{eq-EGileq2} and \eqref{eq-EGigr2} 
we get the required \eqref{eq-EGLH}. \qed 
\end{proof}

The following program is based on Theorem \ref{theorem-EGL}. 
It decides whether an $n$-regular sequence is $n$-graphical or not. 

In this paper we use the pseudocode described in \cite{CormenLRS2009}.

\textit{Input}. $n$: number of vertices $(n \geq 1)$; \\
$b = (b_1,\ldots,b_n)$: $n$-regular sequence.  

\textit{Output}. $L$: logical variable, whose value is \textsc{True}, if the input is graphical, 
and it is \textsc{False}, if the input is not graphical. 

\textit{Work variables.} $i$: cycle variable; \\
$H = (H_1,\ldots,H_n)$: $H_i$ is the cumulated degree, that is the sum of the first $i$ elements of the tested $b$; \\
$w$: the weight point of the actual $b_i$, that is the maximum of the indices of such elements 
of $b,$ which are not smaller than $i$; \\
$y$: the cutting point of the actual $b_i$, that is the maximum of $w$ and $i$. 

\bigskip
\noindent \textsc{Erd\H os-Gallai-Linear}$(n, b, L)$
\vspace{-2mm}
\begin{tabbing}
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_{1} = b_1$                                  \` \textbf{//} line 01: initialization \\
\hspace{-7mm}02 \textbf{for} \= $i=2$ \textbf{to} $n$      \` \textbf{//} line 02--03: computation of the elements of $H$\\
\hspace{-7mm}03              \> $H_{i} = H_{i-1} + b_{i}$    \` \textbf{//} line 04--06: test of the parity \\
\hspace{-7mm}04 \textbf{if} \= $H_n$ is odd\\
\hspace{-7mm}05             \> $L = \textsc{False}$\\
\hspace{-7mm}06             \>  \textbf{return}\\
\hspace{-7mm}07 $w = n$                                      \` \textbf{//} line 07: initialization of the weight point \\
\hspace{-7mm}08 \textbf{for} \= $i = 1$ \textbf{to} $n$      \` \textbf{//} lines 08--12: test of the elements of $b$\\
\hspace{-7mm}09              \> \textbf{while} \= $w > 0$ and $b_w < i$ \\
\hspace{-7mm}10              \>                \> $w = w - 1$ \\
\hspace{-7mm}11              \> $y = \max(i,w)$  \\
\hspace{-7mm}12              \> \textbf{if} \= $H_i > i(y - 1) + H_n - H_y$  \\
\hspace{-7mm}13              \>             \> $L = \textsc{False}$ \` \textbf{//} lines 13--14: rejection of $b$ \\
\hspace{-7mm}14              \>             \> \textbf{return} $L$   \\
\hspace{-7mm}15 $L = \textsc{True}$                         \` \textbf{//} lines 15--16:  acceptance of $b$\\
\hspace{-7mm}16 \textbf{return} $L$
\end{tabbing}

\begin{theorem} \textsc{Erd\H os-Gallai-Linear} decides in $\Theta(n)$ time, whether an $n$-regular sequence is graphical or not.  
\end{theorem} 

\begin{proof} Line 01 requires $O(1)$ time, lines 02--03 $\Theta(n)$ time, lines 04--07 $O(1)$ time,  
lines 08--14 $O(n)$ time ($w$ is decreased at most $n$ times), lines 15--23 $O(n)$ time and lines 24--25 $O(1)$ time, 
therefore the total time requirement of the algorithm is $\Theta(n)$. 
\end{proof}

It is worth to remark, that if $b$ is not regular, then we can use a linear time sorting algorithm to sort $b$ and then apply 
\textsc{Erd\H os-Gallai-Linear} for the sorted $b$, that is the testing can be executed in linear time 
for bounded input too.

Since in the case of a graphical sequence all elements of the investigated sequence are to be tested, 
in the case of RAM model of computations \textsc{Erd\H os-Gallai-Linear} is asymptotically optimal testing algorithm. 
Since we need $n$ memory cells for $b$, $n$ cells for $H$, the memory requirement of the program is $\Theta(n)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Enumerating (EGE) and parallel (EGP) Erd\H os-Gallai test \label{sec-EGEP}}
\textsc{Erd\H os-Gallai-Enumerating} algorithm (EGE) \cite{IvanyiL2011CEJOR,IvanyiLMS2011Acta} generates and 
tests every zerofree even sequence  
for given $n$. Its input is $n$ and output is the number of corresponding zerofree graphical sequences $G_z(n).$

\begin{table}[!t]
\begin{scriptsize}
\begin{center}
\begin{tabular}{|r|r|r|r|r|}  \hline \hline
$n$&$E(n)$                                &$G_z(n)$                             &$G(n)$                               &$\frac{G(n)}{E(n)}$      \\ \hline \hline
$1$&$1$                                   &$\mathbf{0}$                         &$1$                                  &$1.000000$ \\ \hline
$2$&$2$                                   &$\mathbf{1}$                         &$2$                                  &$1.000000$ \\ \hline
$3$  &     $6$                            &$\mathbf{2}$                         &$4$                                  &$0.666667$  \\ \hline
$4$  &     $19$                           &$\mathbf{7}$                         & $11$                                &$0.578947$\\ \hline
$5$  &    $66$                            &$\mathbf{20}$                        &$31$                                 &$0.469697$       \\ \hline
$6$  &    $236$                           &$\mathbf{71}$                        &$102$                                &$0.432203$       \\ \hline 
$7$  &    $868$                           &$\mathbf{240}$                       &$342$                                &$0.394009$       \\ \hline 
$8$  &    $3\,235$                        &$\mathbf{871}$                       &$1\,213$                             &$0.374961$    \\ \hline 
$9$  &   $12\,190$                        &$\mathbf{3\,148}$                    &$4\,361$                             &$0.357752$ \\ \hline 
$10$  &    $46\,252$                      &$\mathbf{11\,655}$                   &$16\,016$                            &$0.346277$ \\ \hline 
$11$  &  $176\,484$                       &$\mathbf{43\,332}$                   &$59\,348$                            &$0.336280$  \\ \hline 
$12$  & $676\,270$                        &$\mathbf{162\,769}$                  &$222\,117$                           &$0.328444$   \\ \hline 
$13$  &$2\,600\,612$                      &$\mathbf{614\,198}$                  &$836\,315$                           &$0.321584$       \\ \hline 
$14$  &$10\,030\,008$                     &$\mathbf{2\,330\,537}$               &$3\,166\,852$                        &$0.315738$      \\ \hline 
$15$  &$38\,781\,096$                     &$\mathbf{8\,875\,768}$               &$12\,042\,620$                       &$0.310528$    \\ \hline 
$16$  &$150\,273\,315$                    &$\mathbf{33\,924\,859}$              &$45\,967\,479$                       &$0.305892$    \\ \hline 
$17$  &$583\,407\,990$                    &$\mathbf{130\,038\,230}$             &$176\,005\,709$                      &$0.301685$\\ \hline 
$18$  &$2\,268\,795\,980$                 &$\mathbf{499 753 855}$               & $675\,759\,564$                     &$0.297849$\\ \hline 
$19$  &$8\,836\,340\,260$                 &$\mathbf{1\,924\,912\,894}$          &$2\,600\,672\,458$                   &$0.294316$\\ \hline 
$20$  &$34\,461\,678\,394$                &$\mathbf{7\,429\,160\,296}$          &$10\,029\,832\,754$                  &$0.291043$\\ \hline 
$21$  &$134\,564\,560\,988$               &$\mathbf{28\,723\,877\,732}$         &$38\,753\,710\,486$                  &$0.287993$      \\ \hline 
$22$  &$526\,024\,917\,288$               &$\mathbf{111\,236\,423\,288}$        &$149\,990\,133\,774$                 &$0.285139$      \\ \hline 
$23$&$2\,058\,358\,034\,616$              &$\mathbf{431\,403\,470\,222}$        &$581\,393\,603\,996$                 &$0.282455$   \\ \hline 
$24$&$\mathbf{8\,061\,901\,596\,814}$     &$\mathbf{1\,675\,316\,535\,350}$     &$\mathbf{2\,256\,710\,139\,346}$     &$0.279923$       \\ \hline 
$25$&$\mathbf{31\,602\,652\,961\,516}$    &$\mathbf{6\,513\,837\,679\,610}$     &$\mathbf{8\,770\,547\,818\,956}$     &$0.277526$   \\ \hline 
$26$&$\mathbf{123\,979\,635\,837\,176}$   &$\mathbf{25\,354\,842\,100\,894}$    &$\mathbf{34\,125\,389\,919\,850}$    &$0.275250$     \\ \hline 
$27$&$\mathbf{486\,734\,861\,612\,328}$   &$\mathbf{98\,794\,053\,269\,694}$    &$\mathbf{132\,919\,443\,189\,544}$   &$0.273084$     \\ \hline 
$28$&$\mathbf{1\,912\,172\,660\,219\,260}$&$\mathbf{385\,312\,558\,571\,890}$   &$\mathbf{518\,232\,001\,761\,434}$   &$0.271017$     \\ \hline 
$29$&$\mathbf{7\,516\,816\,644\,943\,560}$&$\mathbf{1\,504\,105\,116\,253\,904}$&$\mathbf{2\,022\,337\,118\,015\,338}$&$0.269042$\\ \hline \hline
\end{tabular}
\caption{Number of even, zerofree graphical, and graphical sequences for $n = 1, \ \ldots, \ 29$ vertices. \label{tab-EZG}}
\end{center}
\end{scriptsize}
\end{table}


The algorithm is based on \textsc{Erd\H os-Gallai-Linear}. It generates and tests (in lexicographic order) 
only the zerofree even sequences, that is about the 25 percent of the $n$-regular sequences \cite{IvanyiLMS2011Acta}. 

EGE tests the input sequences only in the jumping points $j_i$ (defined by $b_i < b_{i+1}$ and $i < n$). 
According to \cite{IvanyiLMS2011Acta} about the half of the elements of the input sequences is jumping point.  

Table \ref{tab-EZG} contains the number of even $(E(n))$, zerofree graphical $(G_z(n))$, and graphical 
$(G(n))$ sequences. The bold values were new for \textit{The On-Line Encyclopedia of Integer Sequences}.

Important property of EGE is that it solves in $\Theta(1)$ average time 
\begin{itemize}
\item
the generation of one zerofree even sequence;
\item
the updating of the sequence of the cumulated degrees $H$;
\item
the updating of the sequence of the checking points $C$;
\item
the updating of the sequence of the weight points $W$.
\end{itemize}

The average running time of this algorithm for a sequence is $\Theta(1)$, so the total running time of the whole program 
is $\Theta(E(n))$.

We implemented the parallel version of EGE (EGP). It was run on about 200 PC's containing about 700 cores. The total 
running time of EGP and the number of slices of the whole task are shown in Table \ref{fig-totalpar} for 
$n = 24, \ \ldots, \ 29$ vertices. 

\begin{table}[!t]
\begin{small}
\begin{center}
\begin{tabular}{||r|r|r||}  \hline \hline
$n$  & running time (in days)       & number of slices   \\ \hline \hline
$24$ &              $7$              & $415$           \\ \hline
$25$ &              $26$              & $415$           \\ \hline
$26$ &             $70$             & $435$ \\ \hline
 $27$ &            $316$            & $435$ \\ \hline
 $28$ &               $1130$             & $2 001$ \\ \hline
 $29$ &               $6733$             & $15 119$\\ \hline \hline
\end{tabular}
\caption{The total running time of EGP for $n = 24, \ \ldots, \ 29.$\label{fig-totalpar}}
\end{center} 
\end{small}
\end{table}

If we wish to enjoy the "parallel advantage" (the substantial decreasing of the running time) of EGP, then we have to increase 
the number of slices according to the growth of $G(n)$ and some operations on the first sequence of each slice require 
$\Theta(n)$ time, and therefore the running time of EGP is $\Theta(nE(n))$. 


\medskip
We remark that the referenced papers and programs can be downloaded from the site 
\href{http://compalg.inf.elte.hu/~tony/Kutatas/EGHH/}{http://compalg.inf.elte.hu/$\sim$tony/Kutatas/EGHH/}.

\paragraph{Acknowledgements.} The authors thank Andr\'as Frank and Zolt\'an Kir\'aly 
(E\"otv\"os Lor\'and University, Faculty of Science, Institute of Mathematics) 
for the continuous consultations. The European Union and the European Social Fund have provided financial support to the project 
under the grant agreement no. T\'AMOP 4.2.1/B-09/1/KMR-2010-0003.




\begin{thebibliography}{0}

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

\bibitem{CormenLRS2009} \textsc{\href{http://www.cs.dartmouth.edu/~thc/}{T. H. Cormen},     
\href{http://people.csail.mit.edu/cel/}{Ch. E. Leiserson},  
\href{http://people.csail.mit.edu/rivest/}{R. L. Rivest}} and \textsc{\href{http://www.columbia.edu/~cs2035/}{C. Stein}}:     
\textit{Introduction to Algorithms}. Third edition, The MIT Press/McGraw Hill, Cambridge/New York, 2009.

\bibitem{ErdosG1960} \textsc{\href{http://www-history.mcs.st-and.ac.uk/Mathematicians/Erdos.html}{P. Erd\H os}} and    
\textsc{\href{http://hu.wikipedia.org/wiki/Gallai_Tibor}{T. Gallai}}:  
Gr\'afok el\H o\'irt fok\'u pontokkal (Graphs with prescribed degrees). \textit{Mat. Lapok} \textbf{11} (1960), 264--274.

\bibitem{Frank2011} \textsc{\href{http://www.cs.elte.hu/~frank/}{A. Frank}}: \textit{Connections in Combinatorial Optimization}.   
Oxford University Press, Oxford, 2011.

\bibitem{Hakimi1962} \textsc{\href{http://en.wikipedia.org/wiki/S.\_L.\_Hakimi}{S. L. Hakimi}}:   
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} \textsc{\href{http://en.wikipedia.org/wiki/Degree_(graph_theory)}{V. Havel}}: 
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} \textsc{\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{A. Iv\'anyi}}:  
Reconstruction of complete interval tournaments. \textit{Acta Univ. Sapientiae}, 
\href{http://www.acta.sapientia.ro/acta-info/informatica-main.htm}{\textit{Inform.}} 
\textbf{1(1)} (2009), 71--88.

\bibitem{Ivanyi2010} \textsc{\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{A. Iv\'anyi}}:    
Reconstruction of complete interval tournaments. II. \textit{Acta Univ. Sapientiae},   
\href{http://www.acta.sapientia.ro/acta-math/matematica-main.htm}{\textit{Math.}} \textbf{2(1)} (2010), 47--71.

\bibitem{IvanyiL2011CEJOR} \textsc{\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{A. Iv\'anyi}} and 
\textsc{\href{http://people.inf.elte.hu/lulsaai}{L. Lucz}}: Parallel Erd\H os-Gallai algorithm. 
\href{http://www.springerlink.com/content/1435-246x/}{\textit{CEJOR}} \textit{Cent. Eur. J. Oper. Res.}  
(submitted).

\bibitem{IvanyiLMS2011Acta} \textsc{\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{A. Iv\'anyi}, 
\href{http://people.inf.elte.hu/lulsaai}{L. Lucz}, \href{http://www.math.elte.hu/~mori}{F. T. M\'ori}} and  
\textsc{\href{http://people.inf.elte.hu/sopsaai}{P. S\'ot\'er}}: On Erd\H os-Gallai and Havel-Hakimi algorithms.  
\textit{Acta Univ. Sapientiae}, \href{http://www.acta.sapientia.ro/acta-info/informatica-main.htm}{\textit{Inform.}} 
\textbf{3(2)} (2011), 230--268. 

\bibitem{Landau1953} \textsc{H. H. Landau}: On dominance relations and the structure of 
\href{http://www.springerlink.com/content/765042v152l07721/}{animal societies}. III. 
The condition for a score sequence. \textit{Bull. Math.} \href{}{\textit{Biophys.}} \textbf{15} (1953), 143--148. 

\bibitem{Lovasz2007} \textsc{\href{http://www.cs.elte.hu/~lovasz/}{L. Lov\'asz}}:    
\textit{Combinatorial Problems and Exercises} (corrected version of 
the second edition).  AMS \href{http://www.ams.org/bookstore/chelsealist}{Chelsea} Publishing, Boston, 2007.

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

\bibitem{Sloane2011A004251} \textsc{\href{http://www2.research.att.com/~njas/}{N. J. A. Sloane}}:
The number of \href{http://oeis.org/A004251}{graphical vectors}. 
In: \textit{The On-Line Encyclopedia of Integer Sequences} (ed. by N. J. A. Sloane), 2011.

\bibitem{TripathiVW2010} \textsc{\href{http://maths.iitd.ac.in/people/faculty/amitabh_tripathi.php}{A. Tripathi}}, 
 \textsc{S. Venugopalanb} and \textsc{\href{http://www.math.uiuc.edu/~west/}{D. B. West}}: 
A short constructive proof of the Erd\H os-Gallai characterization of graphic lists. 
\href{http://www.sciencedirect.com/science/journal/0012365X}{\textit{Discrete}} \textit{Math.} 
\textbf{310(4)} (2010), 833--834. 

\end{thebibliography}

\end{document}

