主题
数学天地
Search

Lovász 猜想


Lovász 猜想(在其最常见的形式中)指出,毫无例外,每个连通顶点传递图都是可迹的 (Lovász 1970; cf. Gould 1991; Godsil and Royle 2001, p. 45; Mütze 2024)。

有趣的是,Babai (1979, 1996) 发表了一个直接矛盾的猜想。

Thomassen (Bermond 1979, Gould 1991) 提出的一个类似猜想断言,除了五个例外(非哈密顿顶点传递图)之外,每个顶点传递图都是哈密顿图

虽然 Lovász 猜想随后已针对几个特殊阶数和类别进行了验证,但这两个猜想仍然是开放的。


另请参阅

哈密顿环, 哈密顿图, 哈密顿路径, 非哈密顿顶点传递图, 可迹图, 顶点传递图

使用 探索

参考文献

Babai, L. 问题 17,载于 "Unsolved Problems." Summer Research Workshop in Algebraic Combinatorics. Burnaby, Canada: Simon Fraser University, 1979 年 7 月。Babai, L. "Automorphism Groups, Isomorphism, Reconstruction." 第 27 章,载于 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." 第 6 章,载于 Selected Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson)。 London: Academic Press, pp. 127-167, 1979。Godsil, C. 和 Royle, G. "Hamilton Paths and Cycles." C§3.6,载于 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。Lovász, L. 问题 11,载于 "Combinatorial Structures and Their Applications." Proc. Calgary Internat. Conf. Calgary, Alberta, 1969. London: Gordon and Breach, pp. 243-246, 1970。Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024。

请引用为

Weisstein, Eric W. “Lovász 猜想。” 来自 -- 资源。 https://mathworld.net.cn/LovaszConjecture.html

主题分类