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

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 α(Circ(r, n) × H ) = max{r|H |, nα(H )} for every vertex transitive graph H, and describe the structure of maximum independent sets in Circ(r, n) × H. As consequences, we prove α(G × H ) = max{α(G)|V (H )|, α(H )|V (G)|} 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.