On the Independence Graph of Hamming Graph

The independence graph Ind(G) of a graph G is the graph with vertices as maximum independent sets of G and two vertices are adjacent, if and only if the corresponding maximum independent sets are disjoint.In this work, we find the independence graph of Cartesian product of d copies of complete graphs Kq, which is known as the Hamming graph H(d, q).Greenwell and Lovasz [7] found that the independence number of direct product of d copies of Kq as q d-1 .We prove that the independence number of Hamming graph H(d, q), which is cartesian product of d copies of Kq, is also q d-1 .As an application of our findings, we find answers for rook problem in higher dimensional square chess board.