问题
洛瓦兹 1969 年猜想:每个连通顶点传递图都有哈密顿路;加强版:除 5 个已知例外,每个连通顶点传递图都有哈密顿圈。5 个例外:皮特森图、考克斯特图、以及三个 1950–60 年代发现的散例——它们都有哈密顿路、都缺哈密顿圈。
主要概念
顶点传递的 «旋转余量»
顶点传递 = 存在自同构群在顶点上传递。对称性给哈密顿性 «留余量» 的直觉:传递图 «处处一样»,一条走到底的长路径只要 «各处都不撞墙» 就能延伸。技术化余量来自 «自同构把路径推到新起点» 的平移论证。凯莱图(27 号)是最对称的子类:群元当顶点、生成集当边。
例外五人组
皮特森图(10 点 3 度)、考克斯特图(30 点 3 度)等——全为三次图,皆 «非哈密顿但有哈密顿路»。它们的 «非哈密顿性» 各有独立证明(皮特森:完美匹配结构;考克斯特:距离正则谱分析),共性是 «三次 + 高对称 + 小直径» 的张力。
主要命题与证明
命题 1(交换凯莱图,Chen–Quimpo 定理完整陈述) 有限交换群 G 的连通凯莱图(除 K₂ 外)有哈密顿圈;更强:两个交换凯莱图的笛卡尔积有哈密顿圈。
梗概 交换凯莱图可分解为 «圈因子»(每个生成元的循环子群给出圈);圈的 «错位乘积» 技巧:两圈 Cm, Cn 的笛卡尔积有哈密顿圈当 gcd(m,n) 配合(«梯形扭一圈» 的显式构造);归纳拼接所有圈因子。核心引理(«Rankin 型»):交换群的任何极小生成集给出的圈因子可 «边到边» 焊接。□
命题 2(一般凯莱图的主要正结果) ①任意群 + 生成集含 «大循环» 时哈密顿(Witte:p-群的凯莱图有哈密顿圈——经 «幂拼接»);②几乎所有凯莱图哈密顿(对随机生成集的概率 1);③三次顶点传递图除已知例外全哈密顿(经结构二分:弧传递分解到 «环面型» 与 «扩展型»,分别承圈)。
进展与文献
洛瓦兹 1969 原文(问题形式);Lovász《Problem 11 in Combinatorial Problems and Exercises》;Chen–Quimpo 1976/1981 的交换定理;Witte 1986 的 p-群定理;Pak–Radoičić 的 «几乎全哈密顿» 概率结果;Kratochvíl–Nesetřil–... 与 Witte–Morris 的凯莱图哈密顿性综述(收录数百个正结果家族)。开放核心:一般凯莱圈(27 号)与顶点传递圈(本问)的最后一步—— «5 例外之外全有圈» 三十余年无新反例出现,共识强烈偏向真,但统一技术缺席。