英文标题：Maximal Hamiltonicity of realization graphs of degree sequences
作者：Jeffrey S. Baggett
arXiv ID：2609.08007 | 分类：math.CO | 发表：2026-09-07
许可：CC-BY
摘要 我们证明每个可图度序列的实现图都是最大哈密顿的：当它二部且顶点数多于一个时是哈密顿-花边的，否则是哈密顿-连通的。这回答了 Mütze 的组合格雷码综述 [24] 中的问题 P59，以及 Barrus [5] 记录为公开的哈密顿性问题，且是该问题所能容许的最强形式。论证是对基顶点数的归纳，将实现图在单个基顶点处切割为纤维以及它们所位于的商图。该证明在 Lean 4 中形式化并由其内核检查，引用了文献中的七个结果，除此之外没有其他假设。 其引擎是一个分类。一个基顶点的可实现邻域构成一个移位族——即在将元素替换为更小元素下封闭的族——而商图是该族的 Johnson 图。这样的 Johnson
We prove that the realization graph of every graphical degree sequence is maximally Hamiltonian: it is Hamilton-laceable when bipartite on more than one vertex, and Hamilton-connected otherwise. This answers Problem P59 of Mütze's survey of combinatorial Gray codes, and the Hamiltonicity question recorded as open by Barrus, in the strongest form either admits. The argument is an induction on the number of ground vertices, cutting the realization graph at a single ground vertex into fibers and the quotient they lie over. The proof is formalized in Lean 4 and checked by its kernel, with seven results cited from the literature and nothing else assumed. Its engine is a classification. The realizable neighborhoods of a ground vertex form a shifted family -- one closed under replacing an element by a smaller one -- and the quotient is the Johnson graph of that family. Such a Johnson graph can fail to be Hamilton-connected, and we determine exactly when: the failures are one explicit family of examples, the Y-families, and each of them fails between a single pair of its members. A shifted family with a greatest member never fails, and those families are exactly the shifted matroids, where the conclusion already follows from the theorem of Naddef and Pulleyblank on the graphs of 0/1-polytopes. The obstruction lives entirely outside the matroid case, which is why it has not been met before.
查看完整双语翻译 →
正在跳转到翻译阅读页… 如果没有自动跳转，请点击这里。