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.

Key words and phrases. Degree sequence, graphical sequence, \((a,b,n)\)-graph, tournament.