On Erdős-Gallai and Havel-Hakimi algorithms

Abstract

Havel in 1955, Erdős and Gallai in 1960, Hakimi in 1962, Ruskey, Cohen, Eades and Scott in 1994, Barnes and Savage in 1997, Kohnert in 2004, Tripathi, Venugopalan and West in 2010 proposed a method to decide, whether a sequence of nonnegative integers can be the degree sequence of a simple graph. The running time of their algorithms is $\Omega (n^2)$ in worst case. In this paper we propose a new algorithm called EGL (Erdős-Gallai Linear algorithm), whose worst running time is $\Theta (n).$ As an application of this quick algorithm we computed the number of the different degree sequences of simple graphs for $24,...,29$ vertices.

Cited by in corpus (1)

• Hereditary unigraphs and Erdős--Gallai equalities