Degree complete graphs (Q2368928)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Degree complete graphs |
scientific article |
Statements
Degree complete graphs (English)
0 references
28 April 2006
0 references
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.
0 references
labelled graph
0 references
orientation
0 references
degree vector
0 references