论文标题
$ n $ - Queens图的光谱属性
Spectral properties of the $n$-Queens' Graphs
论文作者
论文摘要
$ n $ - Queens的图，$ \ Mathcal {q}（n）$，是与$ n \ times n $ Chessboard（经典$ 8 \ times 8 $ Chessboard的概括）相关的图形，带有$ n^2 $顶点，每个都与棋盘的正方形相对应。 $ \ MATHCAL {Q}（n）$的两个顶点是相邻的，并且仅当它们在同一行，同一列或棋盘的对角线中时。在$ \ Mathcal {q}（n）$的主要组合属性的简短概述之后，研究了其光谱属性。首先，使用集团边缘分区获得了任意图的最小特征值的下限，并推导获得该下限的足够条件。对于$ \ Mathcal {q}（n）$的特定情况，我们证明，对于每$ n $，其最低特征值不少于$ -4 $，并且等于$ -4 $，而乘以$ n-3）^2 $，对于每个$ n \ ge 4 $。此外，$ n-4 $也是$ \ Mathcal {q}（n）$的特征值，具有$ \ frac {n-2} {2} $时，当$ n $均匀，至少$ \ frac {n+1}}} $ n $ n $ n $ n $时，至少是$ \ frac {n-2} {2} $。提出了关于$ \ Mathcal {q}（n）$的整数特征值的猜想。 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.
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 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 $\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.
