Independent sets in direct products of vertex-transitive graphs (Q414657): Difference between revisions

Let \(G\) and \(H\) be graphs. The direct product of \(G\) and \(H\), denoted by \(G \times H\), has vertex set \(V(G) \times V(H)\) and edge set \(\{(u_1,v_1)(u_2,v_2):~ u_1u_2 \in E(G)\) and \(v_1v_2 \in E(H)\}\). For a graph \(F\), let \(\alpha(F)\) denote the independence number of \(F\). It is shown that if \(G\) and \(H\) are vertex transitive, then \(\alpha(G \times H) =\max\{\alpha(G)|V(H)|, \alpha(H)|V(G)|\}\). This settles an open problem posed by Tardif in 1998. The author also gives a complete description of the maximum independent sets for such direct products of graphs.