
Summary: The independence graph \(\operatorname{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)\). \textit{D. Greenwell} and \textit{L. Lovász} [Acta Math. Acad. Sci. Hung. 25, 335--340 (1974; Zbl 0294.05108)] 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.
independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Hamming graph, Graph representations (geometric and intersection representations, etc.), independence graph, Cartesian product, rook problem
independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Hamming graph, Graph representations (geometric and intersection representations, etc.), independence graph, Cartesian product, rook problem
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
