Degree complete graphs

Ryser [Combinatorial Mathematics, Carus Mathematical Monograph, vol. 14, Wiley, New York, 1963] introduced a partially ordered relation ‘≽≽’ on the nonnegative integral vectors. It is clear that if S=(s1,s2,…,sn)S=(s1,s2,…,sn) is an out-degree vector of an orientation of a graph G   with vertices 1,2,…,n1,2,…,n, thenequation(Π)SGr≽S≽SGl,∑i=1nsi=|E(G)|and0⩽si⩽dG(i),i=1,2,…,n,where SGr and SGl are the maximum and minimum degree vectors with respect to ‘≽≽’, respectively. A graph G   is called degree complete if each nonnegative integral vector satisfying the condition (Π)(Π) is an out-degree vector of an orientation of G. By using flows in networks, the degree complete graphs are characterized by showing two simple forbidden configurations.