主题
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.net.cn/KneserGraph.html

主题分类