On the Swap-Distances of Different Realizations of a Graphical Degree Sequence

DOI10.1017/S0963548313000096zbMath1263.05016arXiv1205.2842MaRDI QIDQ4921567

István Miklós, Péter L. Erdős, Zoltán Király

Publication date: 13 May 2013

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

degree sequencesswap operationGallai-type identitiesswap distance \swap sequences

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Vertex degrees (05C07) Sequences and sets (11B99)

Related Items (12)

Graph realizations constrained by skeleton graphs ⋮ On degree sequence optimization ⋮ Optimization over degree sequences of graphs ⋮ Optimization over Degree Sequences ⋮ On the longest flip sequence to untangle segments in the plane ⋮ Complexity results on untangling red-blue matchings ⋮ On realizations of a joint degree matrix ⋮ Exact sampling of graphs with prescribed degree correlations ⋮ The mixing time of switch Markov chains: a unified approach ⋮ Configuring Random Graph Models with Fixed Degree Sequences ⋮ New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling ⋮ Navigating between packings of graphic sequences

Cites Work

• A theorem on flows in networks
• Zero-one matrices with zero trace
• The k-factor conjecture is true
• On the degrees of the vertices of a directed graph
• Algorithms for constructing graphs and digraphs with given valences and factors
• Combinatorial Properties of Matrices of Zeros and Ones
• Degree-based graph construction
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Partitions and Their Representative Graphs
• The Factors of Graphs
• A Short Proof of the Factor Theorem for Finite Graphs

This page was built for publication: On the Swap-Distances of Different Realizations of a Graphical Degree Sequence