主题
Search

非哈密顿顶点传递图


VertexTransitiveNonhamiltonian

目前已知恰好有五个 连通 非哈密顿 顶点传递图,即 路径图 P_2彼得森图 F_(010)A考克斯特图 F_(028)A三角形替换 彼得森图三角形替换 考克斯特图。正如 Gould (1991) 引用 Bermond (1979) 所述,Thomassen 推测所有其他 连通 顶点传递图 都是 哈密顿图(参见 Godsil 和 Royle 2001,第 45 页;Mütze 2024)。相比之下,Babai (1979, 1996) 推测存在无限多个连通的非哈密顿顶点传递图。

证实或反驳 Thomassen 的猜想仍然是一个困难的开放性问题,中间层猜想 证明的事实就证明了这一点,该猜想假设 中间层图哈密顿图,而该猜想只是在最近才被证明(Mütze 2016, Mütze 2024)。

一个稍微弱一点的猜想是所有 凯莱图 都是哈密顿图 (Royle)。反之,所有 凯莱图 都是顶点传递的。

Alspach (1979) 证明了阶数为 2p 的每个连通 顶点传递图 (除了 彼得森图) 都是 哈密顿图。Marušič (1982) 证明了阶数为 p^2p^32p^23p 的每个连通顶点传递图都是 哈密顿图,而 Marušič 和 Parsons (1983) 表明阶数为 4p5p 的连通顶点传递图是 可追踪的 (Gould 1991)。


参见

凯莱图, 哈密顿分解, 哈密顿图, 洛瓦兹猜想, 中间层猜想, 中间层图, 非哈密顿图, 三角形替换图, 顶点传递图

使用 Wolfram|Alpha 探索

参考文献

Babai, L. Problem 17 in "Unsolved Problems." In Summer Research Workshop in Algebraic Combinatorics. Simon Fraser University, Jul. 1979.Babai, L. "Automorphism Groups, Isomorphism, Reconstruction." Ch. 27 in Handbook of Combinatorics, Vol. 2 (Ed. R. L. Graham, M. Grötschel, M.; and L. Lovász). Cambridge, MA: MIT Press, pp. 1447-1540, 1996.Bermond, J.-C. "Hamiltonian Graphs." Ch. 6 in Selected Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson). London: Academic Press, pp. 127-167, 1979.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, 1976.Bryant, D. and Dean, M. "Vertex-Transitive Graphs that have no Hamilton Decomposition." 25 Aug 2014. http://arxiv.org/abs/1408.5211.Godsil, C. and Royle, G. "Hamilton Paths and Cycles." C§3.6 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 45-47, 2001.Gould, R. J. "Updating the Hamiltonian Problem--A Survey." J. Graph Th. 15, 121-157, 1991.Kutnar, K. and Marušič, D. "Hamilton Cycles and Paths in Vertex-Transitive Graphs-Current Directions." Disc. Math. 309, 5491-5500, 2009.Lipman, M. "Hamiltonian Cycles and Paths in Vertex-Transitive Graphs with Abelian and Nilpotent Groups." Disc. Math. 54, 15-21, 1985.Marušič, D. "Hamiltonian Paths in Vertex-Symmetric Graphs of Order 5p." Disc. Math. 42, 227-242, 1982.Marušič, D. and Parsons, T. D. "Hamiltonian Paths in Vertex-Symmetric Graphs of Order 4p." Disc. Math. 43, 91-96, 1983.Mütze, T. "Proof of the Middle Levels Conjecture." Proc. Lond. Math. Soc. 112, 677-713, 2016.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Royle, G. "Transitive Graphs." http://school.maths.uwa.edu.au/~gordon/trans/.Thomassen, C. "Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface." Trans. Amer. Math. Soc. 323 605-635, 1991.

请引用为

Weisstein, Eric W. "非哈密顿顶点传递图。" 来自 MathWorld-- Wolfram Web 资源。 https://mathworld.net.cn/NonhamiltonianVertex-TransitiveGraph.html

主题分类