主題
Search

二部 Kneser 圖

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

給定兩個正整數 n 和 k，二部 Kneser 圖 H(n,k) 是這樣一個圖，其兩個二分頂點集分別代表 {1,...,n} 的 k-子集和 (n-k)-子集，其中兩個頂點相連當且僅當它們位於不同的集合中，且其中一個是另一個的 子集。 H(n,k) 因此有 2(n; k) 個頂點，且是 (n-k; k) 度正則圖。

根據定義，H(n,k) 同構於 H(n,n-k)。

H(n,k) 是 Kneser 圖 K(n,k) 的二部雙圖。

H(n,k) 在 n>2k 時是連通的。Simpson (1991) 證明了二部 Kneser 圖是對稱的。 Shields 和 Savage 證明了 H(k,n) 在 n<=27 時是哈密頓圖。

H(n,1) 同構於 n-冠圖，H(2k,k) 同構於 (2k; k)-階梯橫檔圖，且 H(2k-1,k-1) 同構於奇圖 O(k) 的二部雙圖。後一類圖是距離傳遞的，因此也是距離正則的 (Brouwer 等人，1989，第 222 頁)。

特殊情況總結在下表中。

H(n,k)圖
H(3,1)圈圖 C_6
H(4,1)立方圖 Q_3
H(5,2)Desargues 圖 GP(10,3)
H(7,3)Danzer 圖
H(n,1)冠圖 K_2 square K_n^_
H(2k-1,k-1)奇圖的二部雙圖 奇圖 O(k)
H(2k,k)(2n; n)-階梯橫檔圖
H(2k+1,k)中間層圖

長期以來，人們一直猜想 H(n,k) 在 n>2k 時是哈密頓圖，Shields 和 Savage 驗證了 n<=27 時的情況。

(n,k)-二部 Kneser 圖在 Wolfram 語言中實現為GraphData[{"BipartiteKneser", {n, k}}].

另請參閱

二部雙圖, 二部圖, 冠圖, Kneser 圖, 中間層圖

使用 探索

參考文獻

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.Chen, B. L. and Lih, K.-W. "Hamiltonian Uniform Subset Graphs." J. Combin. Th. Ser. B 42, 257-263, 1987.Dejter, I. J. "Some Hamilton Cycles in Bipartite Reflective Kneser Graphs." Technical Report. Univ. of Puerto Rico.Dejter, I. J.; Cordova, J.; and Quintana, J. A. "Two Hamilton Cycles in Bipartite Reflective Kneser Graphs." In Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986). Vol. 72, pp. 63-70, 1988.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Shields, I. and Savage, C. D. "A Note on Hamilton Cycles in Kneser Graphs." http://www.cybershields.com/publications/kneser3.pdf.Simpson, J. E. "Hamiltonian Bipartite Graphs." In Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991). Vol. 85, pp. 97-110, 1991.

在 上被引用

二部 Kneser 圖

請按如下方式引用

Weisstein, Eric W. “二部 Kneser 圖。” 來自 Web 資源。 https://mathworld.tw/BipartiteKneserGraph.html

主題分類