Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/30086
DC FieldValueLanguage
dc.contributor.authorCardoso, Domingos M.pt_PT
dc.contributor.authorCosta, Inês Serôdiopt_PT
dc.contributor.authorDuarte, Ruipt_PT
dc.date.accessioned2020-12-15T19:35:01Z-
dc.date.available2020-12-15T19:35:01Z-
dc.date.issued2020-12-04-
dc.identifier.urihttp://hdl.handle.net/10773/30086-
dc.description.abstractThe n-Queens’ graph, Q(n), is the graph associated to the n×n chessboard (a generalization of the classical 8×8 chessboard), with n 2 vertices, each one corresponding to a square of the chessboard. Two vertices of Q(n) are adjacent if and only if they are in the same row, in the same column or in the same diagonal of the chessboard. After a short overview on the main combinatorial properties of Q(n), its spectral properties are investigated. First, a lower bound on the least eigenvalue of an arbitrary graph is obtained using clique edge partitions and a sufficient condition for this lower bound be attained is deduced. For the particular case of Q(n), we prove that for every n, its least eigenvalue is not less than −4 and it is equal to −4 with multiplicity (n − 3)2 , for every n ≥ 4. Furthermore, n − 4 is also an eigenvalue of Q(n), with multiplicity at least n−2 2 when n is even and at least n+1 2 when n is odd. A conjecture about the integer eigenvalues of Q(n) is presented. We finish this article with an algorithm to determine an equitable partition of the n-Queens’ graph, Q(n), for n ≥ 3, concluding that such equitable partition has (⌈n/2⌉+1)⌈n/2⌉ 2 cells.pt_PT
dc.description.abstractThe $n$-Queens' graph, $\mathcal{Q}(n)$, is the graph associated to the $n \times n$ chessboard (a generalization of the classical $8 \times 8$ chessboard), with $n^2$ vertices, each one corresponding to a square of the chessboard. Two vertices of $\mathcal{Q}(n)$ are \textit{adjacent}, that is, linked by an edge, if and only if they are in the same row, in the same column or in the same diagonal of the chessboard. After a short overview on the main combinatorial properties of $\mathcal{Q}(n)$, its spectral properties are investigated. First, a lower bound on the least eigenvalue of an arbitrary graph is obtained using clique edge partitions and a sufficient condition for this lower bound be attained is deduced. For the particular case of $\mathcal{Q}(n)$, we prove that for every $n$, its least eigenvalue is not less than $-4$ and it is equal to $-4$ with multiplicity $(n-3)^2$, for every $n \ge 4$. Furthermore, $n-4$ is also an eigenvalue of $\mathcal{Q}(n)$, with multiplicity at least $\frac{n-2}{2}$ when $n$ is even and at least $\frac{n+1}{2}$ when $n$ is odd. A conjecture about the integer eigenvalues of $\mathcal{Q}(n)$ is presented. We finish this article with an algorithm to determine an equitable partition of the $n$-Queens' graph, $\mathcal{Q}(n)$, for $n \ge 3$, concluding that such equitable partition has $\frac{(\lceil n/2\rceil+1)\lceil n/2\rceil}{2}$ cells.pt_PT
dc.language.isoengpt_PT
dc.publisherarXivpt_PT
dc.relationUIDB/04106/2020pt_PT
dc.relationPD/BD/150538/2019pt_PT
dc.rightsopenAccesspt_PT
dc.subjectQueens' graphpt_PT
dc.subjectGraph spectrapt_PT
dc.subjectEquitable partitionpt_PT
dc.titleSpectral properties of the n-Queens' graphspt_PT
dc.typepreprintpt_PT
dc.description.versionpublishedpt_PT
dc.peerreviewedno-
dc.relation.publisherversionhttps://arxiv.org/abs/2012.01992pt_PT
Appears in Collections:CIDMA - Artigos
DMat - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat