نشریه علوم ریاضی و انفورماتیک

Mendeley  

Zotero  

Saravanan M, Kathiresan K. On the Independence Graph of Hamming Graph. IJMSI 2025; 20 (1) :125-130
URL: http://ijmsi.ir/article-1-1865-fa.html

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 K_q, 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 K_q as q^d−1. We prove that the independence number of Hamming graph H(d, q), which is cartesian product of d copies of K_q, is also q^d−1. As an application of our findings, we find answers for rook problem in higher dimensional square chess board.