The realization graph of every degree sequence has a Hamilton path
Abstract
For a degree sequence d, the realization graph 𝒢_ℱ(d) is the graph whose vertices are the labeled realizations of d, two of which are adjacent if they differ by a single $2$-switch. We prove that for every degree sequence d and every realization S of d, the graph 𝒢_ℱ(d) contains a Hamilton path starting at S. This answers a question of Barrus (2016), which was also raised independently by Mütze (2023) in his survey of combinatorial Gray codes. As a consequence, an embedding observation of Arikati and Peled (1999) implies that for any vectors R and C of non-negative integers, the interchange graph 𝒜ℱ(R,C) of (0,1)-matrices with row sums R and column sums C contains a Hamilton path starting at any prescribed matrix, thereby resolving a question of Brualdi (1980).
Related
- Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density
- Connected ω-limit sets of Cournot maps: periodic orbits, realization and almost every point
- Every Nonrecursive Many-One Degree Contains Either One or Infinitely Many Finite-One Degrees
- Structural stability of the Jouanolou foliations in every degree
- Counterexamples to the Mu--Welker recursive decomposition in every degree
BibTeX
@misc{hladik2026realization,
title = {{The realization graph of every degree sequence has a Hamilton path}},
author = {Petr Hladík and Jiří Fink},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.18146},
eprint = {2607.18146},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.18146},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - The realization graph of every degree sequence has a Hamilton path
AU - Petr Hladík
AU - Jiří Fink
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2607.18146
UR - https://arxiv.org/abs/2607.18146
AB - For a degree sequence d, the realization graph 𝒢_ℱ(d) is the graph whose vertices are the labeled realizations of d, two of which are adjacent if they differ by a single $2$-switch. We prove that for every degree sequence d and every realization S of d, the graph 𝒢_ℱ(d) contains a Hamilton path starting at S. This answers a question of Barrus (2016), which was also raised independently by Mütze (2023) in his survey of combinatorial Gray codes. As a consequence, an embedding observation of Arikati and Peled (1999) implies that for any vectors R and C of non-negative integers, the interchange graph 𝒜_ℱ(R,C) of (0,1)-matrices with row sums R and column sums C contains a Hamilton path starting at any prescribed matrix, thereby resolving a question of Brualdi (1980).
ER -