zbMATH — the first resource for mathematics

On Erdös-Gallai and Havel-Hakimi algorithms. (English) Zbl 1302.05189
This paper presents a linear algorithm to determine whether a given non-decreasing sequence of nonnegative integers, \(\mathbf{b}=\langle b_1, b_2, \ldots, b_n \rangle,\) can be a graphical sequence, namely, the degree sequence of a simple graph. This algorithm is based on the following result that the authors recently derived: Let \(H_i=\sum_{k \in [1, i]}b_k\) and let \(w(\mathbf{b})=\langle w_1, w_2, \ldots, w_{n-1} \rangle\), where, for \(i \in [1, n-1]\), \(w_i=\max_{k \in [1, n]}\{k\mid b_k \geq i\}\), then \(\mathbf{b}\) is a graphical sequence if and only if \(H_n\) is even and, for all \(i \in [1, n-1]\), if \(i > w_i\), then \(H_i \leq i(i-1)+H_n-H_i\); otherwise, \(H_i \leq i(i-1)+i(w_i-i)+H_n-H_{w_i}\).
Besides the above major contribution, this quite inclusive, and almost exhaustive, paper makes a significant effort to discuss quite a few related works, including the two classic, but quadratic, algorithms; several newly developed algorithms, all running in quadratic time in the worst case; and linear, but approximate, algorithms based on some necessary conditions such a graphical sequence must possess, e.g., the sum of all of its components, namely, \(H_n\), must be even. The authors also review and derive several interesting combinatorial results related to the graphical sequence enumeration, both analytically and experimentally. Based on such results, various comparative and interpretive conclusions are established. Last but not least, an extensive list of close to ninety references are provided.

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science