图变换及其在图的最小无符号拉普拉斯特征值的应用

作者：冯小芸; 陈旭; 王国平^*

来源：工程数学学报, 2022, 39(04): 631-647.

• 图的变换
• 最小无符号拉普拉斯特征值
• 双圈图
• 补图

假定G是一个带有点集V(G)={v1,v2,···,vn}的连通简单图，图G的邻接矩阵A(G)=(aij)n×n，其中点vi与点vj相邻，则aij=1；否则aij=0。我们定义度矩阵D(G)=diag(dG(v1),dG(v2),···,dG(vn))，其中dG(vi)是图G中点vi(1≤i≤n)的度数。定义图G的无符号拉普拉斯矩阵Q(G)=D(G)+A(G)，因为Q(G)是一个半正定矩阵，所以可将其特征值设为λ1(G)≥λ2(G)≥···≥λn(G)≥0，其中特征值λn(G)也称为图G的最小无符号拉普拉斯特征值。对补图的最小无符号拉普拉斯特征值问题进行了研究，报告了相关问题的研究现状，给出了两种图变换，并且应用他们去确定所有双圈图的补图中最小无符号拉普拉斯特征值取最小的唯一图。

• 单位
  新疆师范大学