Degree complete graphs (Q2368928): Difference between revisions

Let \(S= (S_1,\dots, S_n)\) be an out-degree vector of an orientation of a graph \(G\) with vertices \(1,\dots, n\). According to the partial order \(\succeq\) on the nonnegative integral vectors [see \textit{H. J. Ryser}, J. Algebra 10, 246--261 (1968; Zbl 0167.28001)] \(S^r_G\succeq S\succeq S^l_G\), \(\sum^n_{i=1} s_i= |E(G)|\) and \(0\leq s_i\leq d_G(i)\), \(i= 1,\dots, n\), where \(S^r_G\) and \(S^l_G\) are the maximum and minimum degree vectors with respect to \(\succeq\). A graph is called degree complete if each nonnegative integral vector \(S\) satisfying this condition is an out-degree vector of an orientation of \(G\). The author characterizes the degree complete graphs by showing two forbidden configurations in graphs.