论文部分内容阅读
设Ω是一个给定的集合,其势为n。定义在这个集合上的Kneser图J(n,k)的顶点集V是Ω的所有k元子集,若两个k元子集不相交则它们在图中关联(其中:n,k是给定的正整数,并且n>2k,k>1)。Kneser图是十分重要的一类图,这是因为许多关于集合的计数以及计算问题可以转换为此类图中的问题加以探讨。关于Kneser图的研究在国外比较多见,而国内在这一方面的研究相对较少。关于Kneser图最著名的结果莫过于被Lovász.L证明的Kneser猜想。C.D.GodsiI和G.Royle从多个角度对这类图进行了深入研究并且取得丰富成果。
本文尝试利用代数理论主要是群理论来讨论Kneser图的部分性质,得到了如下主要结论。
首先,我们引入确定数的概念利用群论方法证明了Kneser图J(n,k)的自同构群与n次对称群Sym(n)同构。其次,我们进一步的证明了Kneser图的半径为2,由此,可以得到Kneser图自中心的一个充分条件。最后,借助计算机程序,我们分析了Kneser图的谱以及Laplace谱并得到一个猜想。