Integer eigenvalues of the n-Queens graph

The n-Queens graph, Q(n), is the graph obtained from a n×n chessboard where each of its n2 squares is a vertex and two vertices are adjacent if and only if they are in the same row, column or diagonal. In a previous work the authors have shown that, for n≥4, the least eigenvalue of Q(n) is −4 and its multiplicity is (n−3)2. In this paper we prove that n−4 is also an eigenvalue of Q(n) and its multiplicity is at least n+12 or n−22 when n is odd or even, respectively. Furthermore, when n is odd, it is proved that −3,−2,…,n−112 and n−52,…,n−5 are additional integer eigenvalues of Q(n) and a family of eigenvectors associated with them is presented. Finally, conjectures about the multiplicity of the aforementioned eigenvalues and about the non-existence of any other integer eigenvalue are stated.