Integer eigenvalues of the n-Queens graph

DOI10.1016/J.DISC.2024.114065MaRDI QIDQ6423834zbMATH OpenFDO

Authors D. M. Cardoso, Inês Serôdio Costa, Rui Duarte

Publication date 19 January 2023

Full work available at URL https://doi.org/10.1016/J.DISC.2024.114065

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: The $n$-Queens graph, $mathcalQ(n)$, is the graph obtained from a $nimesn$ chessboard where each of its $n^2$ 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 $nge4$, the least eigenvalue of $mathcalQ(n)$ is $-4$ and its multiplicity is $(n-3{)}^2$. In this paper we prove that $n-4$ is also an eigenvalue of $mathcalQ(n)$ and its multiplicity is at least $fracn+12$ or $fracn-22$ when $n$ is odd or even, respectively. Furthermore, when $n$ is odd, it is proved that $-3,-2ldots,fracn-112$ and $fracn-52,ldots,n-5$ are additional integer eigenvalues of $mathcalQ(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.

Recommendations

• Sharp bounds on the least eigenvalue of a graph determined from edge clique partitions
• scientific article; zbMATH DE number 861358
• scientific article; zbMATH DE number 1885951
• Domination and irredundance in the queens' graph
• Queens graphs for chessboards on the torus

This page was built for publication: Integer eigenvalues of the $n$-Queens graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6423834)