主题
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 图, 中间层图

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上被引用

二部 Kneser 图

请按如下方式引用

Weisstein, Eric W. “二部 Kneser 图。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/BipartiteKneserGraph.html

主题分类