Degree sequences of multigraphs

Let a, b and n be integers, n ≥ 1 and b ≥ a ≥ 0. Let an (a, b, n)-graph defined as a loopless graph G(a, b, n) on n vertices {V1,...,Vn}, in which Vi and Vj 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´anyi did for (a, b, n)-digraphs. Havel in 1955, Erd˝os 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 Ozkan [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.