关于似星树拟拉普拉斯谱的性质探讨

程霄

（新疆农业大学 数理学院，新疆 乌鲁木齐 830052）

关于似星树拟拉普拉斯谱的性质探讨

程霄

（新疆农业大学 数理学院，新疆 乌鲁木齐 830052）

利用似星树的简单性质，结合偶图的Laplacian谱和拟拉普拉斯谱的关系，得到了拟拉普拉斯同谱的似星树同构的性质.进一步，通过矩阵的交错理论，结合图操作方法，得到了似星树拟拉普拉斯谱的另一个性质.最后，根据其邻接谱半径的界，得到了似星树的拟拉谱拉斯谱半径的一个上界.

拟拉普拉斯矩阵特征值；似星树；谱半径；谱宽度

图谱理论是代数图论的重要研究领域.其中，图的拟拉普拉斯谱问题在微分方程问题，矩阵理论，量子化学、生物学以及复杂网络问题中有重要的应用，是目前研究的活跃问题.

本文讨论的图，均为简单无向图（不包括环和平行边），未定义的概念在文［1］中都可以找到.设G=（V，E）是n阶图，其顶点集为V，点集为E.分别记D（G）=diag（du：u∈V）和A（G）= （auv）表示图的度矩阵和邻接矩阵.其中，du是顶点的度；当uv相邻时，auv=1；否则，auv=0；邻接矩阵的特征值记为λ1≥λ2≥…≥λn.图G的Laplacian矩阵定义为L（G）=D（G）-A（G），其特征多项式为LG（x）.由于L（G）是一个实对称半正定的奇异矩阵，故设其特征值为：μ1≥μ2≥…≥μn=0.图的拟拉普拉斯（signlessLaplacian）矩阵Q（G）=D（G）+A（G），其特征多项式为QG（x）.由于A（G）是一个实对称的、半正定的非负矩阵，则设其特征值为q1≥q2≥…≥qn≥0.

图G的邻接矩阵特征值、Laplacian矩阵特征值和拟拉普拉斯矩阵特征值都是图的不变量.由于后两个矩阵都加入了顶点的度，所以其特征值更能反映图的性质.关于图的谱半径问题以及谱确定问题，一直以来都是前沿热点问题.

似星树（starlike tree）是一类特殊的树图，即只有一个顶点的度数大于2的树.关于其邻接谱半径问题以及Laplacian谱确定问题研究，已经取得了大量的研究成果［3-5］.不过关于其拟拉普拉斯谱的性质的研究较少.

本文在已有的研究基础上，通过矩阵理论、图论的相关知识，结合图操作等方法，进一步对似星树的拟拉普拉斯特征值，谱半径，谱宽度等问题进行探讨，得到了一些结论.

1 基本理论

引理1［6］设n×n矩阵M和H，则下面的关系是等价的：

（1）M和H具有相同的谱；

（2）M和H具有相同的特征多项式；

引理2［7］偶图的拟拉普拉斯矩阵和Laplacian矩阵具有相同的特征多项式，即QG（x）=LG（x）

很多文献提到过此定理，但没给出详细证明，其过程如下.

证明 设G是偶图，两部集的阶数为n1，n2.结合分块矩阵的理论，顶点按一定的顺序标号，G的邻接矩阵A可写成

接下来，对LG（x）的前n1行和n1列分别都乘以-1，那正好得到QG（x），由此得证.

为了证明似星树的拟拉普拉斯谱的性质，需要引入矩阵理论中的交错原则.考虑两个实数序列：

如果αi≥βi≥αn-m+i（i=1，2，…，m），则称第二个序列交错于第一个序列.

引理3［2］设S是一个n×m的实矩阵，满足STS=I.同时，设A是一个n阶实对称矩阵，且特征值为α1≥α2≥…≥αn.定义B=STAS，其特征值为：β1≥β2≥…≥βm，那么B的特征值序列交错于A的特征值序列.

在上述定理中，若令S=［I0］T，那么B就是A的一个主子阵，则有：

引理4［2］设B是对称矩阵A的主子阵，则B的特征值序列交错于A的特征值序列.

利用此引理，就能得到图谱理论中相应的交错定理.

引理5［8］（边交错定理）设图G有n个顶点，m条边.且e∈E（G），并设G的拟拉普拉斯特征值和G-e的拟拉普拉斯特征值分别为：q1≥q2≥…≥qn，s1≥s2≥…≥sn，那么：

0≤sn≤qn≤…≤s2≤q2≤s1≤q1

文献［9］中，利用此引理，同时结合矩阵理论中的Wely's不等式和Cquchy交错定理，得到了关于拟拉普拉斯特征值的点交错定理.

引理6［9］（点交错定理）设图G为n阶图，顶点集为V （G），且v∈V（G），设G的拟拉普拉斯特征值和G-v的拟拉普拉斯特征值分别为q1（G）和qi（G-v），其中i=1，2，…，n.那么：

其中，右边的等号成立，当且仅当v是孤立点.

为了讨论似星树的拟拉普拉斯谱半径问题，需要引入以下定理：

引理7［8］若n阶图G至少有一条边，设其最大度为Δ，那么：

若G是连通的，则当且仅当G是偶图，有第一个等号成立；当且仅当=n-1.有第二个等号成立.

引理8［10］设G为n阶图，则有

其中，λ1是图G的邻接谱半径；当且仅当G是正则的，等号成立.

2 主要结果

定义1［11］只有一个顶点的度数大于2的树，称为似星树.记为S（n1，n2，…，nk），其中n1，n2，…，nk是正整数，n1≥n2≥…≥nk≥1，且顶点最大度为k（k≥3）.

定理1 如果两棵似星树S（n1，n2，…，nk）和S（m1，m2，…，mk）是拟拉普拉斯同谱图，那么它们一定是同构的.

证明 文献［12］中通过似星树的线图的性质，证明了只要两棵似星树是同谱的，则一定也是同构的.树是一类特殊的偶图，由引理2可知，偶图的拟拉普拉斯谱等于其Laplacian谱，那么结论得证.

定理2 似星树最多只有一个拟拉普拉斯特征值不小于5.

证明 由似星树的定义，不妨设顶点v的度数为k，那么显然它有下面的性质：

因此，q2（S）-1≤q1（S-v）≤q1（S），又因为q1（S-v）＜4，那么显然q2（S）＜5.结论得证.

定理3 设q1是Starlike树S（n1，n2，…，nk）的Q-谱半径，且Δ是其最大度，那么对任意的n1≥n2≥…≥nk≥1，都有：

其中，n=n1+n2+…+nk+1，下界的等号成立，当且仅当n1=n2=…=nk=1，即G是星图Sn.

证明 一方面，由边交错定理和引理7易得q1的下界.当且仅当n1=n2=…=nk=1时，G是星图Sn，q1取得最小值.另一方面，由引理8可知，q1≤λ1+Δ，只要根据似星树的邻接谱半径的界，便可找到q1的上界，在文献［11］中，证明了似星树S（n1，n2，…，nk）的邻接谱半径的一个界，即对任意的n1≥n2≥…≥nk≥1，都有：

由似星树的定义可知，k是该图的最大度，也即

综上所述，结论得证.

对于拟拉普拉斯谱宽度的研究也是一个方向，通过上面的定理易得下面的结论.

推论 设SQ（S）是似星树S（n1，n2，…，nk）的拟拉普拉斯谱宽度（即q1-qn）.且Δ是其最大度，那么对任意的n1≥n2≥…≥nk≥1，都有：

其中，n=n1+n2+…+nk+1，下界的等号成立，当且仅当n1=n2=…=nk=1，即G是星图Sn.

3 结束语

针对一类特殊的图——似星树，得到了其部分拟拉普拉斯谱的性质.关于似星树的拟拉普拉斯谱的研究，还值得深入讨论，谱确定问题和顶点连通度问题仍是重要研究方向［13-14］.

〔1〕Bondy JA，Murty U S R.Graph theory with applications［M］.New York：Macmillan，1976.

〔2〕A.E.Brouwer，W.H.Haemers.Spectra of graphs［M］. Springer Verlag，2011.

〔3〕姚瑶，徐美进，杨文杰，等.最大度为4的似星树的谱半径［J］.辽宁工业大学学报（自然科学版），2014，34（01）：67-70.

〔4〕沈小玲.关于图的谱确定问题［D］.长沙：湖南师范大学，2005.

〔5〕姚瑶.一类似星树的谱半径问题研究［D］.锦州：辽宁工业大学，2014.

〔6〕VANDRE，HAEMERSH W.Whichgraphsare determinedby their spectrum ［J］.Linear Algebra Appl.，2003，373：241-272.

〔7〕D.Cvetkovic，P.Rowlinson，S.K.Simic，Signless Laplacians of finite graphs［J］.Linear AlgebraAppl.，2007，423（1）：155-171.

〔8〕D.Cvetkovic，P.Rowlinson，S.K.Simic.Eigenvalue bounds for the signless Laplacian ［J］.Publ.Inst.Math（Beograd），2007，81（95）：11-27.

〔9〕J.F Wang，F.Belardo.A note on the signless Laplacian eigenvalues of graphs ［J］. Linear Algebra and its Applications，2011，435：2585-2590.

〔10〕P.Hansen，C.Lucas，Bounds and conjectures for the signless Laplacian indexof graphs［J］.Linear Algebra and itsApplications，2010，432：3319-3336.

〔11〕M.Lepovic，I.gutman.Some Spectral Properties of Stralike trees［J］.Bull.Acad.Serbe Sci.Arts，Cl.Sci.Math. Natur.，Sci.Math，2001，137（33）：99-105.

〔12〕M.Lepovic.Some results on Starlike trees and Sunlike graphs［J］.J.Appl.Math.&Computing，2003 11（1-2）：109-123.

〔13〕C.J.Bu，J.Zhou，Starlike treeswhose maximum degree exceed4 are determined by their Q-spectra［J］. Linear Algebra and itsAppli-cations，2012，436：143-151.

〔14〕S.N.Qiao.Thestarlike treeswith maximum and minimum secondorder connectivity index［J］.J Appl. Math Comput 2012（39）：523-532.

O157.5

A

1673-260X（2015）05-0004-02