Structure of Independent Sets in Direct Products of Some Vertex-transitive Graphs  

作　　者：Xing Bo GENG Jun WANG Hua Jun ZHANG 

机构地区：[1]School of Mathematical Science,Dalian University of Technology [2]Department of Mathematics,Shanghai Normal University [3]Department of Mathematics,Zhejiang Normal University

出　　处：《Acta Mathematica Sinica,English Series》2012年第4期697-706,共10页数学学报（英文版）

基　　金：supported by National Natural Foundation of China(Grant No.10731040);supported by National Natural Foundation of China(Grant No.11001249);Ph.D.Programs Foundation of Ministry of Education of China (Grant No.20093127110001);Zhejiang Innovation Project(Grant No.T200905)

摘　　要：Let Circ（r, n） be a circular graph. It is well known that its independence number α（Circ（r, n）） = r. In this paper we prove that for every vertex transitive graph H, and describe the structure of maximum independent sets in Circ（r, n） × H. As consequences, we prove for G being Kneser graphs, and the graphs defined by permutations and partial permutations, respectively. The structure of maximum independent sets in these direct products is also described.Let Circ（r, n） be a circular graph. It is well known that its independence number α（Circ（r, n）） = r. In this paper we prove that for every vertex transitive graph H, and describe the structure of maximum independent sets in Circ（r, n） × H. As consequences, we prove for G being Kneser graphs, and the graphs defined by permutations and partial permutations, respectively. The structure of maximum independent sets in these direct products is also described.

关 键 词：Vertex-transitivity PRIMITIVITY independence number 

分 类 号：O157.5[理学—数学] O151.22[理学—基础数学]