Independent Sets in Direct Products of Vertex-transitive Graphs

The direct product $G\times H$ of graphs $G$ and $H$ is defined by: $$V(G\times H)=V(G)\times V(H)$$ and $$E(G\times H)=\{[(u_1,v_1),(u_2,v_2)]:(u_1,u_2)\in E(G)and(v_1,v_2)\in E(H)\}\mathrm{.}$$ In this paper, we will prove that the equality $$\alpha (G\times H)=\max \{\alpha (G)\mathrm{\mid }H\mathrm{\mid },\alpha (H)\mathrm{\mid }G\mathrm{\mid }\}$$ holds for all vertex-transitive graphs $G$ and $H$, which provides an affirmative answer to a problem posed by Tardif (Discrete Math. 185 (1998) 193-200). Furthermore, the structure of all maximum independent sets of $G\times H$ are determined.