主題
Search

平面次哈密頓圖

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook
PlanarHypohamiltonianGraphs

平面次哈密頓圖是一個次哈密頓圖，同時也是平面圖。上面展示了一些平面次哈密頓圖。

Chvátal (1973) 首次提出是否存在平面次哈密頓圖的問題，實際上有人推測這類圖可能不存在 (Grünbaum 1974, Jooyandeh 等人 2017)。Thomassen (1976) 隨後發現了一個無限族，其中最小的圖有 105 個頂點。下表總結了已知最小的平面次哈密頓圖（按頂點數遞增排序）。

頂點數圖參考文獻
9494-Thomassen 圖
57Hatzel 圖Hatzel (1979)
4848-Zamfirescu 圖Zamfirescu 和 Zamfirescu (2007)
42Wiener-Araya 圖Wiener 和 Araya (2009)
42179 個圖Jooyandeh 等人 (2017)
4025 個圖Jooyandeh 等人 (2017)
382 個圖Tsai (2024)
376 個圖Tsai (2024)
342 個圖Tsai (2024)

Jooyandeh 等人 (2017) 搜尋了“平面 4-面可收縮次哈密頓圖”，發現 40 個頂點的圖有 25 個（周長均為 4），42 個頂點的圖有 179 個（包括 Wiener-Araya 圖），以及 43 個頂點的圖有 496 個。他們還證明了對於每個 n>=42 的 n，都存在 n 階平面次哈密頓圖 (Jooyandeh 等人 2017)，Tsai (2024) 隨後將這一結果改進為 n>=40。目前尚不清楚 34 是否是平面次哈密頓圖的最小頂點數，目前已知的最佳下界是 23 (Goedgebeur 和 Zamfirescu 2017；改進了 Aldred 等人 1997 年、Jooyandeh 等人 2017 年的先前界限)。

PlanarHypohamiltonianGraph45

不存在周長為 5 且頂點數少於 45 的次哈密頓平面圖，且在 45 個頂點的圖中恰好存在一個這樣的圖 (Jooyandeh 等人 2017)，如上所示。

Thomassen (1976, 1978) 證明了每個平面次哈密頓圖都包含一個度為 3 的頂點，Zamfirescu (2019) 證明了每個平面次哈密頓圖都至少包含四個三次頂點 (Tsai 2024)。

令 kappa(G) 為頂點連通度，delta(G) 為最小頂點度，以及 lambda(G) 為平面次哈密頓圖 G 的邊連通度，

kappa(G)=lambda(G)=delta(G)=3

(Jooyandeh 等人 2017)。此外，平面次哈密頓圖的周長最多為 5 (Jooyandeh 等人 2017)。

Araya 和 Wiener (2011)、McKay 和 Jooyandeh (McKay) 以及 Tsai (2024) 發現了一些三次平面次哈密頓圖。

另請參閱

三次平面次哈密頓圖, Hatzel 圖, 次哈密頓圖, 平面圖, 平面次可跡圖, Thomassen 圖, Wiener-Araya 圖, Zamfirescu 圖

使用 探索

參考文獻

Aldred, R. E. L.; Bau, S.; Holton, D. A.; and McKay, B. D. "Nonhamiltonian 3-Connected Cubic Planar Graphs." SIAM J. Disc. Math. 13, 25-32, 2000.Aldred, R. E. L.; McKay, B. D.; and Wormald, N. C. "Small Hypohamiltonian Graphs." J. Combin. Math. Combin. Comput. 23, 143-152, 1997.Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin. 18, 2011. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Chvátal, V. "Flip-Flops in Hypohamiltonian Graphs." Canad. Math. Bull. 16, 33-41, 1973.Goedgebeur, J. and Zamfirescu, C. T. "Improved Bounds for Hypohamiltonian Graphs." Ars Math. Contemp. 13, 235-257, 2017.Gruünbaum, B. "Vertices Missed by Longest Paths or Circuits." J. Combin. Th. 17, 31-38, 1974.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Jooyandeh, M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.; and Zamfirescu, C. T. "Planar Hypohamiltonian Graphs on 40 Vertices." J. Graph Th. 84, 121-133, 2017.McKay, B. D. "Plane Graphs: Hypohamiltonian Planar Graphs." http://users.cecs.anu.edu.au/~bdm/data/planegraphs.html.Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs." Disc. Math. 9, 91-96, 1974.Thomassen, C. "On Hypohamiltonian Graphs." Disc. Math. 10, 383-390, 1974.Thomassen, C. "Planar and Infinite Hypohamiltonian and Hypotraceable Graphs." Disc. Math 14, 377-389, 1976.Thomassen, C. "Hypohamiltonian Graphs and Digraphs." In Theory and Applications of Graphs Proceedings, Michigan May 11-15, 1976 (Ed. Y. Alavi and D. R. Lick). New York: Springer-Verlag, pp. 557-571, 1978.Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb. Th. B 30, 36-44, 1981.Tsai, C.-C. "Small Planar Hypohamiltonian Graphs." 8 Apr 2024. https://arxiv.org/abs/2403.18384.Wiener, G. and Araya, M. "The Ultimate Question." 20 Apr 2009. http://arxiv.org/abs/0904.3012.Wiener, G. and Araya, M. "On Planar Hypohamiltonian Graphs." J. Graph Th. 67, 55-68, 2011.Zamfirescu, C. T. and Zamfirescu, T. I. "A Planar Hypohamiltonian Graph with 48 Vertices." J. Graph Th. 48, 338-342, 2007.Zamfirescu, C. T. "Cubic Vertices in Planar Hypohamiltonian Graphs." J. Graph Th. 90, 189-207, 2019.

請引用本文為

Weisstein, Eric W. "平面次哈密頓圖。" 來自 Web 資源。 https://mathworld.tw/PlanarHypohamiltonianGraph.html

主題分類