Independent sets in direct products of vertex-transitive graphs

The direct product G×HG×H of graphs G and H is defined byV(G×H)=V(G)×V(H)V(G×H)=V(G)×V(H) andE(G×H)={[(u1,v1),(u2,v2)]:(u1,u2)∈E(G) and(v1,v2)∈E(H)}.E(G×H)={[(u1,v1),(u2,v2)]:(u1,u2)∈E(G) and(v1,v2)∈E(H)}. In this paper, we will prove thatα(G×H)=max{α(G)|H|,α(H)|G|}α(G×H)=max{α(G)|H|,α(H)|G|} holds for all vertex-transitive graphs G and H, which provides an affirmative answer to a problem posed by Tardif (1998) [11]. Furthermore, the structure of all maximum independent sets of G×HG×H is determined.