主题
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 图

使用 Wolfram|Alpha 探索

参考文献

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. "平面次哈密顿图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PlanarHypohamiltonianGraph.html

主题分类