邢润丹

（五邑大学 计算机学院，广东 江门 529020）

图的无符号拉普拉斯谱半径与最大度

邢润丹

（五邑大学 计算机学院，广东 江门 529020）

图的无符号拉普拉斯矩阵定义为其度矩阵与邻接矩阵之和，其最大特征值称为图的无符号拉普拉斯谱半径. 本文证明了若连通图G的无符号拉普拉斯谱半径大于那么G中必定含2个最大度点.

无符号拉普拉斯矩阵；无符号拉普拉斯谱半径；最大度

1 图的无符号拉普拉斯谱半径

本文研究简单无向图. 假设连通图G的顶点集为V(G)={v1, v2,…,vn}，边集为E(G). 图G的度矩阵D(G)定义为n×n对角矩阵，其中(i, i)元为顶点vi的度dG(vi). G的邻接矩阵定义为n×n矩阵A(G)=(aij)，其中当vivj∈E(G)时，aij=1，否则aij=0. 那么，G的无符号拉普拉斯矩阵就定义为Q(G)=D(G)+A(G)[1-2]. 显而易见，Q(G)为对称矩阵，其最大特征值称为图G的无符号拉普拉斯谱半径，记为q(G).

对于任一图G中的顶点u，令NG(u)表示点u在G中的邻点所成之集. 顶点u在图G中的度数，是指集合NG(u)的元素个数，记为dG(u). 记Δ(G)为图G的最大度. 图G中度为Δ(G)的顶点称为图G的最大度点.

拟证明以下结论：

2 图的Q-Perron向量

对于方阵A，若存在置换矩阵P，使得PAPT为一分块上三角矩阵，则称A为可约矩阵；否则称A为不可约矩阵.

若A为n阶方阵，其特征值为λ1, λ2,…,λn，则称ρ(A)=max{|λ1|,|λ2|,…,|λn|}为A的谱半径. 易见ρ(A)不一定是A的特征值.

在引入Q-Perron向量的概念之前，先介绍非负不可约矩阵的一个重要定理.

引理1[3]（Perron-Frobenius定理） 假设A为非负不可约方阵，那么以下结论成立：

1）ρ(A)＞0；

2）ρ(A)为A的一个特征值；

3）存在一个正向量x，使得Ax=ρ(A) x；

4）ρ(A)是A的单重特征值.

假设G为连通图. 由于矩阵Q(G)为非负不可约矩阵，根据引理1（Perron-Frobenius定理……