给定最大度的补图的最小特征值

The Least Eigenvalue of the Complements of Graphs with Given Maximum Degree

摘要: 假设G是一个简单连通图，其顶点集V(G)={v1,v2,⋯,vn}。图G的邻接矩阵表示为A(G)=(aij)n×n，其中如果两个顶点vi和vj在图G中相邻，则aij=1；否则aij=0。用Jn表示所有元素均为1的n阶矩阵，并且用In表示n阶单位矩阵，那么A(Gc)和A(G)之间有A(Gc)=Jn−In−A(G)。在这篇文章中，通过使用A(Gc)和A(G)的关系，确定了给定最大度Δ≥⌈n2⌉的所有简单图的补图中最小特征值达到最小的图。

Abstract: Suppose G is a connected simple graph with the vertex setV(G)={v1,v2,⋯,vn}. The adjacency matrix of G isA(G)=(aij)n×n, whereaij=1if two verticesviandvjare adjacent in G andaij=0otherwise. LetJnbe the matrix of order n whose all entries are 1 andInbe the identity matrix of order n. Then we haveA(Gc)=Jn−In−A(G). In this paper using the relationship betweenA(Gc)andA(G), we determine the graphs whose least eigenvalue is minimum among all complements of graphs with given maximum degreeΔ≥⌈n2⌉.

1. 引言

图的最小特征值能够反映图的结构性质，所以近年来图的最小特征值的极图问题已经被广泛研究。Wang Y.和Fan Y. Z. [1] 得到了带有割点的最小特征值达到最小的图。Ye M. L.，Fan Y. Z.和Liang D. [2] 描述了给定连通度的最小特征值达到最小的图。Liu Z.和Zhou B. [3] 确定了给定悬挂点数的最小特征值达到最小的图。Hong Y.和Shu J. L. [4] 给出平面图最小特征值的下界。Wang Y.和Fan Y. Z. [5] 描述了带有割边的最小特征值达到最小的图。Zhu B. X. [6] 描述了给定控制数的简单图的最小特征值达到最小的唯一图。

同样，补图的最小特征值也能够很好地反映图的结构性质，但目前为止，关于图的补图的最小特征值研究结果还不是很多。Fan Y. Z.，Zhang F. F.和Wang Y. [7] 给出了所有树的补图中最小特征值达到最小的图。Jiang G.，Yu G.和Sun W. [8] 确定了只有两个悬挂点的图中补图的最小特征值达到最小的图。Wang H.，Javaid M.，Akram S.等 [9] 研究了补图是仙人掌图的简单连通图的最小特征值。Chen X.，Wang G. [10] 研究了带有两个悬挂点的补图的距离谱。相对来说，刻画带参数的补图的最小特征值的文章比较少，所以本文选择研究给定最大度的补图的最小特征值。

假定G是一个简单的连通图。图 $G=\left(V\left(G\right),E\left(G\right)\right)$ 的补集可以表示为 $G^c=\left(V\left(G^c\right),E\left(G^c\right)\right)$ ，其中 $V\left(G^c\right)=V\left(G\right)$ 和 $E\left(G^c\right)=\left\{xy:x,y\in V\left(G\right),xy\notin E\left(G\right)\right\}$ 。图G的邻接矩阵表示为 $A\left(G\right)={\left(a_{ij}\right)}_{n\times n}$ ，其中如果两个顶点 $v_i$ 和 $v_j$ 在图G中相邻，则 $a_{ij}=1$ ；否则 $a_{ij}=\text{0}$ 。由于 $A\left(G\right)$ 是一个非负的实对称矩阵，所以其特征值都是实数，可以排列为 ${\lambda }_1\left(G\right)\ge {\lambda }_2\left(G\right)\ge \cdots \ge {\lambda }_{\min }\left(G\right)$ ，其中 ${\lambda }_1\left(G\right)$ 和 ${\lambda }_{\min }\left(G\right)$ 分别称为图G的谱半径和最小特征值。 $A\left(G\right)$ 的特征值也是图G的特征值。图G的最大度是指图中所有顶点的度的最大值，用 $\Delta$ 表示。用 $N_G\left(v\right)$ 表示图G中顶点v的邻点集。 $J_n$ 表示所有元素均为1的n阶矩阵，并且 $I_n$ 表示n阶单位矩阵，那么 $A\left(G^c\right)$ 和 $A\left(G\right)$ 之间有 $A\left(G^c\right)=J_n-I_n-A\left(G\right)$ 。在这篇文章中，主要通过补图的邻接

矩阵 $A\left(G^c\right)$ 和原图的邻接矩阵 $A\left(G\right)$ 之间的关系，刻画出了给定最大度 $\Delta \ge \lceil \frac{n}{2}\rceil$ 的所有简单图的补图中，

其最小特征值达到最小的图。

2. 预备知识

假定G是n阶简单连通图其顶点集为 $V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ 。令 $x={\left(x_1,x_2,\cdots ,x_n\right)}^{\text{T}}$ 为邻接矩阵 $A\left(G\right)$ 的单位特征向量，其中 $x\left(v_i\right)=x_i\left(i=1,\cdots ,n\right)$ ，则有

$x^{\text{T}}A\left(G\right)x=2{\displaystyle \underset{v_i{v}_j\in E\left(G\right)}{\sum }{x}_i{x}_j}$ (1)

令 $x={\left(x_1,x_2,\cdots ,x_n\right)}^{\text{T}}$ 是 $A\left(G\right)$ 的特征值 $\lambda \left(G\right)$ 对应的单位特征向量，则有

$\lambda \left(G\right)x_i={\displaystyle \underset{v_j\in N_G\left(x_i\right)}{\sum }{x}_j}$ (2)

引理2.1 (瑞利定理)假定 ${\lambda }_1\left(G\right)$ 为图G的谱半径， ${\lambda }_{\min }\left(G\right)$ 为图G的最小特征值，若 $x={\left(x_1,x_2,\cdots ,x_n\right)}^{\text{T}}$ 为邻接矩阵 $A\left(G\right)$ 的单位特征向量，那么有

${\lambda }_{\min }\left(G\right)\le x^{\text{T}}A\left(G\right)x\le {\lambda }_1(\; G\; )$

第一个等号成立当且仅当x是 $A\left(G\right)$ 的最小特征值 ${\lambda }_{\min }\left(G\right)$ 对应的单位特征向量和第二个等号成立当且仅当x是 $A\left(G\right)$ 的谱半径 ${\lambda }_1\left(G\right)$ 对应的单位特征向量。

引理2.2 [11] 假定简单图G的最小特征值用 ${\lambda }_{\min }\left(G\right)$ 表示，则 ${\lambda }_{\min }\left(G\right)\ge -\sqrt{\lceil \frac{n}{2}\rceil \lfloor \frac{n}{2}\rfloor }$ ，等号成立当且

仅当 $G\cong K_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }$ 。

引理2.3 [12] 假设G是一个最大度为 $\Delta$ 简单连通图，其谱半径用 ${\lambda }_1\left(G\right)$ 表示，那么有 $\sqrt{\Delta }\le {\lambda }_1\left(G\right)\le \Delta$ 。□

3. 主要结论

设G是一个顶点集为 $V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ 的n阶简单图，将其补图记为 $G^c$ ，有 $V\left(G^c\right)=V\left(G\right)$ 。令 $x={\left(x_1,x_2,\cdots ,x_n\right)}^{\text{T}}$ 是 $A\left(G^c\right)$ 的最小特征值 ${\lambda }_{\min }\left(G^c\right)$ 对应的单位特征向量，其中 $x\left(v_i\right)=x_i\left(i=1,2,\cdots ,n\right)$ 。记 $V^{+}=\left\{v_i\in V\left(G^c\right):x_i>0\right\}$ ， $V^{-}=\left\{v_i\in V\left(G^c\right):x_i<0\right\}$ 和 $V^0=\left\{v_i\in V\left(G^c\right):x_i=0\right\}$ 。接下来，通过补图的邻接

矩阵 $A\left(G^c\right)$ 和原图的邻接矩阵 $A\left(G\right)$ 之间的关系，刻画出了给定最大度 $\Delta \ge \lceil \frac{n}{2}\rceil$ 的所有简单图的补图中，

其最小特征值达到最小的图。

令二部图 $B\left(p,q\right)$ 具有两部分顶点集 $\left(V_1,V_2\right)$ ，其中 $V_1=\left\{v_1,v_2,\cdots ,v_p\right\}$ 且 $V_2=\left\{v_{p+1},v_{p+2},\cdots ,v_{p+q}\right\}$ 。令V₁中所有的顶点相邻，并令V₂中的所有顶点也相邻，删除所有V₁与V₂相连的边。添加一个新的顶点u，将顶点u与V₁中的s个顶点和V₂中的t个顶点连接。这样得到的图记为 $H_{p,q}^{s,t}$ 。

定理3.1 假设G是一个给定最大度 $\Delta \ge \lceil \frac{n}{2}\rceil$ 的n阶简单连通图，那么 ${\lambda }_{\min }\left(H^c\left({}_{\lfloor \frac{n}{2}\rfloor -1,\lceil \frac{n}{2}\rceil }^{\lfloor \frac{n}{2}\rfloor -1,\Delta -\lfloor \frac{n}{2}\rfloor +1}\right)\right)<{\lambda }_{\min }\left(G^c\right)$ 。

证明：下面先分是否存在零分量两种情况进行讨论。

情况1：假设 $\left|V^0\right|=0$ 。若 $\left|V^0\right|=0$ ，则一定有 $n-\Delta \le \left|V^{-}\right|,\left|V^{+}\right|\le \Delta$ 。否则，根据引理2.1和 2.2有

$\begin{array}{c}{\lambda }_{\min }\left(G^c\right)=x^{\text{T}}A\left(G^c\right)x=2{\displaystyle \underset{v_i,v_j\in E\left(G^c\right)}{\sum }{x}_i{x}_j}\ge 2{\displaystyle \underset{v_i\in \left|V^{-}\right|,v_j\in \left|V^{+}\right|}{\sum }{x}_i{x}_j}>{\lambda }_{\min }\left(K_{\left|V^{-}\right|,\left|V^{+}\right|}\right)\\ =-\sqrt{\left|V^{-}\right|\left|V^{+}\right|}>-\sqrt{\Delta \left(n-\Delta \right)}={\lambda }_{\min }\left(K_{\Delta ,n-\Delta }\right)\end{array}$

这与 ${\lambda }_{\min }\left(G^c\right)$ 是极小的产生矛盾。所以接下来我们只需讨论 $n-\Delta \le \left|V^{-}\right|,\left|V^{+}\right|\le \Delta$ 时的情况。

假设顶点u为最大度点，不失一般性，假定 $x_u>0$ 。由于 $\left|V^{+}\right|\le \Delta$ 且 $\left|V^{-}\right|\le \Delta$ ，可以得到 $V^{+}$ 中的所有顶点一定都相邻， $V^{-}$ 中的所有顶点也一定都相邻。否则，如果存在不相邻的两个顶点 $u_1\in V^{+}$ 和 $v_1\in V^{+}$ 。显然，图 $G+u_1{v}_1$ 的最大度也是 $\Delta$ 。根据方程(1)，可以得到

$x^{\text{T}}A\left(G\right)x=2{\displaystyle \underset{v_i{v}_j\in E\left(G\right)}{\sum }{x}_i{x}_j}<2{\displaystyle \underset{v_i{v}_j\in E\left(G\right)}{\sum }{x}_i{x}_j}+2x_{u_1}{x}_{v_1}=x^{\text{T}}A\left(G+u_1{v}_1\right)x$

通过引理2.1，有

$\begin{array}{c}{\lambda }_{\min }\left(G^c\right)=x^{\text{T}}A\left(G^c\right)x\\ =x^{\text{T}}\left(J_n-I_n\right)x-x^{\text{T}}A\left(G\right)x\\ >x^{\text{T}}\left(J_n-I_n\right)x-x^{\text{T}}A\left(G+u_1{v}_1\right)x\\ =x^{\text{T}}A\left({\left(G+u_1{v}_1\right)}^c\right)x\\ \ge {\lambda }_{\min }\left({\left(G+u_1{v}_1\right)}^c\right)\end{array}$

这与 ${\lambda }_{\min }\left(G^c\right)$ 极小相矛盾。同理，也可以证明 $V^{-}$ 中的所有顶点一定都相邻。

接下来我们证明 $V^{+}$ 中除最大度点u以外的所有的顶点都和 $V^{-}$ 中的顶点不相邻。否则，如果除u点以外存在相邻的两个顶点 $w_1\in V^{+}$ 和 $z_1\in V^{-}$ 。显然，图 $G-w_1{z}_1$ 的最大度也是 $\Delta$ 。根据方程(1)，可以得到

$x^{\text{T}}A\left(G\right)x=2{\displaystyle \underset{v_i{v}_j\in E\left(G\right)}{\sum }{x}_i{x}_j}<2{\displaystyle \underset{v_i{v}_j\in E\left(G\right)}{\sum }{x}_i{x}_j}-2x_{w_1}{x}_{z_1}=x^{\text{T}}A\left(G-w_1{z}_1\right)x$

通过引理2.1，有

$\begin{array}{c}{\lambda }_{\min }\left(G^c\right)=x^{\text{T}}A\left(G^c\right)x\\ =x^{\text{T}}\left(J_n-I_n\right)x-x^{\text{T}}A\left(G\right)x\\ >x^{\text{T}}\left(J_n-I_n\right)x-x^{\text{T}}A\left(G-w_1{z}_1\right)x\\ =x^{\text{T}}A{\left(G-w_1{z}_1\right)}^{c}x\\ \ge {\lambda }_{\min }\left({\left(G-w_1{z}_1\right)}^c\right)\end{array}$

这与 ${\lambda }_{\min }\left(G^c\right)$ 极小相矛盾。

综合上述讨论和图 $H_{p,q}^{s,t}$ 的构造可以知道，如果假定 $\left|V^{+}\right|=p$ 和 $\left|V^{-}\right|=q$ ，那么 $G^c\cong H^c\left({}_{p-1,q}^{p-1,\Delta -p+1}\right)$ 。

根据 $H^c\left({}_{p-1,q}^{p-1,\Delta -p+1}\right)$ 的对称性，可以知道， $V^{+}\backslash u$ 中的所有顶点对应于相同的分量 $x_1$ ， $V^{-}\cap N\left(u\right)$ 中的所有顶点对应于相同的分量 $x_2$ 和 $V^{-}\backslash N\left(u\right)$ 中的所有顶点对应相同的值 $x_3$ ，u点对应分量 $x_u$ 。由方程(2)可以得到

$\{\begin{array}{l}{\lambda }_{\min }{x}_1=\left(p+q-\Delta -1\right)x_2+\left(\Delta -p+1\right)x_3\\ {\lambda }_{\min }{x}_2=\left(p-1\right)x_1+x_u\\ {\lambda }_{\min }{x}_3=\left(p-1\right)x_1\\ {\lambda }_{\min }{x}_u=\left(p+q-\Delta -1\right)x_2\end{array}$

将上述方程转化为矩阵方程 $\left(\lambda I_4-A\right)x\prime =0$ ，其中 $x\prime ={\left(x_1,x_2,x_3,x_u\right)}^{\text{T}}$ 和

$A=\left(\begin{array}{cccc}0& p+q-\Delta -1& \Delta -p+1& 0\\ p-1& 0& 0& 1\\ p-1& 0& 0& 0\\ 0& p+q-\Delta -1& 0& 0\end{array}\right)$

令 ${\phi }_{p,q}\left(\lambda \right)=det\left(I_4\lambda -A\right)$ 。那么有

${\phi }_{p,q}\left(\lambda \right)={\lambda }^4+\left(\Delta +1-p-pq\right){\lambda }^2+\left(\Delta +1-p-q\right)\left(\Delta +1-p\right)\left(1-p\right)$ (3)

因此，可以得到

${\phi }_{p,q}\left(\lambda \right)-{\phi }_{p+1,q-1}\left(\lambda \right)=\left(q-p\right){\lambda }^2+\left(\Delta +1-p-q\right)\left(\Delta +1-2p\right)$

令

$\begin{array}{c}f\left(\Delta \right)=-\left(\Delta +1-p-q\right)\left(\Delta +1-2p\right)\\ =-{\Delta }^2+\left(3p+q-2\right)\Delta -2pq-2p^2+3p+q-1\end{array}$

由上式可知 $f\left(\Delta \right)$ 的最大根为 $\frac{{\left(p-q\right)}^2}{4}$ 。显然，如果 ${\lambda }_{\min }=-\sqrt{\Delta }$ ，则 $\left(q-p\right){\left(-\sqrt{\Delta }\right)}^2>\frac{{\left(p-q\right)}^2}{4}$ 。所以 ${\phi }_{p,q}\left(-\sqrt{\Delta }\right)-{\phi }_{p+1,q-1}\left(-\sqrt{\Delta }\right)=\left(q-p\right){\left(-\sqrt{\Delta }\right)}^2+\left(\Delta +1-p-q\right)\left(\Delta +1-2p\right)>0$ 。根据 $H^c\left({}_{p-1,q}^{p-1,\Delta -p+1}\right)$ 的构造可以知道其是二部图，那么 ${\lambda }_1\left(G\right)=-{\lambda }_{\min }\left(G\right)$ 。通过引理2.3，有 ${\lambda }_{\min }<-\sqrt{\Delta }$ ，从而可得 ${\phi }_{p,q}\left({\lambda }_{\min }\right)-{\phi }_{p+1,q-1}\left({\lambda }_{\min }\right)>0$ 。由于 ${\phi }_{p,q}\left({\lambda }_{\min }\right)=0$ ，所以 ${\phi }_{p+1,q-1}\left({\lambda }_{\min }\right)<0$ 。因此， ${\lambda }_{\min }\left(H^c\left({}_{\lfloor \frac{n}{2}\rfloor -1,\lceil \frac{n}{2}\rceil }^{\lfloor \frac{n}{2}\rfloor -1,\Delta -\lfloor \frac{n}{2}\rfloor +1}\right)\right)<{\lambda }_{\min }\left(H^c\left({}_{p-1,q}^{p-1,\Delta -p+1}\right)\right)$ 。根据以上论证和引理3.1，可以得到 ${\lambda }_{\min }\left(H^c\left({}_{\lfloor \frac{n}{2}\rfloor -1,\lceil \frac{n}{2}\rceil }^{\lfloor \frac{n}{2}\rfloor -1,\Delta -\lfloor \frac{n}{2}\rfloor +1}\right)\right)<{\lambda }_{\min }\left(G^c\right)$ 。至此情况1证明完成。

情况2：假设 $\left|V^0\right|\ne 0$ 。若 $\left|V^0\right|\ne 0$ ，则令y是x去掉 $v\in V^0$ 的相应分量的子向量。根据引理2.1和方程(1)，有

$\begin{array}{c}{\lambda }_{\min }\left(G^c\right)=2{\displaystyle \underset{v_i{v}_j\in E\left(G^c\right)}{\sum }{x}_i{x}_j}\\ =y^{\text{T}}A\left({\left(G-V^0\right)}^c\right)y\\ \ge {\lambda }_{\min }\left({\left(G-V^0\right)}^c\right)\end{array}$

其中不等式中的等号成立当且仅当y是 ${\left(G-V^0\right)}^c$ 的最小特征值对应的向量。显然有

$\begin{array}{c}{\lambda }_{\min }\left({\left(G-V^0\right)}^c\right)\ge {\lambda }_{\min }\left(K_{\left|V^{-}\right|,\left|V^{+}\right|}\right)\\ =-\sqrt{\left|V^{-}\right|\left|V^{+}\right|}\\ \ge -\sqrt{\lceil \frac{n-1}{2}\rceil \lfloor \frac{n-1}{2}\rfloor }\end{array}$

其中第一个不等式中的等号成立当且仅当 ${\left(G-V^0\right)}^c\cong K_{\left|V^{-}\right|,\left|V^{+}\right|}$ 。结合上面两个式子，如果 $\left|V^0\right|\ne 0$ ，则有 ${\lambda }_{\min }\left(G^c\right)\ge -\sqrt{\lceil \frac{n-1}{2}\rceil \lfloor \frac{n-1}{2}\rfloor }$ 。等号成立当且仅当 $V^0=\left\{u\right\}$ 和 $G^c\cong H^c\left({}_{\lfloor \frac{n-1}{2}\rfloor ,\lceil \frac{n-1}{2}\rceil }^{b,\Delta -b}\right)$ ，其中u是最大度点，b

是一些正整数。至此完成了情况2的证明。

最后，在情况1中，从式子(3)可以知道 ${\lambda }_{\min }\left(H^c\left({}_{\lfloor \frac{n-1}{2}\rfloor ,\lceil \frac{n-1}{2}\rceil }^{\lfloor \frac{n-1}{2}\rfloor ,\Delta -\lfloor \frac{n-1}{2}\rfloor }\right)\right)$ 是如下方程的最小根：

$\begin{array}{l}{\lambda }^4+\left[\Delta +1-\left(\lfloor \frac{n-1}{2}\rfloor +1\right)-\left(\lfloor \frac{n-1}{2}\rfloor +1\right)\lceil \frac{n-1}{2}\rceil \right]{\lambda }^2\\ +\left[\Delta +1-\left(\lfloor \frac{n-1}{2}\rfloor +1\right)-\lceil \frac{n-1}{2}\rceil \right]\left[\Delta +1-\left(\lfloor \frac{n-1}{2}\rfloor +1\right)\right]\left[1-\left(\lfloor \frac{n-1}{2}\rfloor +1\right)\right]=0\end{array}$

通过计算可以得到当 $\lambda =-\sqrt{\lceil \frac{n-1}{2}\rceil \lfloor \frac{n-1}{2}\rfloor }$ 时，有

$\begin{array}{l}{\lambda }^4+\left[\Delta +1-\left(\lfloor \frac{n-1}{2}\rfloor +1\right)-\left(\lfloor \frac{n-1}{2}\rfloor +1\right)\lceil \frac{n-1}{2}\rceil \right]{\lambda }^2\\ +\left[\Delta +1-\left(\lfloor \frac{n-1}{2}\rfloor +1\right)-\lceil \frac{n-1}{2}\rceil \right]\left[\Delta +1-\left(\lfloor \frac{n-1}{2}\rfloor +1\right)\right]\left[1-\left(\lfloor \frac{n-1}{2}\rfloor +1\right)\right]\le 0\end{array}$

等号成立当且仅当 $\Delta =n-1$ 是偶数，这表明 ${\lambda }_{\min }\left(G^c\right)<{\lambda }_{\min }\left(H^c\left({}_{\lfloor \frac{n-1}{2}\rfloor ,\lceil \frac{n-1}{2}\rceil }^{\lfloor \frac{n-1}{2}\rfloor ,\Delta -\lfloor \frac{n-1}{2}\rfloor }\right)\right)\le -\sqrt{\lceil \frac{n-1}{2}\rceil \lfloor \frac{n-1}{2}\rfloor }$ 。

在情况2中，根据情况2中的证明过程，可以得到 ${\lambda }_{\min }\left(G^c\right)\ge -\sqrt{\lceil \frac{n-1}{2}\rceil \lfloor \frac{n-1}{2}\rfloor }$ 。

综合上述讨论，如果 $G^c$ 的最小特征值达到最小对应的极图属于情况1，则有 ${\lambda }_{\min }\left(G^c\right)<-\sqrt{\lceil \frac{n-1}{2}\rceil \lfloor \frac{n-1}{2}\rfloor }$ ；如果 $G^c$ 的最小特征值达到最小对应的极图属于情况2，则有 ${\lambda }_{\min }\left(G^c\right)\ge -\sqrt{\lceil \frac{n-1}{2}\rceil \lfloor \frac{n-1}{2}\rfloor }$ 。所以 $G^c$ 的最小特征值达到最小对应的极图属于情况1。因此 ${\lambda }_{\min }\left(H^c\left({}_{\lfloor \frac{n}{2}\rfloor -1,\lceil \frac{n}{2}\rceil }^{\lfloor \frac{n}{2}\rfloor -1,\Delta -\lfloor \frac{n}{2}\rfloor +1}\right)\right)<{\lambda }_{\min }\left(G^c\right)$ ，结论成立。□