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的邻接矩阵表示为
,其中如果两个顶点
和
在图G中相邻,则
;否则
。由于
是一个非负的实对称矩阵,所以其特征值都是实数,可以排列为
,其中
和
分别称为图G的谱半径和最小特征值。
的特征值也是图G的特征值。图G的最大度是指图中所有顶点的度的最大值,用
表示。用
表示图G中顶点v的邻点集。
表示所有元素均为1的n阶矩阵,并且
表示n阶单位矩阵,那么
和
之间有
。在这篇文章中,主要通过补图的邻接
矩阵
和原图的邻接矩阵
之间的关系,刻画出了给定最大度
的所有简单图的补图中,
其最小特征值达到最小的图。
2. 预备知识
假定G是n阶简单连通图其顶点集为
。令
为邻接矩阵
的单位特征向量,其中
,则有
(1)
令
是
的特征值
对应的单位特征向量,则有
(2)
引理2.1 (瑞利定理)假定
为图G的谱半径,
为图G的最小特征值,若
为邻接矩阵
的单位特征向量,那么有
第一个等号成立当且仅当x是
的最小特征值
对应的单位特征向量和第二个等号成立当且仅当x是
的谱半径
对应的单位特征向量。
引理2.2 [11] 假定简单图G的最小特征值用
表示,则
,等号成立当且
仅当
。
引理2.3 [12] 假设G是一个最大度为
简单连通图,其谱半径用
表示,那么有
。□
3. 主要结论
设G是一个顶点集为
的n阶简单图,将其补图记为
,有
。令
是
的最小特征值
对应的单位特征向量,其中
。记
,
和
。接下来,通过补图的邻接
矩阵
和原图的邻接矩阵
之间的关系,刻画出了给定最大度
的所有简单图的补图中,
其最小特征值达到最小的图。
令二部图
具有两部分顶点集
,其中
且
。令V1中所有的顶点相邻,并令V2中的所有顶点也相邻,删除所有V1与V2相连的边。添加一个新的顶点u,将顶点u与V1中的s个顶点和V2中的t个顶点连接。这样得到的图记为
。
定理3.1 假设G是一个给定最大度
的n阶简单连通图,那么
。
证明:下面先分是否存在零分量两种情况进行讨论。
情况1:假设
。若
,则一定有
。否则,根据引理2.1和 2.2有
这与
是极小的产生矛盾。所以接下来我们只需讨论
时的情况。
假设顶点u为最大度点,不失一般性,假定
。由于
且
,可以得到
中的所有顶点一定都相邻,
中的所有顶点也一定都相邻。否则,如果存在不相邻的两个顶点
和
。显然,图
的最大度也是
。根据方程(1),可以得到
通过引理2.1,有
这与
极小相矛盾。同理,也可以证明
中的所有顶点一定都相邻。
接下来我们证明
中除最大度点u以外的所有的顶点都和
中的顶点不相邻。否则,如果除u点以外存在相邻的两个顶点
和
。显然,图
的最大度也是
。根据方程(1),可以得到
通过引理2.1,有
这与
极小相矛盾。
综合上述讨论和图
的构造可以知道,如果假定
和
,那么
。
根据
的对称性,可以知道,
中的所有顶点对应于相同的分量
,
中的所有顶点对应于相同的分量
和
中的所有顶点对应相同的值
,u点对应分量
。由方程(2)可以得到
将上述方程转化为矩阵方程
,其中
和
令
。那么有
(3)
因此,可以得到
令
由上式可知
的最大根为
。显然,如果
,则
。所以
。根据
的构造可以知道其是二部图,那么
。通过引理2.3,有
,从而可得
。由于
,所以
。因此,
。根据以上论证和引理3.1,可以得到
。至此情况1证明完成。
情况2:假设
。若
,则令y是x去掉
的相应分量的子向量。根据引理2.1和方程(1),有
其中不等式中的等号成立当且仅当y是
的最小特征值对应的向量。显然有
其中第一个不等式中的等号成立当且仅当
。结合上面两个式子,如果
,则有
。等号成立当且仅当
和
,其中u是最大度点,b
是一些正整数。至此完成了情况2的证明。
最后,在情况1中,从式子(3)可以知道
是如下方程的最小根:
通过计算可以得到当
时,有
等号成立当且仅当
是偶数,这表明
。
在情况2中,根据情况2中的证明过程,可以得到
。
综合上述讨论,如果
的最小特征值达到最小对应的极图属于情况1,则有
;如果
的最小特征值达到最小对应的极图属于情况2,则有
。所以
的最小特征值达到最小对应的极图属于情况1。因此
,结论成立。□