主题
Search

平面次可迹图

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook
PlanarHypotraceableGraphs

平面次可迹图是一个次可迹图，同时也是平面图。上面展示了一些平面次可迹图。

根据 Thomassen (1974) 的一个定理，具有 42 个顶点的 Wiener-Araya 图 可以用来构造一个具有 162 个顶点的平面次可迹图，这比使用 Thomassen 构造从 48-Zamfirescu 图 获得的 186 顶点图要小。这些图在 Wolfram 语言 中实现为GraphData[{"PlanarHypohamiltonian", 162}] 和GraphData[{"PlanarHypohamiltonian", 186}]， 分别为。

Jooyandeh 等人 (2017) 表明，存在具有 154 个顶点的平面次可迹图，以及所有顶点数大于或等于 156 的平面次可迹图。

使用 70 节点的 Araya-Wiener 图，可以构造一个 340 节点的立方平面次可迹图 (Araya 和 Wiener 2011)。

Holton 和 Sheehan (1993) 询问是否存在一个整数 n，使得对于每个偶数 >=n 都存在立方平面次可迹图，而 Araya 和 Wiener (2011) 用 n=356 回答了这个问题。

另请参阅

哈密顿连通图, 次可迹图, 平面图, 平面次哈密顿图, Thomassen 图, 可迹图, Wiener-Araya 图, Zamfirescu 图

使用 Wolfram|Alpha 探索

参考文献

Araya, M. 和 Wiener, G. "关于立方平面次哈密顿图和次可迹图." Elec. J. Combin. 18, 2001. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Bondy, J. A. 和 Murty, U. S. R. 图论及其应用。 New York: North Holland, pp. 61 和 239-240, 1976.Grotschel, M. "关于单调对称旅行商问题：次哈密顿/次可迹图和面." Math. Operations Res. 5, 285-292, 1980.Grünbaum, B. "最长路径或回路遗漏的顶点." J. Combin. Th. A 17, 31-38, 1974.Holton, D. A. 和 Sheehan, J. 彼得森图。 Cambridge, England: Cambridge University Press, 1993.Jooyandeh, M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.; 和 Zamfirescu, C. T. "具有 40 个顶点的平面次哈密顿图." J. Graph Th. 84, 121-133, 2017.Kapoor, S. F.; Kronk, H. V.; 和 Lick, D. R. "关于图中的绕道." Canad. Math. Bull. 11, 195-201, 1968.Thomassen, C. "次哈密顿图和次可迹图." Disc. Math. 9, 91-96, 1974.Walter, H. "Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen." J. Combin. Th. 6, 1-6, 1969.Wiener, G. 和 Araya, M. "终极问题." 2009 年 4 月 20 日. http://arxiv.org/abs/0904.3012.Wiener, G. 和 Araya, M. "关于平面次可迹图." J. Graph Th. 67, 55-68, 2011.

请引用为

韦斯坦因，埃里克·W. "平面次可迹图。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/PlanarHypotraceableGraph.html

主题分类