主題
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.tw/LovaszConjecture.html

主題分類