Independent Sets in Tensor Products of Three Vertex-transitive Graphs

The tensor product T(G(1), G(2), G(3)) of graphs G(1), G(2) and G(3) is defined by V T(G(1), G(2), G(3)) = V(G(1)) x V(G(2)) x V(G(3)) and ET(G(1), G(2), G(3)) = {vertical bar(u(1), u(2), u(3)), (v(1), v(2), v(3))]vertical bar : vertical bar{i : (u(i), v(i)) is an element of E(G(i))}vertical bar >= 2}. From this definition, it is easy to see that the preimage of the direct product of two independent sets of two factors under projections is an independent set of T(G(1), G(2), G(3)). So alpha T(G(1), G(2), G(3)) >= max{alpha(G(1))alpha(G(2))vertical bar G(3)vertical bar, alpha(G(1))alpha(G(3))vertical bar G(2)vertical bar, alpha(G(2))alpha(G(3))vertical bar G(1)vertical bar}. In this paper, we prove that the equality holds if G(1) and G(2) are vertex-transitive graphs and G(3) is a circular graph, a Kneser graph, or a permutation graph. Furthermore, in this case, the structure of all maximum independent sets of T(G(1), G(2), G(3)) is determined.