幾乎次哈密頓圖 -- 來自

幾乎次哈密頓圖

幾乎次哈密頓圖是一個非哈密頓圖，其頂點刪除子圖是哈密頓圖，但恰好有一個例外。具體來說，如果存在一個頂點，則圖是幾乎次哈密頓圖，使得是非哈密頓圖，但對於所有頂點，是哈密頓圖。頂點可以稱為“例外頂點”（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.

幾乎次哈密頓圖