Degree sequences of multigraphs

Abstract. Let \(a, \ b\) and \(n\) be integers, \(n \geq 1\) and \(b \geq a \geq 0\). Let an \((a,b,n)\)-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)\)-digraph and if it is undirected, then it is called \((a,b,n)\)-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 \((b,b,n)\)-digraphs, and in 2009 Iványi did for \((a,b,n)\)-digraphs. Havel in 1955, Erdős and Gallai in 1960 proposed an algorithm to decide the same question for \((0,1,n)\)-undigraphs. Their theorem was extended to \((0,b,n)\)-undigraphs by Chungphaisan in 1974. In 2011 Özkan [24] 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.