哈密顿分解

哈密顿分解（也称为 Hamiltonian 分解；Bosák 1990, p. 123）是指将哈密顿正则图的边集划分为哈密顿环。上图展示了五胞体图 的六种不同的哈密顿分解。

该定义有时会扩展到将偶数度正则图分解为哈密顿环，或将奇数度正则图分解为哈密顿环和一个完美匹配（Alspach 2010），后一种类型的分解被称为准哈密顿分解（quasi-Hamilton decomposition）（Bosák 1990, p. 123）。

对于三次图，哈密顿分解等价于单个哈密顿环。对于四次图，哈密顿分解等价于一个哈密顿环 ，移除该环的边后会留下一个连通图。当这个连通图存在时，它给出了构成哈密顿分解 的一对哈密顿环中的第二个环 。对四次图的所有哈密顿环迭代此过程会生成每个哈密顿分解两次，对应于两种不同的排序 和 。

在 19 世纪 90 年代，Walecki 证明了完全图 当 为奇数时，允许哈密顿分解；当 为偶数时，允许分解为哈密顿环加上一个完美匹配（Lucas 1892, Bryant 2007, Alspach 2008）。

1954 年，Ringel 证明了当 是 2 的幂时，超立方体图 允许哈密顿分解（Alspach 2010）。Alspach et al. (1990) 证明了每个 对于 都允许哈密顿分解。

Laskar 和 Auerbach (1976) 证明了完全二部图 在度数为偶数时具有（真）哈密顿分解。事实上， 具有真哈密顿分解当且仅当 且 为偶数时；具有准哈密顿分解当且仅当 且 为奇数时（Bosák 1990, p. 124）。更一般地，完全 部图 ，其中 ，具有哈密顿[准哈密顿]分解当且仅当 且 为偶数[奇数]时（Bosák 1990, p. 124）。

Alspach et al. (2012) 证明了 Paley 图允许哈密顿分解。

Kotzig (1964) 证明了三次图是哈密顿图当且仅当它的线图具有哈密顿分解时（Bryant 和 Dean 2014）。

找到非哈密顿可分解的正则哈密顿非顶点传递图并不太难，如上面的例子所示。

要描述非哈密顿可分解的正则哈密顿顶点传递图则更为困难。S. Wagon（私人通信，2013 年 2 月；Dupuis 和 Wagon 2014）曾推测，所有连通顶点传递图都是哈密顿可分解的，但以下情况除外：、、、、 和 。其中， 表示 Petersen 图， 表示 Coxeter 图， 表示 的三角形替换图， 表示 的线图。根据 Kotzig (1964) 的定理，Bryant 和 Dean (2014) 将 添加到此列表。因此，该猜想可以更简单地表述为：“除了 和 之外，每个哈密顿顶点传递图都具有哈密顿分解”，该猜想已在节点数不超过 的情况下得到验证。（可以用 H-*-连通图来对该猜想进行稍微更通用和精确的陈述。）

然而，Bryant 和 Dean (2014) 反驳了该猜想，他们证明存在无限多个没有哈密顿分解的连通顶点传递图，其中包括无限多个顶点度为 6 的图，以及顶点度数任意大的Cayley 图。反例来自于将三角形替换图推广到 替换 正则图，最小的反例是由从立方图 的边加倍得到的多重图获得的 替换图给出。一般来说， 和 是反例，其中 表示通过取 份 的边而得到的多重图，， 表示对 进行 顶点替换操作，并且 是 Möbius-Kantor 图（Bryant 和 Dean 2014）。