The principal Erdős-Gallai differences of a degree sequence

DOI10.1016/J.DISC.2021.112755MaRDI QIDQ2075508zbMATH OpenOpenAlexFDO

Authors Michael D. Barrus

Publication date 14 February 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.07643

zbMATH Keywords

degree sequenceErdős-Gallai theoremmajorizationsplit graphthreshold graph

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Special sequences and polynomials (11B83)

Abstract: The ErdH{o}s--Gallai criteria for recognizing degree sequences of simple graphs involve a system of inequalities. Given a fixed degree sequence, we consider the list of differences of the two sides of these inequalities. These differences have appeared in varying contexts, including characterizations of the split and threshold graphs, and we survey their uses here. Then, enlarging upon properties of these graph families, we show that both the last term and the maximum term of the principal ErdH{o}s--Gallai differences of a degree sequence are preserved under graph complementation and are monotonic under the majorization order and Rao's order on degree sequences.

Recommendations

• The degree of primitive sequences and Erdős conjecture
• Solution to a general version of a degree sequence variant of the Erdős-Sós conjecture
• Hadwiger's conjecture for degree sequences
• On a degree sequence analogue of Pósa's conjecture
• A simple proof of the Erdos-Gallai theorem on graph sequences
• On a Problem of Erdos Concerning Primitive Sequences
• A generalization of a theorem of Erdős-Rényi to m-fold sums and differences
• A variant of Niessen's problem on degree sequences of graphs
• The distribution of the generic recursively enumerable degrees
• Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture

Cites work

• A note on a theorem of Erdős and Gallai
• A Note on Unigraphic Sequences
• Adjacency relationships forced by a degree sequence
• Contributions to the theory of graphic sequences
• Decomposition of graphical sequences and unigraphs
• Degree sequences and majorization
• Degree sequences of matrogenic graphs
• Fuchsian equations of type DN
• Graphic sequences with unique realization
• Hereditary unigraphs and Erdős-Gallai equalities
• scientific article; zbMATH DE number 3648761 (Why is no real title available?)
• scientific article; zbMATH DE number 3674138 (Why is no real title available?)
• scientific article; zbMATH DE number 3720966 (Why is no real title available?)
• scientific article; zbMATH DE number 3754758 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3489167 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Laplacian spectra and spanning trees of threshold graphs
• Length thresholds for graphic lists given fixed largest and smallest entries and bounded gaps
• Linear recognition of pseudo-split graphs
• On fractional realizations of graph degree sequences
• Once more on matrogenic graphs
• Rao's degree sequence conjecture
• Sequences with a unique realization by simple graphs
• Split graphs
• The splittance of a graph
• Threshold graphs and related topics
• Threshold Sequences
• Weakly threshold graphs

Cited in

(5)

• Degree sequences and majorization
• Hereditary unigraphs and Erdős-Gallai equalities
• Upward-closed hereditary families in the dominance order
• Characterising \(3\)-polytopes of radius one with unique realisation
• On a conjecture that strengthens Kundu's k-factor theorem

This page was built for publication: The principal Erdős-Gallai differences of a degree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2075508)