连通图的拟拉普拉斯谱半径的一个上界.pdfVIP

维普资讯 第31卷第2期 南京师大学报 (自然科学版) V01．31No．2 2008年 6月 JOURNALOFNANJINGNORMALUNIVERSITY(NaturalScienceEdition) Jun，2008 连通图的拟拉普拉斯谱半径的一个上界 朱晓欣 ，孙志人 ，曹春正 (1．南京信息工程大学数理学院，江苏 南京 210044) (2．南京师范大学数学与计算机科学学院，江苏 南京210097) [摘要] 对于连通图G，矩阵Q(G)：D(G)+A(G)称为图G的拟拉普拉斯矩阵，其中D(G)为图的度对角矩 阵，A(G)为图的邻接矩阵．本文利用矩阵的一些性质 ，推导出连通图的拟拉普拉斯谱半径的一个上界．并将该上 界与已有的一些结论结合具体图例作了优越性比较． [关键词] 连通图，拟拉普拉斯矩阵，特征值，谱半径 ，度序列 [中图分类号]0157．7 [文献标识码]A [文章编号]1001-4616(2008)02-0027-04 ABoundonQuasiL·aplacianSpectralRadiusofConnectedGraphs ZhuXiaoxin ，SunZhiren ，CaoChunzheng (1．SchoolofMathematicsandPhysics，NanjingUniversityofInformationScienceandTechnology，Nanjing210044，China) (2．SchoolofMathematicsandComputerScience，NanjingNormalUniversity，Nanjing210097，China) Abstract：LetGbeaconnectedgraph，itsquasi—LaplacianmatrixisQ(G)：D(G)+A(G)，whereD(G)isthediago— nalmatrixofitsvertexdegreesandA(G)isitsadjacencymatrix．Usingsomepropertiesofmatrix，asharpupperbound onthequasi—Laplacianspectralradiusofconnectedrgaphsisobtained，andthesuperiorityoftheupperbound iscon— paredwithotherboundsthroughsomergaphs． Keywords：connectedgraphs，quasi—Laplacianmatrix，eigenvalue，spectralradius，dergeesequence 设G=(V，E)为聘阶无 向简单连通图，其顶点集为V= ， ，…，}，其边集为E={e，e，…，e}． 令 d表示顶点 的度 (i=1，2，…，凡)，且有d ≥d ≥…≥d．A(G)=(0)… 及D(G)=diag(d，d：， … ， d)分别为图G的邻接矩阵和度对角矩阵，则L(G)=D(G)一A(G)称为图G的拉普拉斯矩阵，Q(G) = D(G)+A(G)称为图G的拟拉普拉斯矩阵． 图G的拟拉普拉斯矩阵Q(G)的所有特征值排成的序列称为图G的拟拉普拉斯谱，其中最大特征值 称为 图G的拟拉普拉斯谱半径． 显然Q(G)是一个实对称非负不可约矩阵，其所有特征值均为实数，我们用序列 l (G)≥ 2(G)≥… ≥ (G) 来表示，在不引起混淆的情况下将 (G)简记为 ，1≤i≤凡． 目前对图的邻接谱，拉普拉斯谱的研究已经有了非常多的结论，甚至专著．但对拟拉普拉斯谱的研究 相对不多，其实对拟拉普拉斯谱的研究也具有一定的应用价值．我们可以看到图G的拟拉普拉斯矩阵 Q(G)和图G的线图 。的邻接矩阵有着密切的联系