Adjacency relationships forced by a degree sequence

DOI10.1007/S00373-018-1953-1MaRDI QIDQ1756108zbMATH OpenOpenAlexWikidataFDO

Authors Michael D. Barrus

Publication date 11 January 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

degree sequencerealizationthreshold graphdominance order

Mathematics Subject Classification ID

Vertex degrees (05C07)

Abstract: There are typically several nonisomorphic graphs having a given degree sequence, and for any two degree sequence terms it is often possible to find a realization in which the corresponding vertices are adjacent and one in which they are not. We provide necessary and sufficient conditions for two vertices to be adjacent (or nonadjacent) in every realization of the degree sequence. These conditions generalize degree sequence and structural characterizations of the threshold graphs, in which every adjacency relationship is forcibly determined by the degree sequence. We further show that degree sequences for which adjacency relationships are forced form an upward-closed set in the dominance order on graphic partitions of an even integer.

Recommendations

• The polytope of degree sequences
• Graph classes characterized both by forbidden subgraphs and degree sequences
• Forcibly bipartite and acyclic (uni-)graphic sequences
• On realization graphs of degree sequences
• On forcibly connected graphic sequences

Cites work

• scientific article; zbMATH DE number 3648761 (Why is no real title available?)
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 3674138 (Why is no real title available?)
• scientific article; zbMATH DE number 3743297 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• Best monotone degree conditions for graph properties: a survey
• Decomposition of graphical sequences and unigraphs
• Hereditary unigraphs and Erdős-Gallai equalities
• Neighborhood degree lists of graphs
• Some Properties of Graphs with Multiple Edges
• Split graphs
• The lattice of integer partitions
• The polytope of degree sequences
• The splittance of a graph
• Threshold Sequences
• Threshold graphs and related topics

Cited in

(7)

• The polytope of degree sequences
• On fractional realizations of graph degree sequences
• Degree sequences of matrogenic graphs
• The principal Erdős-Gallai differences of a degree sequence
• scientific article; zbMATH DE number 906868 (Why is no real title available?)
• Graph classes characterized both by forbidden subgraphs and degree sequences
• Weakly threshold graphs

This page was built for publication: Adjacency relationships forced by a degree sequence

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