Independent sets in direct products of vertex-transitive graphs

摘要

The direct product G × H of graphs G and H is defined by V(G × H) = V(G) × V(H) and E(G × H)={[(u_1, v_1), (u_2, v_2)]: (u_1, u_2) ∈ E(G) and (v_1, v_2) ∈ E(H)}. In this paper, we will prove that α(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 × H is determined.