主题
Search

Hypotraceable 图


一个图 G 是 hypotraceable 图,如果 G 没有 哈密顿路径 (即,它不是一个 可追踪图),但是对于每个 v in VG-v 都有一个 哈密顿路径 (即,是一个 可追踪图) (Bondy 和 Murty 1976, p. 61)。

HypotraceableGraphs

不存在节点数少于或等于 10 的 hypotraceable 图 (E. Weisstein, Dec. 11, 2013)。事实上,在少量顶点上不存在 hypotraceable 图导致 T. Gallai 推测这种图不存在。当 Horton 随后发现一个有 40 个顶点的 hypotraceable 图时,这个猜想被反驳了 (Grünbaum 1974, Thomassen 1974)。然后 Thomassen (1974) 表明,对于 p=34, 37, 39, 40,以及所有 p>=42,都存在具有 p 个顶点的 hypotraceable 图。其中最小的是 34 顶点的 Thomassen 图 (上图左侧;Thomassen 1974;Bondy 和 Murty 1976, pp. 239-240)。

Walter (1969) 给出了一个连通图的例子,其中最长路径没有共同的顶点,hypotraceable 图也具有此属性。

平面 hypotraceable 图是一类特别令人感兴趣的图。


另请参阅

哈密顿连通图, Hypohamiltonian 图, 平面 Hypotraceable 图, Thomassen 图, 可追踪图, Wiener-Araya 图, Zamfirescu 图

使用 Wolfram|Alpha 探索

参考文献

Araya, M. 和 Wiener, G. "关于三次平面 Hypohamiltonian 和 Hypotraceable 图。" 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. "关于单调对称旅行商问题:Hypohamiltonian/Hypotraceable 图和面。" 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 个顶点上的平面 Hypohamiltonian 图。" 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. "Hypohamiltonian 和 Hypotraceable 图。" Disc. Math. 9, 91-96, 1974.Walter, H. "关于图中所有最长路径都不经过某个顶点的非存在性。" J. Combin. Th. 6, 1-6, 1969.Wiener, G. 和 Araya, M. "终极问题。" 20 Apr 2009. http://arxiv.org/abs/0904.3012.Wiener, G. 和 Araya, M. "关于平面 Hypotraceable 图。" J. Graph Th. 67, 55-68, 2011.

在 Wolfram|Alpha 中被引用

Hypotraceable 图

请引用为

Weisstein, Eric W. "Hypotraceable 图。" 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/HypotraceableGraph.html

主题分类