Degree sequences of matrogenic graphs
type: Item
instance of: scholarly article
title: Degree sequences of matrogenic graphs
zbMATH Open document ID: 0545.05054
DOI: 10.1016/0012-365X(84)90023-2
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3867383
zbMATH Keywords: degree sequences
zbMATH Keywords: box-threshold graphs
author: Paola Marchioro
author: Aurora Morgana
author: Rossella Petreschi
author: Bruno Simeone
reviewed by: Regina Iosifovna Tyshkevich
MaRDI profile type: MaRDI publication profile
cites work: Q3941433
cites work: Q4165164
cites work: Q4193514
cites work: Q4177589
cites work: Some Properties of Graphs with Multiple Edges
cites work: Q4182796
cites work: Threshold Sequences
cites work: The splittance of a graph
cites work: Matroidal graphs
cites work: Class of graphs with restricted neighborhoods
cites work: Graphs and degree sequences: Canonical decomposition
full work available at URL: 0012-365x(84)90023-2
OpenAlex ID: W2036789425
Recommended article: The polytope of degree sequences
Recommended article: Q3812278
Recommended article: Hereditary unigraphs and Erdős-Gallai equalities
Recommended article: Adjacency relationships forced by a degree sequence
Recommended article: On realization graphs of degree sequences
description: scientific article; zbMATH DE number 3867383