Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/30086
Título: | Spectral properties of the n-Queens' graphs |
Autor: | Cardoso, Domingos M. Costa, Inês Serôdio Duarte, Rui |
Palavras-chave: | Queens' graph Graph spectra Equitable partition |
Data: | 4-Dez-2020 |
Editora: | arXiv |
Resumo: | The 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. The $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. |
Peer review: | no |
URI: | http://hdl.handle.net/10773/30086 |
Versão do Editor: | https://arxiv.org/abs/2012.01992 |
Aparece nas coleções: | CIDMA - Artigos DMat - Artigos OGTCG - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
2012.01992.pdf | 298.96 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.