一些奇异同谱图的性质研究

Research on the Property of Some Singularly Cospectral Graphs

摘要: 图G的能量E(G)是其邻接矩阵的所有特征值绝对值的和。如果两个图有相同的非零奇异值及重数，那么被称为奇异同谱图。奇异同谱图的刻画及性质研究对于图能量问题的推进有重要意义。本文利用克罗内克积和笛卡尔积运算，给出了一些新的关于奇异同谱图的性质。

Abstract: The energy E(G) of graph G is the sum of the absolute values of all the eigenvalues of its adjacency matrix. If two graphs have the same non-zero singular values with the same multiplicities, then they are called singularly cospectral. The study of the characterization and properties of singularly cospectral graphs is important for the advancement of the graph energy problem. In this paper, some new properties on singularly cospectral graphs are given using the Kronecker product and the Cartesian product.

1. 引言

设无向简单图G的顶点集为 $V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ ，边集为 $E\left(G\right)$ 。其邻接矩阵定义为 $A\left(G\right)=\left(a_{ij}\right)$ ，其中 $a_{ij}=\{\begin{array}{l}1,如果v_i\sim v_j,\\ 0,其它.\end{array}$ 。图G的特征值就是邻接矩阵 $A\left(G\right)$ 的特征值。图G的谱定义为 $A\left(G\right)$ 的特征值的多重集，记为 $\text{Spec}\left(G\right)$ 。假设 $A\left(G\right)$ 的不同特征值为 ${\lambda }_1>{\lambda }_2>\cdots >{\lambda }_s$ ，其重数分别为 $m_1,m_2,\cdots ,m_s$ ，则G的谱记为 $\text{Spec}\left(G\right)=\left(\begin{array}{cccc}{\lambda }_1& {\lambda }_2& \cdots & {\lambda }_s\\ m_1& m_2& \cdots & m_s\end{array}\right)$ 。若图G的顶点集可划分为两个非空子集X和Y，使得G的任一条边都有一个端点在X中，另一个端点在Y中，则称G为二部图。图能量的研究起源于有机化学，1978年Gutman [1] 首先将图G的能量 $\mathcal{E}\left(G\right)$ 定义为图G的特征值的绝对值之和，即 $\mathcal{E}\left(G\right)={\displaystyle \underset{i=1}{\overset{s}{\sum }}{m}_i}\left|{\lambda }_i\right|$ 。如果 $\mathcal{E}\left(G\right)=\mathcal{E}\left(H\right)$ ，则称两个不同构的图G和图H等能量。如果两个图具有相同的谱，则称它们是同谱的。

为了进一步研究图的能量，Nikiforov [2] 引入了奇异同谱的定义。如果两个图具有相同的非零奇异值及重数，则称这两个图是奇异同谱的。显然同谱一定奇异同谱，反之不然。奇异同谱图的非零特征值的绝对值是相同。因此，奇异同谱图自然是等能量的。Nikiforov [2] 提出了寻找两个图是奇异同谱的充要条件的问题。与被充分研究的同谱图不同(研究结果可以参考文献 [3] [4] [5] [6] [7] )，很少有文献关注到奇异同谱图。Conde等人 [8] 通过给出奇异同谱的一些等价条件，在一定程度上回答了Nikiforov的问题。此外，他们还提出了一个寻找非同谱的奇异同谱图的问题。本文利用克罗内克积和笛卡尔积运算，给出了一些新的关于奇异同谱图的性质。

2. 预备知识

定义2.1给出了克罗内克积的矩阵表示。

定义2.1 [9] 设 $A=\left(a_{ij}\right)$ 是 $\left(m\times n\right)$ 的矩阵， $B=\left(b_{ij}\right)$ 是 $\left(r\times s\right)$ 的矩阵。矩阵A和B的克罗内克积(张量积)，记为 $A\otimes B$ ，被定义为分块矩阵

$A\otimes B=\left(\begin{array}{cccc}{a}_{11}B& a_{12}B& \cdots & a_{1n}B\\ a_{21}B& a_{22}B& \cdots & a_{2n}B\\ ⋮& ⋮& & ⋮\\ a_{m1}B& a_{m2}B& \cdots & a_{mn}B\end{array}\right).$

$A\otimes B$ 的阶数为 $\left(mr\times ns\right)$ ，有mn个块，且第 $\left(i,j\right)$ 个块是 $\left(r\times s\right)$ 阶矩阵 $a_{ij}B$ 。

定义2.2给出了两个图的笛卡尔积的定义方式。

定义2.2 [10] 两个图 $G_1$ 和 $G_2$ 的笛卡尔积 $G_1\square G_2$ 的顶点集为 $V\left(G_1\right)\times V\left(G_2\right)$ ，如果在 $G_1$ 中 $u_1$ 和 $v_1$ 相邻且 $u_2=v_2$ ，或者 $u_1=v_1$ 且在 $G_2$ 中 $u_2$ 和 $v_2$ 相邻，那么顶点 $\left(u_1,u_2\right)$ 和 $\left(v_1,v_2\right)$ 是相邻的。

定理2.1给出了矩阵克罗内克积、笛卡尔积的谱刻画和特征向量的对应关系。

定理2.1 [10] 设A是m阶方阵，B是n阶方阵。假设 ${\lambda }_i\left(1\le i\le m\right)$ 是A的任意特征值，对应的特征向量为 $x_i$ ， ${\mu }_j\left(1\le j\le n\right)$ 是B的任意特征值，对应的特征向量为 $y_j$ 。那么 $A\otimes B$ 和 $A\square B$ 的谱和特征向量如下：

i) ${\lambda }_i{\mu }_j\left(1\le i\le m,1\le j\le n\right)$ 是 $A\otimes B$ 的一个特征值，对应的特征向量为 $x_i\otimes y_j$ 。

ii) ${\lambda }_i+{\mu }_j\left(1\le i\le m,1\le j\le n\right)$ 是 $A\square B$ 的一个特征值，对应的特征向量为 $x_i\otimes y_j$ 。

3. 一些奇异同谱图的性质

下面我们利用图的克罗内克积和笛卡尔积，给出一些新的奇异同谱图的性质。

定理3.1设 $G_1$ 和 $G_2$ 是一对n阶奇异同谱图。设 $H_1$ 和 $H_2$ 是一对m阶同谱图。

i) 如果 $H_1$ 和 $H_2$ 是二部图，那么 $A\left(G_1\right)\otimes A\left(H_1\right)$ 和 $A\left(G_2\right)\otimes A\left(H_2\right)$ 是同谱的。

ii) 如果 $H_1$ 和 $H_2$ 是二部图，那么 $A\left(G_1\right)\square A\left(H_1\right)$ 和 $A\left(G_2\right)\square A\left(H_2\right)$ 是奇异同谱的。

iii) 如果 $H_1$ 和 $H_2$ 不是二部图，那么 $A\left(G_1\right)\otimes A\left(H_1\right)$ 和 $A\left(G_2\right)\otimes A\left(H_2\right)$ 是奇异同谱的。

证明：i) 假设图 $G_1$ 和 $G_2$ 的特征值分别按 $\left|{\lambda }_1\right|\ge \left|{\lambda }_2\right|\ge \cdots \ge \left|{\lambda }_n\right|$ ； $\left|{\mu }_1\right|\ge \left|{\mu }_2\right|\ge \cdots \ge \left|{\mu }_n\right|$ 排列。因为图 $G_1$ 和 $G_2$ 是奇异同谱的，我们有 $\left|{\lambda }_i\right|=\left|{\mu }_i\right|$ 。由于 $H_i\left(i=1,2\right)$ 是一个二部图，那么 ${\nu }_j$ 是 $H_i$ 的特征值当且仅当 $-{\nu }_j$ 也是 $H_i$ 的特征值。根据定理2.1，我们有

$\begin{array}{l}\text{Spec}\left(A\left(G_1\right)\otimes A\left(H_1\right)\right)=\left\{\pm {\lambda }_i{\nu }_j|i=1,\cdots ,n,j=1,\cdots ,\lceil \frac{m}{2}\rceil \right\},\\ \text{Spec}\left(A\left(G_2\right)\otimes A\left(H_2\right)\right)=\left\{\pm {\mu }_i{\nu }_j|i=1,\cdots ,n,j=1,\cdots ,\lceil \frac{m}{2}\rceil \right\}.\end{array}$ (1)

由此可见， $A\left(G_1\right)\otimes A\left(H_1\right)$ 和 $A\left(G_2\right)\otimes A\left(H_2\right)$ 是同谱的。

ii) 根据定理2.1，我们有

$\begin{array}{l}\text{Spec}\left(A\left(G_1\right)\square A\left(H_1\right)\right)=\left\{{\lambda }_i\pm {\nu }_j|i=1,\cdots ,n,j=1,\cdots ,\lceil \frac{m}{2}\rceil \right\},\\ \text{Spec}\left(A\left(G_2\right)\square A\left(H_2\right)\right)=\left\{{\mu }_i\pm {\nu }_j|i=1,\cdots ,n,j=1,\cdots ,\lceil \frac{m}{2}\rceil \right\}.\end{array}$ (2)

如果 ${\lambda }_i={\mu }_i$ ，则 ${\lambda }_i\pm {\nu }_j={\mu }_i\pm {\nu }_j\left(i=1,\cdots ,n;j=1,\cdots ,\lceil \frac{m}{2}\rceil \right)$ ，否则 ${\lambda }_i=-{\mu }_i$ ，有 ${\lambda }_i\pm {\nu }_j=-\left({\mu }_i\mp {\nu }_j\right)$ 。由此可知， $\left|{\lambda }_i\pm {\nu }_j\right|=\left|{\mu }_i\pm {\nu }_j\right|$ ，即 $A\left(G_1\right)\square A\left(H_1\right)$ 和 $A\left(G_2\right)\square A\left(H_2\right)$ 是奇异同谱的。

iii) 由于 $H_i\left(i=1,2\right)$ 不是一个二部图，因此存在 $H_i$ 的特征值 ${\nu }_{j_0}$ ，使得 $-{\nu }_{j_0}$ 不是 $H_i$ 的特征值。又因为图 $G_1$ 和 $G_2$ 是奇异同谱的，对于每个 $i=1,\cdots ,n;j=1,\cdots ,\lceil \frac{m}{2}\rceil$ ，都有 $\left|{\lambda }_i{\nu }_j\right|=\left|{\mu }_i{\nu }_j\right|$ 成立。由于图 $G_1$ 和 $G_2$ 是不同谱的，因此至少存在一个下标 $i_0$ ，使得 ${\lambda }_{i_0}=-{\mu }_{i_0}$ ，因此存在特征值 ${\lambda }_{i_0}{\nu }_{j_0}$ 不在 $A\left(G_2\right)\otimes A\left(H_2\right)$ 的谱中，即 ${\lambda }_{i_0}{\nu }_{j_0}\cancel{\in }\text{Spec}\left(A\left(G_2\right)\otimes A\left(H_2\right)\right)$ 。这就意味着， $A\left(G_1\right)\otimes A\left(H_1\right)$ 和 $A\left(G_2\right)\otimes A\left(H_2\right)$ 是奇异同谱的。

如果 $H_1$ 和 $H_2$ 是同构图，那么我们可以立即得到一个推论。

推论3.2设 $G_1$ 和 $G_2$ 是一对n阶奇异同谱图。设H是一个m阶的图。

i) 如果H是一个二部图，那么 $A\left(G_1\right)\otimes A\left(H\right)$ 和 $A\left(G_2\right)\otimes A\left(H\right)$ 是同谱的。

ii) 如果H是一个二部图，那么 $A\left(G_1\right)\square A\left(H\right)$ 和 $A\left(G_2\right)\square A\left(H\right)$ 是奇异同谱的。

iii) 如果H不是一个二部图，那么 $A\left(G_1\right)\otimes A\left(H\right)$ 和 $A\left(G_2\right)\otimes A\left(H\right)$ 是奇异同谱的。

为了说明推论3.2，我们给出以下三个例子。

例3.3设 $G_1$ 和 $G_2$ 是一对奇异同谱图(见图1)，设H是4个顶点的路图(见图2)。我们可以得到 $A\left(G_1\right)\otimes A\left(H\right)$ 和 $A\left(G_2\right)\otimes A\left(H\right)$ 所对应的邻接矩阵图(见图3)。在表1中我们列出 $A\left(G_1\right)\otimes A\left(H\right)$ 和 $A\left(G_2\right)\otimes A\left(H\right)$ 的所有特征值，容易验证 $A\left(G_1\right)\otimes A\left(H\right)$ 和 $A\left(G_2\right)\otimes A\left(H\right)$ 是同谱的。

Figure 1. A pair of singularly cospectral graph $G_1$ and $G_2$

图1. 一对奇异同谱图 $G_1$ 与 $G_2$

Figure 2. Graph H

图2. 图H

Figure 3. The adjacency matrix graph corresponding to $A\left(G_1\right)\otimes A\left(H\right)$ and $A\left(G_2\right)\otimes A(\; H\; )$

图3. $A\left(G_1\right)\otimes A\left(H\right)$ 与 $A\left(G_2\right)\otimes A\left(H\right)$ 所对应的邻接矩阵图

Table 1. Eigenvalues of A ( G 1 ) ⊗ A ( H ) and A ( G 2 ) ⊗ A ( H )

表1. $A\left(G_1\right)\otimes A\left(H\right)$ 与 $A\left(G_2\right)\otimes A\left(H\right)$ 的特征值

例3.4设 $G_1$ 和 $G_2$ 是一对奇异同谱图(见图4)，设H是4个顶点的路图(见图5)。我们可以得到 $A\left(G_1\right)\square A\left(H\right)$ 和 $A\left(G_2\right)\square A\left(H\right)$ 所对应的邻接矩阵图(见图6)。在表2中我们列出 $A\left(G_1\right)\square A\left(H\right)$ 和 $A\left(G_2\right)\square A\left(H\right)$ 的所有特征值，容易验证 $A\left(G_1\right)\square A\left(H\right)$ 和 $A\left(G_2\right)\square A\left(H\right)$ 是奇异同谱的。

Figure 4. A pair of singularly cospectral graph $G_1$ and $G_2$

图4. 一对奇异同谱图 $G_1$ 与 $G_2$

Figure 5. Graph H

图5. 图H

Figure 6. The adjacency matrix graph corresponding to $A\left(G_1\right)\square A\left(H\right)$ and $A\left(G_2\right)\square A(\; H\; )$

图6. $A\left(G_1\right)\square A\left(H\right)$ 与 $A\left(G_2\right)\square A\left(H\right)$ 所对应的邻接矩阵图

Table 2. Eigenvalues of A ( G 1 )   □   A ( H ) and A ( G 2 )   □   A ( H )

表2. $A\left(G_1\right)\square A\left(H\right)$ 与 $A\left(G_2\right)\square A\left(H\right)$ 的特征值

例3.5设 $G_1$ 和 $G_2$ 是一对奇异同谱图(见图7)，设H是一个5个顶点的图(见图8)。我们可以得到 $A\left(G_1\right)\otimes A\left(H\right)$ 和 $A\left(G_2\right)\otimes A\left(H\right)$ 所对应的邻接矩阵图(见图9)。在表3中我们列出 $A\left(G_1\right)\otimes A\left(H\right)$ 和 $A\left(G_2\right)\otimes A\left(H\right)$ 的所有特征值，容易验证 $A\left(G_1\right)\otimes A\left(H\right)$ 和 $A\left(G_2\right)\otimes A\left(H\right)$ 是奇异同谱的。

Figure 7. A pair of singularly cospectral graph $G_1$ and $G_2$

图7. 一对奇异同谱图 $G_1$ 与 $G_2$

Figure 8. Graph H

图8. 图H

Figure 9. The adjacency matrix graph corresponding to $A\left(G_1\right)\otimes A\left(H\right)$ and $A\left(G_2\right)\otimes A(\; H\; )$

图9. $A\left(G_1\right)\otimes A\left(H\right)$ 与 $A\left(G_2\right)\otimes A\left(H\right)$ 所对应的邻接矩阵图

Table 3. Eigenvalues of A ( G 1 ) ⊗ A ( H ) and A ( G 2 ) ⊗ A ( H )

表3. $A\left(G_1\right)\otimes A\left(H\right)$ 与 $A\left(G_2\right)\otimes A\left(H\right)$ 的特征值

4. 结语

奇异同谱图的刻画及性质研究对于图能量问题的推进具有重要意义，我们利用图的克罗内克积和笛卡尔积，给出一些新的奇异同谱图的性质，并给出了具体的实例。后续将利用此性质，研究构造同构图的充分条件。