2023/01/19 by Cardoso, Domingos M., Costa, Inês Serôdio, Duarte, Rui · 1 citation
#05C50 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2301.08106
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+1)/(2) or (n-2)/(2) when n is odd or even, respectively. Furthermore, when n is odd, it is proved that -3,-2…,(n-11)/(2) and (n-5)/(2),…,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.