几乎哈密顿图 -- 来自

关于“几乎哈密顿”有几种不同的定义在使用。

根据 Punnim et al. (2007) 的定义，几乎哈密顿图是指在个节点上，具有哈密顿数的图。

根据 Sanders (1987) 的定义，具有个顶点的图，如果每个个顶点的子集都包含在一个回路中，则该图是几乎哈密顿图。这个定义类似于极大非哈密顿图的定义。

本文采用 Punnim et al. (2007) 的定义。此类型的几乎哈密顿图在 , 2, ... 个顶点上的数量分别为 0, 0, 1, 1, 7, 28, 257, 2933, ... (OEIS A185360)，其中前几个示例如上所示。

由于树的哈密顿数为，因此几乎哈密顿树满足，得出。由于 3-路径图是三个节点上唯一的树，因此它也是唯一的几乎哈密顿树。

次哈密顿图是几乎哈密顿图。许多（甚至可能全部？）snark 图都是几乎哈密顿图。

Punnim et al. (2007) 表明广义 Petersen 图是几乎哈密顿图，当且仅当且时成立。

Punnim et al. (2007) 证明了对于每个偶数阶，都存在几乎哈密顿三次图。Petersen 图是 10 个顶点上唯一几乎哈密顿三次图，Tietze 图是 12 个顶点上唯一几乎哈密顿三次图 (Punnim et al. 2007)。Punnim et al. (2007) 证明了个顶点上的三次非哈密顿图是几乎哈密顿图，当且仅当它 2-连通且包含长度为的环。下表总结了个顶点上缺少 -环，因此不是几乎哈密顿图的 2-连通三次非哈密顿图的示例。