Constructing bounded degree graphs with prescribed degree and neighbor degree sequences

DOI10.1016/j.dam.2023.02.004OpenAlexW3202307230MaRDI QIDQ2696614

Sohaib Nasir, Varun Srikanth, Aaron Li, Uroš Čibej, István Miklós

Publication date: 17 April 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

degree sequencesNMR spectroscopyneighbor degree constraint

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Chemical graph theory (05C92)

Uses Software

• SCIP
• Zimpl

Cites Work

• Unnamed Item
• Colour degree matrices of graphs with at most one cycle
• On realizations of a joint degree matrix
• Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem
• A theorem on flows in networks
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• Not all simple looking degree sequence problems are easy
• Packing of graphic n-tuples
• Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography
• Integer Programming with a Fixed Number of Variables
• Combinatorial Properties of Matrices of Zeros and Ones
• Degree-constrained edge partitioning in graphs arising from discrete tomography
• Constructing and sampling graphs with a prescribed joint degree distribution

This page was built for publication: Constructing bounded degree graphs with prescribed degree and neighbor degree sequences