Degree-based graph construction

DOI10.1088/1751-8113/42/39/392001MaRDI QIDQ3650407zbMATH OpenOpenAlexFDO

Authors Hyunju Kim, Z. Toroczkai, Péter L. Erdős, István Miklós, László A. Székely

Publication date 14 December 2009

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

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

zbMATH Keywords

degree sequencef-factor subgraphsgraph constructionnetwork modelling

Mathematics Subject Classification ID

Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computer-aided design (modeling of curves and surfaces) (65D17)

Abstract: Degree-based graph construction is an ubiquitous problem in network modeling, ranging from social sciences to chemical compounds and biochemical reaction networks in the cell. This problem includes existence, enumeration, exhaustive construction and sampling questions with aspects that are still open today. Here we give necessary and sufficient conditions for a sequence of nonnegative integers to be realized as a simple graph's degree sequence, such that a given (but otherwise arbitrary) set of connections from a arbitrarily given node are avoided. We then use this result to present a swap-free algorithm that builds {em all} simple graphs realizing a given degree sequence. In a wider context, we show that our result provides a greedy construction method to build all the $f$-factor subgraphs embedded within $K_{n}setminus{S}_k$, where $K_n$ is the complete graph and $S_k$ is a star graph centered on one of the nodes.

Recommendations

• scientific article; zbMATH DE number 4065027
• Classifying graphs by degrees
• Degree complete graphs
• Analyzing graphs by degrees
• Graphs with degree constraints
• scientific article; zbMATH DE number 446400
• Degree sequences in graphs
• scientific article; zbMATH DE number 713480
• Graphs with a given degree sequence
• Degrees in a digraph whose nodes are graphs

Cited in

(17)

• Rejection sampling of bipartite graphs with given degree sequence
• On partial sorting in restricted rounds
• An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem
• Relaxed and approximate graph realizations
• Global dynamics of an epidemic model with incomplete recovery in a complex network
• Graph realizations constrained by skeleton graphs
• A survey of discrete methods in (algebraic) statistics for networks
• On fractional realizations of graph degree sequences
• New classes of degree sequences with fast mixing swap Markov chain sampling
• On realizations of a joint degree matrix
• On the swap-distances of different realizations of a graphical degree sequence
• Constructing and sampling directed graphs with given degree sequences
• Exact sampling of graphs with prescribed degree correlations
• A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
• Graph realizations: maximum degree in vertex neighborhoods
• Methods for the graph realization problem
• Closeness centrality reconstruction of tree graphs

This page was built for publication: Degree-based graph construction

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