问题
凯莱图 Cay(G, S):顶点为群元素,g 与 gs(s ∈ S)连边。猜想(Lovász 1969 提出,常归 Lovász 或 «凯莱哈密顿»):除 K₂ 外每个连通凯莱图有哈密顿圈。它比 26 号(顶点传递版)强——凯莱图是顶点传递的特例,而 5 个已知顶点传递反例都不是凯莱图,故凯莱版字面成立的可能性更大。
主要概念
群结构如何 «养» 出圈
哈密顿圈在凯莱图里 = 群元素的枚举 g₁ = e, g₂, …, gn,相邻者差一个生成元,且 gns = e——即 «生成元序列» s₁s₂⋯sn−1 恰遍历群各一次。这叫 «列举»(sequential listing):把哈密顿性翻译成 «群可被生成元字单射遍历»,组合群论的 «Gray 码» 传统由此而生(反射 Gray 码 = ℤ/2k 的列举)。
交换情形的圈因子焊接
交换群 = 循环群之积;每个循环因子给 «内圈»,Chen–Quimpo 的 «焊接» 把内圈串成总圈(26 号命题 1)。非交换的困难:子群结构不再 «整齐»,极小生成元的 «阶梯» 会 «回头»——需要 «回文拼接» 或 «公转自转» 技巧。
主要命题与证明
命题 1(Chen–Quimpo 完整证明骨架,1976) 有限交换群 G 的连通凯莱图(≠ K₂)有哈密顿圈。
梗概(阶梯构造) 取极小生成集 s₁, …, sk(阶 n₁, …, nk)。阶梯:H₁ = ⟨s₁⟩ 的圈;从 Hj 到 Hj+1 = Hj⟨sj+1⟩:若 gcd(nj+1, |Hj|) 有余量,用 «sj+1 每走一步回串一整圈» 的螺旋;否则 «两圈并排» 的梯形(含 2 的因子时用 «扭 » 变体)。交换性保证螺旋与梯形 «不回头»——每步元素唯一。归纳到底。□
命题 2(一般群的主要结果) ①p-群的每个连通凯莱图有哈密顿圈(Witte 1986:经 «中心阶梯»——中心循环扩张型阶梯在 p-群中 «抬得动»);②几乎所有生成集下凯莱图哈密顿(Krivelevich 等的概率型);③二面体群、对称群的多数族、Coxeter 群的 «标准生成» 情形逐类已证。
进展与文献
Lovász 1969 问题 11;Chen–Quimpo《Hamilton cycles in Cayley graphs of abelian groups》;Witte(Cayley 图哈密顿性综述,收录 «已知正结果覆盖的群类» 长清单);Conder–Richter 的 «几乎全哈密顿» 概率线。开放核心:非交换一般情形五十余年—— «无一个凯莱反例» 的事实与 «无统一技术» 的僵局并存;与 26 号、38 号(凯莱直径)、41 号(CI)同属凯莱图四大前沿。