A note on the characterization of digraphic sequences

Given pairs ( a 1 , b 1 ) , … , ( a n , b n ) of nonnegative integers, the digraph realization problem for digraphs asks whether there is a simple digraph (no loops or multiple arcs) with vertices v 1 , … , v n such that each vertex v i ∈ V has indegree a i and outdegree b i . Fulkerson and Chen obtained a characterization analogous to the classical Erdős–Gallai characterization for graphs, but with the additional constraint that the pairs must be sorted in nonincreasing lexicographical order. We provide a more general characterization that avoids the additional sorting. The inequalities needed correspond to those k such that a k + 1 > a k . We prove a similar result when one loop is allowed at each vertex.