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

The Graft Transformations and Their Applications on the Least Signless Laplacian Eigenvalue of Graphs

作　　者：冯小芸 陈旭 王国平[1] FENG Xiaoyun;CHEN Xu;WANG Guoping(School of Mathematical Sciences,Xinjiang Normal University,Urumqi 830017)

机构地区：[1]新疆师范大学数学科学学院,乌鲁木齐830017

出　　处：《工程数学学报》2022年第4期631-647,共17页Chinese Journal of Engineering Mathematics

基　　金：国家自然科学基金(11461071);自治区研究生创新项目(XJ2021G253)。

摘　　要：假定G是一个带有点集V(G)={v_(1),v_(2),···,v_(n)}的连通简单图,图G的邻接矩阵A(G)=(a_(ij))_(n×n),其中点vi与点vj相邻,则a_(ij)=1;否则a_(ij)=0。我们定义度矩阵D(G)=diag(dG(v_(1)),dG(v_(2)),···,dG(v_(n))),其中dG(v_(i))是图G中点v_(i)(1≤i≤n)的度数。定义图G的无符号拉普拉斯矩阵Q(G)=D(G)+A(G),因为Q(G)是一个半正定矩阵,所以可将其特征值设为λ_(1)(G)≥λ_(2)(G)≥···≥λ_(n)(G)≥0,其中特征值λn(G)也称为图G的最小无符号拉普拉斯特征值。对补图的最小无符号拉普拉斯特征值问题进行了研究,报告了相关问题的研究现状,给出了两种图变换,并且应用他们去确定所有双圈图的补图中最小无符号拉普拉斯特征值取最小的唯一图。Suppose that G is a simple connected graph with the vertex set V(G)={v_(1),v_(2),···,v_(n)}.Then the adjacency matrix of G is A(G)=(a_(ij))_(n×n),where a_(ij)=1 if vi is adjacent to vj,and otherwise a_(ij)=0.The degree matrix D(G)=diag(dG(v1),dG(v2),···,dG(vn)),where dG(vi)denotes the degree of vi in the graph G(1≤i≤n).The matrix Q(G)=D(G)+A(G)is the signless Laplacian matrix of G.Since Q(G)is positive semidefinite,its eigenvalues can be arranged asλ_(1)(G)≥λ_(2)(G)≥···≥λ_(n)(G)≥0,whereλn(G)is the least signless Laplacian eigenvalue of G.The least signless Laplacian eigenvalues is investigated for the complements of graphs and the state of art of the relevant issues is summarized.By virtue of two graft transformations obtained by us,the unique connected graph is characterized,whose least signless Laplacian eigenvalue is minimum among the complements of all bicyclic graphs.

关 键 词：图的变换 最小无符号拉普拉斯特征值 双圈图 补图 

分 类 号：O157.5[理学—数学]