主題
Search

克內澤爾圖

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
KneserGraphs

克內澤爾圖是由 Lovász (1978) 引入的一類圖，用於證明克內澤爾猜想。給定兩個正整數 n 和 k，克內澤爾圖 K(n,k)，常表示為 K_(n:k) (Godsil 和 Royle 2001; Pirnazar 和 Ullman 2002; Scheinerman 和 Ullman 2011, pp. 31-32)，是頂點表示集合 {1,...,n} 的 k-子集的圖，其中兩個頂點相連當且僅當它們對應於不相交的子集。K(n,k) 因此有 (n; k) 個頂點，並且是度數為 (n-k; k) 的正則圖。

當 n>2k 時，K(n,k) 是連通的。對於非空克內澤爾圖 (即，n!=k+1)，色數由 n-2k+2 給出，這是由 Kneser (1956) 猜想的，並由 Lovász (1978)、Bárány (1978)、Greene (2002) 和 Matoušek (2004) 證明的。

K(n,k) 的團數是

omega(K(n,k))=|_n/k_|.
(1)

這結論來自 Baranyai 定理的推廣，Brouwer 和 Schrijver (1979) 證明了當 k|n 時，omega(K(n,k))=(n-1; k-1)。因此，團覆蓋數是

theta(K(n,k))=[(|K(n,k)|)/(omega(K(n,k)))]
(2)
=[((n; k))/(|_n/k_|)]
(3)

(S. Wagon, 私人通訊, 2013年2月12日)。非空克內澤爾圖 K(n,k) 的分數色數是 n/k (Scheinerman 和 Ullman 2011, p. 32)。

類似地，非空克內澤爾圖的獨立數由下式給出

alpha(K(n,k))=(n-1; k-1)
(4)

根據 Erdős-Ko-Rado 定理 (Aigner 和 Ziegler 2000, p.  251)。

Östergård 等人 (2015) 給出了克內澤爾圖的支配數的界限，以及一些較小情況下的精確值。

克內澤爾圖是奇圖的推廣，其中奇圖 O_n 對應於 K(2n-1,n-1)。特殊情況總結在下表中。

K(n,k)特例
K(5,2)Petersen 圖
K(n,1)n-完全圖 K_n
K(n,n-1)n-空圖 K^__n
K(2n,n)梯形 rung 圖 P_2 square P_((2n; n))

克內澤爾圖 K(n,2) 是距離正則圖，其相交陣列為 {(n-2)(n-3)/2,2n-8;1,(n-3)(n-4)/2}。

Chen 和 Lih (1987) 證明了 K(n,k) 是對稱的。長期以來一直有人猜測，對於 n>2k，K(n,k) 是哈密頓圖（除了 K(5,2)），Shields 和 Savage (2004) 對 n<=27 驗證了這一點。

K(7,2) 是三個區域性 Petersen 圖之一 (Hall 1980)。

K(n,k) 的二部雙圖是二部克內澤爾圖 H(n,k)。

(n,k)-克內澤爾圖在 Wolfram 語言中實現為GraphData[{"Kneser", {n, k}}].

另請參閱

二部克內澤爾圖, 克內澤爾猜想, 區域性 Petersen 圖, 奇圖, Petersen 圖

此條目部分內容由 Margherita Barile 貢獻

使用 探索

參考文獻

Aigner, M. 和 Ziegler, G. M. "Kneser 圖的色數。" 第 38 章，《來自書中的證明》，第二版。 紐約：Springer-Verlag, pp. 251-256, 2000.Bárány, I. "克內澤爾猜想的簡短證明。" J. Combin. Th., Ser. A 25, 325-326, 1978.Brouwer, A. E. "克內澤爾圖。" http://www.win.tue.nl/~aeb/drg/graphs/Kneser.html.Brouwer, A. E. 和 Schrijver, A. "均勻超圖。" 在 組合學中的填充和覆蓋。 Mathematical Centre Tracts, No. 106, pp. 39-73, 1979.Chen, Y.-C. "對於 n>=3k 克內澤爾圖是哈密頓圖。" J. Combin. Th. Ser. B 80, 69-79, 2000.Chen, B. L. 和 Lih, K.-W. "哈密頓均勻子集圖。" J. Combin. Th. Ser. B 42, 257-263, 1987.DistanceRegular.org. "克內澤爾圖。" http://www.distanceregular.org/indexes/knesergraphs.html.Godsil, C. 和 Royle, G. "克內澤爾圖。" 第 7 章，代數圖論。 紐約：Springer-Verlag, pp. 135-161, 2001.Greene, J. E. "克內澤爾猜想的新簡短證明。" Amer. Math. Monthly 109, 918-920, 2002.Hall, J. I. "區域性 Petersen 圖。" J. Graph Th. 4, 173-187, 1980.Heinrich, K. 和 Wallis, W. D. "某些圖中的哈密頓圈。" J. Austral. Math. Soc. Ser. A 2, 89-98, 1978.Kneser, M. "Aufgabe 300." Jahresber. Deutsch. Math.-Verein 58, 1955.Lovász, L. "克內澤爾猜想、色數和同倫。" J. Comb. Th. A 25, 319-324, 1978.Matoušek, J. "克內澤爾猜想的組合證明。" Combinatorica 24, 163-170, 2004.Mütze, T. "關於由相交集系統定義的圖中的哈密頓環。" Not. Amer. Soc. 74, 583-592, 2024.Östergård, P. R. J.; Shao, Z.; 和 Xu, X. "克內澤爾圖的支配數界限。" Ars Math. Contemp. 9, 197-205, 2015.Phillips, D. "克內澤爾圖最大鄰域單純形。" http://www.ucalgary.ca/~phillips/users/sali/kneser.html.Pirnazar, A. 和 Ullman, D. H. "平面圖的圍長和分數色數。" J. Graph Th. 39, 201-217, 2002.Scheinerman, E. R. 和 Ullman, D. H. 分數圖論：圖論的理性方法。 紐約：Dover, 2011.Shields, I. 和 Savage, C. D. "關於克內澤爾圖中的哈密頓環的註釋。" Bull. Inst. Combin. Appl. 40, 13-22, 2004.

在 上被引用

克內澤爾圖

引用為

Barile, Margherita 和 Weisstein, Eric W. "克內澤爾圖。" 來自 Web 資源。 https://mathworld.tw/KneserGraph.html

主題分類