给定直径的单圈图的拟拉普拉斯谱半径
开篇：润墨网以专业的文秘视角，为您筛选了一篇给定直径的单圈图的拟拉普拉斯谱半径范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
【摘 要】文章研究的是单圈图的拟拉普拉斯的最大特征值（谱半径），刻画了所有阶数为，直径为的单圈图中取得最大谱半径的单圈图是。
【关键词】单圈图 直径 拟拉谱拉斯 谱半径
[Abstract] This paper vestigates the signless Laplacian spectral radius of unicyclic graphs and unicyclic graphs of fixed order and diameter with greatest signless Laplacian spectral radius are determined.
[Keywords] Unicyclic graphs；diameter；signless laplacian；spectral radius
1.引言及预备知识
设是一个阶简单连通无向图，定义G的邻接矩阵为，这里
。
矩阵为图G的度对角矩阵，其中表示顶点的度。矩阵称为G的拉普拉斯矩阵，矩阵称为G的拟拉普拉斯矩阵。由于是一个实对称方阵，它的特征值均为实数，不妨将其排列为。称的最大特征值称为图G的拟拉普拉斯谱半径，通常记为。此外，文中未给出定义的一些概念可以参考文献[6][7]。
图的拟拉普拉斯谱半径的研究是近年来热门的一个课题，在给定一个图的集合，在这个集合中寻找一个谱半径的上界或下界，并刻画达到这个界的图。即在给定条件下确定具有最大或者最小谱半径的极图。文献[2][3][5]分别研究了在给定围长、悬挂点个数、度序列的条件下的极图。本文研究的是在给定直径的条件下，所有单圈图取得最大拟拉普拉斯谱半径的极图。
2.引理及相关定理
引理1[3] 设为图G的一条边，在边中间加上一个新的顶点之后所得的图记为，那么有：
（1）若不是图G的内部路，且，则，其中是n阶圈。
（2）若是图G的内部路，且，则，其中这里是阶路的首尾两个顶点各添加两条悬挂边而得到的图。
引理2[1] 设u，v是简单非平凡连通图G的两个顶点，且。在顶点u和v上分别接出一条k个顶点和一条个顶点的路和，且而形成的图记为，则当或时有。
引理3[4] 假设u，v是连通图G的两个顶点，与顶点v相邻，而不与顶点u相邻，是图G的拟拉普拉斯矩阵的Perron向量，其中对应顶点（），令，如果，则。
引理4 [1]. 假设G是n阶单圈图，则且等号成立当且仅当。
图G的拟拉普拉斯特征多项式记为。
引理5 [1].假设是图G的一个悬挂点，是图G的一条边。则。
引理6. 假设是两个图：
（1）[3] 如果是的生成子图，则当时，则有。
（2）[1]如果当时有，则。
对于任意有且。如果，则。因此下面的内容中我们假设。
记为一个围长为3的圈的一个顶点上连接个悬挂边和一条长为的路，在圈的另外一个顶点上连接长为的路而得到的阶单圈图。
记为一个围长为3的圈的一个顶点上连接个悬挂边和一条长为的路，在圈的另外一个顶点上连接长为的路而得到的n阶单圈图。
注意到如果或，则。
图1
引理7：假设和是上图1显示的两个图，假设.则。
证明：首先我们对t用数学归纳法证明当，。
当时，则。假设是由增加个孤立的顶点而成的图。
则是由的一个生成子图，由引理（6）可知当时，。由引理5，
因为，所以当
因此由引理6（2）可知结论对是成立的。
现在假设，继续对进行归纳。由引理5，
注意到，
，
由归纳假设可得当时
由引理6（2）可知。
假设是如图3中所示的阶单圈图，是在中的每个顶点
上添加个悬挂点而成的阶单圈图，这里有当或时有。记
，且
引理8：假设则一定存在使得。
证明：且是拟拉普拉斯矩阵的Perron向量。这里与顶点相对应。假设则。
假设，。不妨设。
假设且
由引理1知。注意到当时且当时。当时，我们用重复上面的步骤直到是唯一的一个非零数。于是我们得到和。因为，所以引理成立。
引理9：对任意的图，，有，等式当且仅当时成立。
证明：假设，且是拟拉普拉斯矩阵的Perron向量。这里与顶点相对应。
选择使得图G的拟拉普拉斯谱半径最大，由引理8假设。假设当时，。是图G的一条导出路且，是图G中唯一的圈。因为，，我们有以下结论：
结论1：如果，则。
证明结论1：假设，首先考虑当，其中。
如果，则令是由图压缩成一个新的顶点。注意到。
假设
则且，因为，由引理2有且。因此，矛盾。
因此当，假设
任何一种情形下，由引理1，，矛盾。
因此我们有，且，假设
此时，且由引理1可得，矛盾。
结论2：
结论2的证明：假设，因为，存在。
假设
此时，由引理1可得，矛盾。
结论3：
结论3的证明：如若不然，则令
此时，由引理3可得，矛盾。
由结论1-3可知，由引理7可得引理9成立。
3.主要结果
在这部分，将给出我们的结果
定理1：假设是集合中的一个图，则，等式当且仅当时成立。
证明：假设且是拟拉普拉斯矩阵的Perron向量。这里与顶点相对应。
如果，则。如果，则或。
由引理4可知对结论成立。下面假设。
选择中具有最大谱半径的图G，由引理4我们假设。假设是直径为且是图G中唯一的圈。因为，则，，我们首先证明以下结论：
结论1：
证明结论1：否则，因为图G是连通的，则存在一条最短路连接与，则且。假设
且
则，由引理1可得
，矛盾。
由结论1，
记，这里
且。
结论2：对有。
结论2的证明：否则，假设且。
这里且。
假设。令
显然，由引理1可得，矛盾。
结论3：
结论3的证明：假设。则且。因为，假设。
令
显然，由引理1可得，矛盾。
结论4：如果，则且如果则。
结论4的证明：否则，因为，则有。因此存在。
由结论3有，这表示。由得。
令
显然由假设，，由引理1可得，矛盾。
结论5：
结论5的证明：假设。则由结论3得。如果，则令是由G压缩变成一个顶点。注意到。令，则且。注意到
由引理4得。由引理2得且。因此，矛盾。
如果，设，由引理2得。
令
显然，由引理1可得，矛盾。
由结论4和结论5得。则由引理1和引理2得。由引理9知定理1成立。
参考文献：
[1] Dragos Cvetkovic，Slobodan K.Simic ，Towards a spectral theory of graphs based on the signless Laplacian II， Linear algebra and its application 432（2010） 2257-2272.
[2]冯琳，姚艳红等，具有固定围长的单圈图的无号拉普拉斯谱半径，高校应用数学学报2011，26（1）：121-126.
[3]MuHuo Liu，XueZHong Tan，BoLian Liu， The signless Laplacian spectral radius of Unicycic and Bicyclic graphs with n vertices and k pendant vertices， Czechoslovak Mathematical Journal，60（135） （2010），849-867.
[4] X. D .Zhang， The Laplacian spectral radii of trees with degree sequences， Discrete Mathematics 308（2008） 3143-3150.
[5] X. D. Zhang， The signless Laplacian spectral radius of graphs with given degree sequences， Discrete Applied Mathematics 157（2009）2928-2937 .
[6] J.A.Bondy， U.S.R.Murty， Graph Theory[M]. New York： Springer， 2008.
[7] Dragos Cvetkovic， Peter Rowlinson， Slobodan Simic. An Introduction to the Theory of Graph Spectra [M].New York：Cambridge University Press，2010.
基金项目：
上海电机学院青年教师科研基金项目资助（09C105）
作者简介：
欧阳庚旭（1980-），男，讲师，专业方向为图论及其应用。