主題
Search

Pósa 猜想


Dirac (1952) 證明了,如果對於一個在 n>=3 個節點上的圖 G,其最小頂點度 delta(G)>=n/2,那麼 G 包含一個 哈密頓環 (Bollobás 1978, Komlós et al. 1996)。

在 1962 年,Pósa 猜想如果 delta(G)>=2n/3,則 G(V,E) 包含一個 哈密頓環 的平方 (Erdős 1964, p. 159; Komlós et al. 1996),其中圖 G(V,E) 包含 哈密頓環平方,如果存在一個 哈密頓環 H=(x_1,x_2,...,x_n,x_(n+1)=x_1) 使得 (x_i,x_(i+2)) in E(G),對於 i=1, 2, ..., n

Komlós et al. (1996) 證明了存在一個自然數 n_0,使得如果一個圖 G 的階為 n>=n_0 並且最小頂點度至少為 2n/3,那麼 G 包含哈密頓環的平方。這證明了對於足夠大的 n,Pósa 猜想成立 (Erdős 1964)。 Kierstead 和 Quintana (1998) 證明了對於包含 4-團 K_4 的圖 G,Pósa 猜想成立。

Seymour (1974) 將該猜想推廣為:如果 delta(G)>=kn/(k+1),那麼 G 包含 哈密頓環k 次冪 (Komlós et al. 1996)。


參見

哈密頓環, Pósa 定理, Seymour 猜想

使用 探索

參考文獻

Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.Dirac, G. A. "Some Theorems on Abstract Graphs." Proc. London Math. Soc. 2, 69-81, 1952.Erdős, P. "Problem 9." In Theory of Graphs and Its Applications, Proceedings of the Symposium held in Smolenice in June 1963 (Ed. M. Fiedler). Prague, Czechoslovakia: Publishing House of the Czechoslovak Academy of Sciences, p. 159, 1964.Fan, G. and Kierstead, H. A. "Hamiltonian Square-Paths." J. Combin. Theory Ser. B 67, 167-182, 1996.Kierstead, H. A. and Quintana, J. "Square Hamiltonian Cycles in Graphs with Maximal 4-Cliques." Disc. Math. 178, 81-92, 1998.Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "On the Square of a Hamiltonian Cycle in Dense Graphs." In Random Structures Algorithms 9, 193-211, 1996.Seymour, P. Problem Section in Combinatorics: Proceedings of the British Combinatorial Conference, 1973 (Ed. T. P. McDonough and V. C. Mavron). Cambridge, England: Cambridge University Press, pp. 201-202, 1974.

在 上被引用

Pósa 猜想

引用為

Weisstein, Eric W. "Pósa's Conjecture." 出自 --一個 Wolfram 網路資源。 https://mathworld.tw/PosasConjecture.html

主題分類