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

作     者：Xing Bo GENG Jun WANG Hua Jun ZHANG 

作者机构：School of Mathematical ScienceDalian University of Technology Department of MathematicsShanghai Normal University Department of MathematicsZhejiang Normal University 

出 版 物：《Acta Mathematica Sinica,English Series》 (数学学报（英文版）)

年 卷 期：2012年第28卷第4期

页      面：697-706页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：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) 

主　　题：Vertex-transitivity primitivity independence number 

摘      要：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.