几乎次哈密顿图 -- 来自 Wolfram MathWorld

几乎次哈密顿图

几乎次哈密顿图是一个非哈密顿图，其顶点删除子图是哈密顿图，但恰好有一个例外。具体来说，如果存在一个顶点，则图是几乎次哈密顿图，使得是非哈密顿图，但对于所有顶点，是哈密顿图。顶点可以称为“例外顶点”（Goedgebeur 和 Zamfirescu1 2019，Tsai 2024）。

Wiener（2018）给出了顶点数为 31 和 36 的平面几乎次哈密顿图的例子。 Zamfirescu（2019）证明了每个平面几乎次哈密顿图都有一个三次顶点，该顶点不是例外顶点（Tsai 2024）。

Zamfirescu（2015）找到了最小的几乎次哈密顿图，它有 17 个顶点（Zamfirescu 2015，Goedgebeur 和 Zamfirescu 2019）。 Goedgebeur 和 Zamfirescu1（2019）找到了围长为 4 的最小的几乎次哈密顿图，它有 18 个顶点。

目前尚不清楚是否存在围长为 3 的平面几乎次哈密顿图（Goedgebeur 和 Zamfirescu 2019，Tsai 2014）。

下表总结了满足各种标准的最小的几乎次哈密顿图（Goedgebeur 和 Zamfirescu 2019）。

参考文献

Goedgebeur, J. 和 Zamfirescu, C. T. "On Almost Hypohamiltonian Graphs." Disc. Math. Theor. Comput. Sci. 21, #5, 2019.

Tsai, C.-C. "Small Planar Hypohamiltonian Graphs." 2024 年 4 月 8 日. https://arxiv.org/abs/2403.18384.

Wiener, G. "New Constructions of Hypohamiltonian and Hypotraceable Graphs." J. Graph Th. 87, 526-535, 2018.

Zamfirescu, C. T. "On Hypohamiltonian and Almost Hypohamiltonian Graphs." J. Graph Th. 79, 63-81, 2015.

Zamfirescu, C. T. "Cubic Vertices in Planar Hypohamiltonian Graphs." J. Graph Th. 90, 189-207, 2019.

几乎次哈密顿图