主題
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)。


參見

凱萊圖, 哈密頓分解, 哈密頓圖, 洛瓦茲猜想, 中間層猜想, 中間層圖, 非哈密頓圖, 三角形替換圖, 頂點傳遞圖

使用 探索

參考文獻

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. "非哈密頓頂點傳遞圖。" 來自 -- 資源。 https://mathworld.tw/NonhamiltonianVertex-TransitiveGraph.html

主題分類