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)=\left\{[(u_1,v_1),(u_2,v_2)]: (u_1,u_2)\in E(G) \mbox{\ and\ } (v_1,v_2)\in E(H)\right\}.\] In this paper, we will prove that the equality $α(G\times 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 (Discrete Math. 185 (1998) 193-200). Furthermore, the structure of all maximum independent sets of $G\times H$ are determined.

No reviews yet.

No comments yet.