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 indepe...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.展开更多
基金supported by National Natural Foundation of China(Grant No.10731040)supported by National Natural Foundation of China(Grant No.11001249)+1 种基金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.
