\documentclass[11pt,twoside]{article} 
\usepackage{combinatorica-8aug}
\usepackage[latin2]{inputenc}
\frenchspacing

\usepackage{epic}
\usepackage{eepic}

\title{%
Erdős-Gallai test in linear time
}

\newcommand{\vol}{\textbf{3,} 2 (2011) xx--yy}   %% to be completed by the editor, do not modify it
\setcounter{page}{1}  %% to be completed by the editor 

\newcommand{\amss}{\amssubj{%
%% Write here the AMS subject classification codes as: 68R15
05C85, 68R10
}}   %% Source:   http://www.ams.org/msc/    
%%%\newcommand{\CRs}{\CRsubj{%
%% Write here the CR  Categories and Description codes codes as: 
%%%G.2.2. [Graph Theory]: Subtopic - Network problems.
%%}}   %% Source: http://oldwww.acm.org/class/1998/
\newcommand{\keyw}{\keywords{%
%% Write here the keywords and phrases, as: 
\noindent $^*$The European Union and the European Social Fund have provided financial support 
to the project under the grant agreement no. TÁMOP 4.2.1/B-09/1/KMR-2010-0003.
}} 

\def\textbinom#1#2{\left(\strut\textstyle{#1 \atop #2}\right)}

\begin{document}
\maketitle

\twoauthors{%
\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony&angolul=1}{Antal Iv\'anyi$^*$ }}
{%
\href{http://compalg.inf.elte.hu/tanszek/index.php?angolul=1}{Department of Computer Algebra}, 
\href{http://www.elte.hu/en}{E\"otv\"os Lor\'and University}, Hungary}
{%
 \href{mailto:tony@compalg.inf.elte.hu}{tony@compalg.inf.elte.hu}
}{%
\href{http://people.inf.elte.hu/lulsaai}{Lor\'and Lucz$^*$}
}{%
 \href{http://compalg.inf.elte.hu/tanszek/index.php?angolul=1}{Department of Computer Algebra}, 
 \href{http://www.elte.hu/en}{E\"otv\"os Lor\'and University}, Hungary}
{%
\href{mailto:lorand.lutz@caesar.elte.hu}{lorand.lucz@caesar.elte.hu}}


 %% Short name of the authors and short title, to be included in heading.

\short{%
A. Iványi, L. Lucz
}{%
Erdős-Gallai test in linear time}

\begin{abstract}
Havel in 1955 \cite{Havel1955}, Erdős and Gallai in 1960 \cite{ErdosG1960}, 
Hakimi in 1962 \cite{Hakimi1962}, Ruskey, Cohen, Eades and Scott in 1994 \cite{RuskeyCES1994}, Barnes and Savage in 1997  
\cite{BarnesS1997}, Tripathi, Venugopalan and West in 2010 \cite{TripathiVW2010} proposed a method to decide, whether a sequence    
of nonnegative integers can be the degree sequence of a simple graph (such sequences are called graphical). 
The running time of their algorithms in worst case is $\Omega(n^2).$ In this paper we propose a new algorithm called LED 
(Linear Erdős-Gallai algorithm), whose worst running time is $O(n).$ 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 LEG is asymptotically optimal.
\end{abstract}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\normalsize
\section{Introduction\label{sec-Intro}}
In practice we often need the ranking of different objects. One of the popular methods is pairwise comparison of the objects and 
assignment points to the objects, summing the assigned points and ranking of the objects according to the number 
of the gathered points. E. G. Landau referenced biological \cite{Landau1953}, Hakimi chemical,  
\cite{Hakimi1962}, Kim et al. \cite{KimTME2009}, Newman and Barab\'asi \cite{NewmanB2006} network,   
Bozóki, Fülöp, and Rónyai economical \cite{BozokiFR2010} applications,  
Liljeros et al. applications connected with human connections \cite{LiljerosEASA2001}, Iványi et al. connected with sport 
 \cite{Ivanyi2009,Ivanyi2010,IvanyiLS2011}. 

A számos lehetséges terminológia közül Erdős Pál és Gallai Tibor \cite{ErdosG1960} cikkének szóhasználatát és jelöléseit 
követjük. A pontozás módjától függően sokféle feladat és eredmény van. Ebben a cikkben gráfon 
olyan véges, irányítás nélküli gráfot értünk, amelyben nem fordulnak elő hurokélek és bármely két csúcsot 
legfeljebb egy él köt össze -- azaz \textit{egyszerű gráfokról} lesz szó. 
Ez a gráf annak a pontozásnak felel meg, amikor az összehasonlításoknak két 
lehetséges eredménye van: vagy mindkét objektum egy, vagy pedig mindkettő nulla pontot kap. Az összehasonlítások 
eredményét ábrázoló gráfban két csúcs pontosan akkor van összekötve, amikor a nekik megfelelő objektumok 
összehasonlítása során mindkét objektum egy pontot kapott. 

A sok népszerű feladat közül azt vizsgáljuk, hogyan dönthető el gyorsan, hogy nemnegatív egészek 
$n \geq 1$ hosszúságú $b = (b_1,\ldots,b_n)$ sorozatához létezik-e olyan egyszerű gráf, amelynek 
$b$ a foksorozata. 

A hasonló feladatokkal kapcsolatban megjegyezzük, hogy mind az irányítatlan, mind pedig az irányított gráfokkal kapcsolatban  
az utóbbi néhány évben is számos cikk és könyvfejezet jelent meg (például \cite{Ivanyi2011AML,RodsethST2009,TripathiVW2010}, illetve   
\cite{BeasleyBR2009,ErdosMT2010,Frank2011,Ivanyi2009,Ivanyi2010}).

Legyen $n \geq m \geq 11$ és $b \geq$. Egész számok $b = (b_1,\ldots,b_nm$ sorozatát \textit{$(m,n)$-korlátosnak} 
(röviden: korlátosnak) nevezzük, ha $0 \leq b_i \leq n - 1$ minden $1 \leq i \leq m$ indexre. 
A $b = (b_1,\ldots,b_m)$ $n$-korlátos sorozatot \textit{$(m,n)$-szabályosnak} (röviden: szabályosnak) mondjuk, ha   
$n - 1 \geq b_1 \geq \cdots \geq b_m \geq 0.$ Egy $(m,n)$-szabályos sorozatot 
\textit{$n$-megvalósíthatónak} (röviden: \textit{jónak}) nevezünk, ha létezik olyan $G$ egyszerű gráf, hogy 
$G$ foksorozata $(b_1,b_2,\ldots,b_m,0^{n-m}),$ ahol $0^{n - m}$ $n - m$ darab nulla elemet jelent. Ha egy 
korlátos vagy szabályos sorozat esetén $m = n,$ akkor az $n$ paramétert csak egyszer írjuk ki. 

A továbbiakban főleg szabályos sorozatokkal foglalkozunk. A definíciókban az alsó és felső korlátok azért szerepelnek, hogy 
ellenőrző algoritmusainkat megkíméljük a nyilvánvalóan nem jó sorozatok ellenőrzésétől, 
ezért ezek a megszorítások nem jelentik az általánosság megszorítását. 

Cikkünk fő célkitűzése, hogy minél kisebb várható futási idejű algoritmust találjunk annak eldöntésére, hogy előírt $b$ 
szabályos sorozathoz található-e olyan $G$ egyszerű gráf, melynek foksorozata $b.$ A probléma önmagában is érdekes, azonban 
számunkra külön motivációt jelent, hogy a feladat részfeladatként jelentkezik, amikor minél kisebb várható futási idejű 
algoritmust keresünk annak eldöntésére, hogy előírt sorozat lehet-e egy labdarúgó bajnokság pontsorozata 
\cite{Frank2011,Ivanyi2001,Ivanyi2011Egres,Ivanyi2011Opkut,IvanyiMN2011,KovacsP2002,Ivanyi2011Egres}. 

Melléktermékként bővítettük az EIS \cite{Sloane2011} adatbázist: egyrészt a benne lévő ismert sorozatok új elemeivel, másrészt 
konkrét alkalmazásokkal kapcsolatos új sorozatok eleminek megadásával.

A cikkben egyrészt a vizsgált feladatot pontosan megoldó klasszikus és általunk javasolt új algoritmusokat, másrészt a feladat 
közelítő megoldását végző, új közelítő algoritmusokat vizsgálunk.

A cikk felépítése a következő. A bevezető első rész után a témakör klasszikus algoritmusait foglaljuk össze. A harmadik rész 
az új tesztelő algoritmusokat ismerteti, az negyedik részben a közelítő algoritmusok hibáját vizsgáljuk, míg az ötödikben  
a pontos algoritmusok futási idejét elemezzük. 

A cikk eredményeinek egy része a magyar nyelvű \cite{Ivanyi2011AML} cikkből származik.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Classical precise theorems}
Given sequence $b = (b_1,\ldots,b_n)$ of nonegative integers the first $i$ elements of the sequence we call 
\textit{the head} of the sequence belonging to the index $i,$ while the last $n - i$ elements of the sequence we call 
\textit{the tail} of the sequence belonging to the index $i.$ 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Havel-Hakimi theorem}
A feladat megoldására az első módszert Vaclav Havel cseh matematikus javasolta 1955-ben \cite{Havel1955,Lovasz2007}. 

\begin{theorem} \emph{(Havel \cite{Havel1955})} If $n \geq 3$, then the $n$-regular sequence $b = (b_1,\ldots,b_n)$   
is $n$-good iff 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)$-good.
\end{theorem}

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

Ha ezen tétel alapján írunk egy rekurzív algoritmust, akkor annak futási ideje a RAM számítási modell 
\cite{CormenLRS2009} szerint legrosszabb esetben $\Theta(n^2)$. Érdemes megjegyezni, hogy a tétel bizonyítása konstruktív, 
és a bizonyításon alapuló algoritmus négyzetes idő alatt nem csak ellenőriz, hanem egy megfelelő gráfot is előállít 
(feltéve persze, hogy létezik megfelelő egyszerű gráf). 
Mivel például a teljes gráfnak $\textbinom{n}{2}$ éle van, a megvalósítást is biztosító algoritmus futási ideje nem lehet 
kisebb, mint négyzetes.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Erdős-Gallai theorem\label{subsec-EG}}
In 1962 Louis Hakimi \cite{Hakimi1962} published independently the same result, therefore the theoren is called today 
usually as  \textit{Havel-Hakimi theorem}, and the method of reconstruction 
is called \textit{Havel-Hakimi algorithm}.

Időrendben a következő eredmény Erdős Pál és Gallai Tibor alábbi szükséges és elégséges feltétele \cite{ErdosG1960} volt. 

\begin{theorem} \emph{(Erdős, Gallai, \cite{ErdosG1960})} Let $n \geq 3.$ The $n$-regular sequence $b = (b_1\ldots,b_n)$ 
is $n$-good iff 
\begin{equation}
\sum _{i=1}^n b_i \quad \mbox{páros}\label{eq-EGparos}
\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{Choudum1986,ErdosG1960,SierksmaH1991,TripathiVW2010}.
\end{proof}

Bár ez a tétel csak ellenőriz, (\ref{eq-EGbinom}) módszeres alkalmazása \textit{minden} esetben $\Theta(n^2)$ időt 
igényel. A közelmúltban 

Tripathi et al. \cite{TripathiVW2010} publikáltak a tételre konstruktív bizonyítást, amely 
megvalósítható bemenet esetén $O(n^3)$ idő alatt egy megoldást is előállít.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Linear time Erdős-Gallai test\label{section-EGLinear}}
A következő tétel még a \textsc{EG-farokfelező} algoritmusnál is jobban kihasználja, hogy a $b$ bemeneti sorozat monoton. 
Legyen $h = \min \{k \ | \ b_k \leq i, \ i = 1, \ldots, n \}.$

\begin{theorem} Ha\label{theorem-EGLinear} $n \geq 1$, az $n$-szabályos $b = (b_1\ldots,b_n)$ sorozat akkor és csak 
akkor $n$-jó, ha
\begin{equation} 
H_n \quad \mbox{páros}\label{eq-EGLparos}
\end{equation} 
és
\begin{equation}
H_i - i(i - 1) \leq (H_n - H_{h}) + (i + 1 - h)(h - 1)/2 \quad \mbox{páros}\label{eq-EGLparos} 
\end{equation}
\end{theorem}  

\begin{proof} Mivel a $b_i$ sorozat csökkenő, az $i$ sorozat pedig növekvő, van metszéspontjuk, amely előtt az indexeke, 
és amely után a $b$ sorozat elemeinek összege adja a megfelelő farokrész kapacitását.
\end{proof}  
 
\begin{corollary} Nemnegatív egészek $n$-szabályos $b = b_1,\ldots,,b_n$ sorozatáról $O(n)$ idő alatt eldönthető, hogy 
létezik-e olyan $G$ egyszerű gráf, amelynek $b$ a foksorozata. 
\end{corollary} 

\begin{proof} A \ref{theorem-EGLinear} tételben szereplő $h$ ''metszéspont`` $O(n)$ (sőt, akár $O(\log n)$) idő alatt 
meghatárározható (a metszéspontot minden sorozatra csak egyszer kell meghatározni.) Ezek után a $b$ sorozat minden 
elemére $O(1)$ idő alatt elvégezhető a (\ref{eq-EGLparos}) egyenlőtlenség ellenőrzése.
\end{proof}

Érdemes megjegyezni, hogy akár a bemenő sorozat rendezettségétől is eltekinthetünk. Mivel a sorozat elemei egész számok és 
mindegyik a $[0,n-1]$ intervallumba esik, szükség esetén $O(n)$ idő alatt rendezni tudjuk.

A következő program a \label{theorem-EGLinear}. tétel alapján adott $n-$-re az összes $n$-páros sorozatot előállítja 
és teszteli, hogy jók-e. A teljes program futási ideje minden sorozatra $(O(n),$ így a teljes futási idő $O(n \epsilon(n)).$

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

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

\textit{Working variables.} $i$ and $j$: cycle variables; \\
$H = (H_1,\ldots,H_n)$: $H_i$ is the sum of the first $i$ elements of $b$; \\
$h$: the intersection point of the input sequence $b.$

\medskip  
\noindent \textsc{EG-Linear}$(n,b,L)$
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_1 = 0$                              \` $\rhd$ Line 01: initialization \\
\hspace{-7mm}02 \textbf{for} \= $i = 2$ \textbf{to} $n$ \` $\rhd$ Lines 02--03: computation of the elements of $H$    \\     
\hspace{-7mm}03              \> $H_i = H_{i-1} + b_i$ \\        
\hspace{-7mm}04                \> $i = 1$ \` $\rhd$ Lines 04--07: computation of $h$ \\
\hspace{-7mm}05                \> \textbf{while} \= $i < b_i$ \\
\hspace{-7mm}06                \>                \> $i = i + 1$ \\
\hspace{-7mm}07                \> $h = i$ \\ 
\hspace{-7mm}08                \> \textbf{for} \= $i = 1$ \textbf{to} $n$ \` $\rhd$ Lines 08--18: test of $b$ \\
\hspace{-7mm}09                \>              \> \textbf{while} \= $i \leq h$ \\
\hspace{-7mm}10                \>              \>                \> \textbf{if} \= $i < h$ \\
\hspace{-7mm}11                \>              \>                \>             \> \textbf{if} \= $H_i-i(i-1)>(h-i)(h-i-1)+H_n-H_h$\\
\hspace{-7mm}12                \>              \>                \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}13                \>              \>                \>             \> \textsc{return} $L$ \\
\hspace{-7mm}14                \>              \>                \> \textbf{if} \= $i \geq h$ \\
\hspace{-7mm}15                \>              \>                \>             \> \textbf{if} \= $H_i - i(i - 1) > H_n - H_i$ \\
\hspace{-7mm}16                \>              \>                \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}17                \>              \>                \>             \> \textsc{return} $L$ \\
\hspace{-7mm}18                \>              \>                \>             \> \textbf{go to}  \\            
\hspace{-7mm}19                \> $L = \textsc{True}$ \` $\rhd$ Lines 19--20: program ends with \textsc{True}   \\
\hspace{-7mm}20                \> \textbf{return} $L$  \\ 
\end{tabbing}
 

\begin{figure}[!ht]
\begin{footnotesize}
\begin{center}
\begin{tabular}{||c|c|c|c|c|c||}  \hline \hline
$n$  &  $\epsilon(n)$  & $\tau(n)$, sec  & $$Op(n)$$ & $\tau(n)/\epsilon(n)/n,$ sec 
& $Op(n)/\epsilon(n)/n$       \\ \hline \hline
$1$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$2$  &    ???    &  ???    &   ???    & ???   &  ???      \\ \hline
$3$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$4$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$5$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$6$  &    ???    &  ???    &   ???    & ???   &  ???      \\ \hline
$7$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$8$  &    ???    &  ???    &   ???    & ???   &  ???    \\ \hline
$9$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$10$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline
$11$  &    ???    &  ???    &   ???    & ???  &  ???      \\ \hline
$12$  &    ???    &  ???    &   ???    & ???  &  ???   \\ \hline
$13$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline
$14$  &    ???    &  ???    &   ???    & ???  &  ???   \\ \hline
$15$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline
$16$  &    ???    &  ???    &   ???    & ???   &  ???      \\ \hline
$17$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$18$  &    ???    &  ???    &   ???    & ???   &  ???    \\ \hline
$19$  &    ???    &  ???    &   ???    & ???   &  ???     \\ \hline
$20$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline
$21$  &    ???    &  ???    &   ???    & ???  &  ???      \\ \hline
$22$  &    ???    &  ???    &   ???    & ???  &  ???   \\ \hline
$33$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline
$24$  &    ???    &  ???    &   ???    & ???  &  ???   \\ \hline
$25$  &    ???    &  ???    &   ???    & ???  &  ???     \\ \hline \hline
\end{tabular}
\caption{Total running time of  \textsc{EG-Linear} for all regular sequences in number of operations, and  running time per 
processed elements for all regular sequences in sec and in number of operations.\label{fig-EGLinear}}
\end{center} 
\end{footnotesize}
\end{figure}


\paragraph{Acknowledgements.} The authors thank Professor András Frank (Eötvös Loránd University) 
for the continuous consultations. 

\begin{thebibliography}{99}
\bibitem{BarnesS1995} T. M. Barnes, C. D. Savage, A recurrence for counting graphical partitions,  
\href{http://www.combinatorics.org/Volume_16/PDF/v16i1n2.pdf}{\textit{Electron.}} \textit{J. Combin.}  
\textbf{2,} (1995), Research Paper 11, 10 pages (electronic).

\bibitem{BarnesS1997}  T. M. Barnes, C. D. Savage, Efficient generation of graphical partitions.  
\textit{Discrete Appl. Math.} \textbf{78,} (1--3) (1997) 17--26.

\bibitem{BozokiFR2010} \href{http://www.oplab.sztaki.hu/cv_bs_hu.htm}{Bozóki} S.: 
J. \href{http://www.oplab.sztaki.hu/cv_fj_hu.htm}{Fülöp}, L. \href{http://www.sztaki.hu/~ronyai/}{Rónyai}:  
On optimal completion of incomplete pairwise comparison matrices.    
\textit{Math. Comput. Modelling} \textbf{52,} (2010) 318--333.

\bibitem{Burns2007} Burns, J. M.: \textit{The number of 
\href{http://dspace.mit.edu/bitstream/handle/1721.1/38882/166267576.pdf?sequence=1}{degree sequences}.} 
PhD Dissertation, \href{http://web.mit.edu/}{MIT}, 2007.

\bibitem{CormenLRS2009} \textsc{\href{http://www.cs.dartmouth.edu/~thc/}{Cormen}}, T. H.,  
\textsc{\href{http://people.csail.mit.edu/cel/}{Leiserson}}, Ch. E.,  
\textsc{\href{http://people.csail.mit.edu/rivest/}{Rivest}}, R. L., 
\textsc{\href{http://www.columbia.edu/~cs2035/}{Stein}}, C.:    
\textit{Introduction to Algorithms.} Third edition, The
\href{http://mitpress.mit.edu/main/home/default.asp}{MIT} 
Press/\href{http://www.mhprofessional.com/category/?cat=1012}{McGraw} Hill, 
Cambridge/New York, 2009.

\bibitem{ErdosG1960} \textsc{\href{http://www-history.mcs.st-and.ac.uk/Mathematicians/Erdos.html}{Erd\H os}}, P.,    
\textsc{\href{http://hu.wikipedia.org/wiki/Gallai_Tibor}{Gallai}}, T.:  
\textit{Gráfok előírt fokú pontokkal}. Mat. Lapok \textbf{11,} (1960) 264--274.

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

\bibitem{FrankSS2002} \textsc{Frank, D. A.,} \textsc{Savage, C. D.,} \textsc{Sellers, J. A.:} 
\textit{On the number of graphical forest partitions.} \textit{Ars Combin.} \textbf{65} (2002) 33--37. 

\bibitem{Hakimi1962} \textsc{\href{http://en.wikipedia.org/wiki/S.\_L.\_Hakimi}{Hakimi}}, S. L.:   
\textit{On the realizability of a set of integers as degrees of the vertices 
of a simple graph.} J. SIAM Appl. Math. \textbf{10,} (1962) 496--506. 

\bibitem{Havel1955} \textsc{Havel, V.:} A remark on the existence of finite graphs (cseh); \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}{Iványi}}, A.:  
\textit{Reconstruction of complete interval tournaments.} Acta Univ. Sapientiae, 
\href{http://www.acta.sapientia.ro/acta-info/informatica-main.htm}{Informatica}, 
\textbf{1(1),} (2009) 71-88.

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

\bibitem{Ivanyi2011Egres} \textsc{\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}}, A.:   
\textit{Deciding the validity of the score sequence of a soccer tournament.} In: Open problems of the   
\href{http://lemon.cs.elte.hu/egres/open/Deciding_the_validity_of_the_score_sequence_of_a_soccer_tournament}
{Egerváry} Research Group, Budapest, 2011. 

\bibitem{IvanyiLS2011} \textsc{Iványi, A., Lucz, L., Sótér, P.:} \textit{On the Erdős-Gallai and Havel-Hakimi algorithms.} 
Acta Univ. Sapientiae, \href{http://www.acta.sapientia.ro/acta-info/informatica-main.htm}{Informatica} (benyújtva).


\bibitem{KimTME2009} \textsc{Kim, H., Toroczkai, Z., Miklós, I., Erd\H os, P. L., Székely, L. A.:}  
Degree-based graph construction. J. Physics: Math. Theor. A \textbf{42(39),} (2009) 392--401.

\bibitem{Landau1953} \textsc{Landau, H. G.:} 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{LiljerosEASA2001} \textsc{Liljeros, F., Edling, C. R., Amaral, L., Stanley, H., Áberg, Y.:}  
\textit{The web of human sexual contacts}. Nature \textbf{411,} (2001) 907--908.

\bibitem{Lovasz2007} \textsc{\href{http://www.cs.elte.hu/~lovasz/}{Lovász}}, L.:    
\textit{Combinatorial Problems and Exercises} (corrected version of 
the second edition).  AMS \href{http://www.ams.org/bookstore/chelsealist}{Chelsea} Publishing, Boston, 2007. 
 Magyarul: \textit{Kombinatorikai problémák és feladatok.} Typotex, Budapest, 1999.

\bibitem{Moon1968} \textsc{Moon, J. W.}: \textit{Topics on Tournaments.} 
\href{http://www.harcourt.com/bu\_info/hrw.html}{Holt}, Rinehart, and Winston, New York, 1968.

\bibitem{NewmanB2006} \textsc{Newman, M. E. J., Barabási, A. L.:} 
\textit{The Structure and Dynamics of Networks}. Princeton University Press, Princeton, NJ. 2006.

\bibitem{RuskeyCES1994} \textsc{Ruskey,} F., \textsc{Cohen,} R., \textsc{Eades,} P., \textsc{Scott,} A.: 
\textit{Alley CAT's in search of good homes.} Congressus Numerantium, \textbf{102} (1994) 97--110.

\bibitem{SierksmaH1991} \textsc{Sierksma,} G., \textsc{Hoogeveen, H.:} 
\textit{Seven criteria for integer sequences being graphic.}  
J. Graph Theory \textbf{15(2),} (1991) 223--231.

\bibitem{Sloane2011} \textsc{\href{http://www2.research.att.com/~njas/}{Sloane}} N. J. A. (szerkesztő): 
\textit{\href{http://oeis.org/Seis.html}{Encyclopedia} \textit{of Integer Sequences.}} 2011.

\bibitem{Sloane2011A001700} \textsc{\href{http://www2.research.att.com/~njas/}{Sloane} N. J. A.:} 
\textit{The \href{http://oeis.org/A001700}{number} of ways to put $n+1$ 
indistinguishable balls into $n+1$ distinguishable boxes.} In: The On-line Encyclopedia of the Integer Sequences. 2011.

\bibitem{Sloane2011A004251} \textsc{\href{http://www2.research.att.com/~njas/}{Sloane} N. J. A.:}
\textit{The \href{http://oeis.org/A004251}{number} 
of degree-vectors for simple graphs.} In: The On-line Encyclopedia of the Integer Sequences. 2011.

\bibitem{Sloane2011A005654} \textsc{\href{http://www2.research.att.com/~njas/}{Sloane} N. J. A.:}
\textit{The \href{http://oeis.org/A005654}{number} Number of bracelets 
with $n$ red, 1 pink and $n - 1$ blue beads.} In: The On-line Encyclopedia of the Integer Sequences. 2011.

\bibitem{Stanley1991} \textsc{\href{}{Stanley}, R.}: \textit{A zonotope associated with graphical degree sequence}. In: 
Applied geometry and discrete mathematics, Festschr. 65th Birthday Victor Klee. 
DIMACS Series in Discrete Mathematics and Theoretical Computer Science. \textbf{4,} (1991) 555-570.   

\bibitem{TripathiV2003} \textsc{Tripathi}, A., \textsc{\href{http://www.math.illinois.edu/~sujith/}{Vijay}}, S.:  
\textit{A note on a theorem of Erd\H os} \& \textit{Gallai.} 
\href{http://www.sciencedirect.com/science/journal/0012365X}{Discrete} Math. \textbf{265(1--3),} (2003) 417--420.

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

\end{thebibliography}

\end{document}
