九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

洛瓦兹顶点传递图哈密顿猜想

《图论中的 50 个公开问题》 · 问题 26 专题综述

题面每个连通顶点传递图都有哈密顿路吗?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

洛瓦兹 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 例外之外全有圈» 三十余年无新反例出现,共识强烈偏向真,但统一技术缺席。

← 返回问题 26