程霄
（新疆农业大学 数理学院，新疆 乌鲁木齐 830052）
图谱理论是代数图论的重要研究领域.其中，图的拟拉普拉斯谱问题在微分方程问题，矩阵理论，量子化学、生物学以及复杂网络问题中有重要的应用，是目前研究的活跃问题.
本文讨论的图，均为简单无向图（不包括环和平行边），未定义的概念在文[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.图的拟拉普拉斯（signless Laplacian）矩阵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具有相同的特征多项式；
（3）tr(Mi)=tr(Hi)(i=1,2,…,n).
引理2[7] 偶图的拟拉普拉斯矩阵和Laplacian矩阵具有相同的特征多项式，即QG(x)=LG(x)
很多文献提到过此定理，但没给出详细证明，其过程如下.
证明 设G是偶图，两部集的阶数为n1,n2.结合分块矩阵的理论，顶点按一定的顺序标号，G的邻接矩阵A可写成
的形式，其中B为n1×n2阶矩阵.可以将图G的度对角矩阵对应的记为
，则
其对应的特征多项式为：
接下来，对LG(x)的前n1行和n1列分别都乘以-1，那正好得到QG(x)，由此得证.
为了证明似星树的拟拉普拉斯谱的性质，需要引入矩阵理论中的交错原则.考虑两个实数序列：
?琢1≥?琢2≥…≥?琢n，?茁1≥?茁2≥…≥?茁m(m<n)
如果?琢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=[I 0]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.那么：
qi+1(G)-1≤qi(G-v)≤qi(G)，i=1,2,…,n-1
其中，右边的等号成立，当且仅当v是孤立点.
为了讨论似星树的拟拉普拉斯谱半径问题，需要引入以下定理：
引理7[8] 若n阶图G至少有一条边，设其最大度为△，那么：
q1≥?滋1≥△+1
若G是连通的，则当且仅当G是偶图，有第一个等号成立；当且仅当=n-1.有第二个等号成立.
引理8[10] 设G为n阶图，则有
q1≤λ1+△
其中，λ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，那么显然它有下面的性质：
路Pn的拟拉普拉斯谱为2+2cos
,i=1,2,…,n.那么，Pn的所有拟拉普拉斯特征值都小于4.结合上述性质可以知道，S(n1,n2,…,nk)-v的Q-特征值也都小于4.下面把似星树S(n1,n2,…,nk)简写为S，由引理6可知：
qi+1(S)-1≤qi(S-v)≤qi(S)，i=1,2,…,n-1
因此，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].
教育期刊网 http://www.jyqkw.com
参考文献：
〔1〕Bondy J A, 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〕VAN D R E,HAEMERS H W.Which graphs are 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 trees whose maximum degree exceed4 are determined by their Q-spectra[J]. Linear Algebra and itsAppli-cations,2012,436: 143–151.
〔14〕S.N. Qiao. The starlike trees with maximum and minimum secondorder connectivity index[J]. J Appl. Math Comput 2012( 39):523–532.
