Degree sequences of matrogenic graphs
The structure of matrogenic graphs introduced by \textit{S. Földes} and \textit{P. L. Hammer} [Combinatorics, Keszthely 1976, Colloq. Math. Soc. Janos Bolyai 18, 331-352 (1978; Zbl 0395.05021)] is described. In particular, it is proved that every matrogenic graph is the unique realization up to isomorphism, of its degree sequence. An exhausting characterization of degree sequences of matrogenic and more generally box-threshold graphs is given. A linear-time recognition algorithm for matrogenic degree sequences is described. Analogous results for matrogenic graphs are obtained independently by the reviewer [Discrete Math. 51, 91-100 (1984; see the following review)].
scientific article; zbMATH DE number 3867383
scientific article