变换为团路的团树的距离无符号拉普拉斯谱半径

朱银芬，胡卫敏，冯小云

(1.新疆师范大学数学科学学院，新疆乌鲁木齐 830017；2.伊犁师范学院数学与统计学院，新疆伊宁 835000)

变换为团路的团树的距离无符号拉普拉斯谱半径

朱银芬1，胡卫敏2，冯小云1

(1.新疆师范大学数学科学学院，新疆乌鲁木齐 830017；2.伊犁师范学院数学与统计学院，新疆伊宁 835000)

若一个连通图G的点集是V(G)={v1,v2,…,vn}.图G的距离矩阵D(G)=(dij)，其中dij表示点vi与vj之间的距离.TrG(vi)表示点vi到图G所有其他点的距离之和，Tr(G)表示i行i列位置的元素是TrG(vi)的对角矩阵.G的距离无符号拉普拉斯矩阵QD(G)=Tr(G)+D(G).QD(G)的最大特征值λQ(G)是图G的距离无符号拉普拉斯谱半径.本文分别确定了变换为团路的团树中具有最大与最小的距离无符号拉普拉斯谱半径的极图.

距离无符号拉普拉斯谱半径；团树；k-T正则图

1 引言

图G=(V,E)中两个点u与v之间的最短路的长度叫作这两个点的距离，将其记作dG(u,v).G中的点u到图G中其他所有点的距离之和用TrG(u)表示.若图G中的每一点v都有TrG(v)=k，则G是k-T正则的.G的距离矩阵D(G)=(dij)，其中dij是点vi与vj之间的距离.让Tr(G)是(i,i)位置的元素为TrG(vi)的n阶对角矩阵.图G的距离无符号拉普拉斯矩阵QD(G)=Tr(G)+D(G)，它的最大特征值λQ(G)被称为图G的距离无符号拉普拉斯谱半径.

Aouchiche M和Hansen P[1]引入了图的距离拉普拉斯谱与距离无符号拉普拉斯谱的概念，并且在文献[2]中证明了在点数为n的树中星图Sn具有最小距离拉普拉斯谱半径.近年来，关于距离拉普拉斯谱与距离无符号拉普拉斯谱的研究已经有了长足的进展.Xing R与Zhou B[3]唯一确定了双圈图中具有最小距离谱半径与最小距离无符号拉普拉斯谱半径的图.Xing R，Zhou B和Li J[4]分别确定了在树、单圈图、双圈图、给定悬挂点数与固定连通度的连通图中具有最小距离无符号拉普拉斯谱半径的图.牛爱红，樊丹丹与王国平[5]得到了固定连通性与匹配数的双圈图中具有最小距离拉普拉斯谱半径的极图.Lin H和Zhou B[6]刻画了在固定悬挂点数与边连通性的图中具有最小的距离拉普拉斯谱半径的唯一图的特性.

图G的一个没有割点的最大的连通子图叫作图G的一个块.若这个块是完全图，则称这个块为图G的团.若图G的每个块都是团，称G为团树.若将一个团树中的每个团都用一条边替换后得到一个路或者星，那么称这个团树为团路或者团星.Lin H，Liu R和Lu X[7]分别确定了固定团数的团树中具有最大和最小的距离谱半径的团树及最大与最小的距离能的团树.本文分别刻画了变换为团路的团树具有最大与最小的距离无符号拉普拉斯谱半径的极图.

2 k-T正则连通图与团树的距离无符号拉普拉斯矩阵

让Jm×n表示m×n阶的所有元素都为1的矩阵.特别地，当m=n时，用Jm代替Jm×m，让In表示n阶单位矩阵.

定理2.1 设G1是一个连通的k-T正则图，将完全图Kt中的一个点与G1中的一个点u粘在一起得到的图记为G，那么det(QD(G))与点u的选择无关.

证明 设V(G1)={v1,v2…,vn-1,u}，让α=(dG(u,v1),dG(u,v2),…,dG(u,vn-1)),

注意到TrG1(u)=k，Trkt(u)=t-1及TrG(u)=t-1+k，则容易得到

于是，

这表明det(QD(G))与u的选择无关.

3 变换为团路的团树最大距离无符号拉普拉斯谱半径的极图

设连通图G的点集V(G)={v1,v2,…,vn}，λQ(G)对应的正的单位向量x=(x1,x2,…,xn)T被称为QD(G)的perron向量，其中xi=x(vi)(i=1,2,…,n).

对于i=1,2,…,n,明显地有λQ(G)xi=∑vj∈V(G)dij(xi+xj).

如果一个团路的所有割点构成的路P=v1v2…vk-1，那么就称vivi+1对应的团为这个团路的第i+1个团(i=1,2,…,k-2)；特别地，称v1左边的团为第1个团，称vk-1的右边的团为第k个团.让Pn1…nk表示具有k(k≥2)个团，且第i个团的点数为ni(i=1,…,k)的团路.

引理3.1 让Pn1,…,nk(k≥2)如上定义，ut是Pn1…nk(k≥2)上的一个点，其中，当2≤t≤k-1时，ut∈V(Knt)；当t=1,k时，ut∈V(Knt){v1,vk-1}.设H是一个连通的k-T正则图，ut与H中的点v粘在一起后得到图Ht.那么，对于任意的t,2≤t≤k-1，有min{λQ(H1),λQ(Hk)}>λQ(Ht).

证明 设QD(Ht)的λQ(Ht)对应的Perron向量为x=(x1,x2,…,xn)T.

令S1=∑v∈V(Kn1)∪V(Kn2)∪…∪V(Knt-1)x(v)，且令S2=∑v∈V(Knt+1)∪…∪V(Knk)x(v).

如果S1≤S2，那么

λQ(H1)-λQ(Ht) ≥xT(QD(H1)-QD(Ht))x

=∑v∈V(H)(x(v)+S2)2+(x(v)+x(ut))2-(x(v)+S1)2

若S1>S2，也有

λQ(Hk)-λQ(Ht) ≥xT(QD(Hk)-QD(Ht))x

=∑v∈V(H)(x(v)+S1)2+(x(v)+x(ut))2-(x(v)+S2)2

这表明min{λQ(H1),λQ(Hk)}>λQ(Ht).

如果G和H同构，那么记为G≅H，n个点k个团的团路Pn1,…,nk与团星Ku,2,…,2,n-k+1，其中n=n1+n2+…+nk-k+1，且ni≥2(i=1,2,…,k).

引理3.2 让Pn1,…,nk(k≥2)如上定义，那么存在某个m,m≥3，使得

λQ(Pm,2,…,2,n-m-k+3)≥λQ(Pn1,…,nk)

等式成立当且仅当Pn1,…,nk≅Pm,2,…,2,n-m-k+3.

证明 如果k≤2，则结论是成立的.接下来，我们认为k≥3，并且有2≤t

S1=∑v∈V(Kn1)∪V(Kn2)∪……∪V(Knt-1)x(v)，并且S2=∑v∈V(Knt+1)∪…∪V(Knk)x(v).

首先假定S1≥S2，此时让

由对称性可知，对任意的v∈V(Knt){vt-1,vt}，有x(v)=g.则

λQ(G′)-λQ(G) ≥xT(QD(G′)-QD(G))x

>(k-t-1)(nt-2)((S1+g)2-(S2+g)2)

这表明λQ(G′)>λQ(G).

若S1

通过类似计算，同样可得到λQ(G′)>λQ(G).

如果G′≅Pm,2,…,2,n-m-k+3，则完成证明.否则，继续进行上述变换.容易看到，经过有限次的上述变换，最终得到一个同构于Pm,2,…,2,n-m-k+3的图.前面的论证说明了λQ(Pm,2,…,2,n-m-k+3)>λQ(G).

定理3.3 让G是一个具有n个点k个团的已经变换为团路的团树，那么一定存在某个m,m≥3，使得λQ(Pm,2,…,2,n-m-k+3)≥λQ(G)，等式成立当且仅当G≅Pm,2,…,2,n-m-k+3.

4 变换为团路的团树的最小距离无符号拉普拉斯谱半径的极图

设v是连通的k-T正则图G1中的一个点，Pn1,…,nk(k≥2)如第二部分定义.让G是将v和V(Knk){vk-1}中的任意点粘在一起后得到的图，而G1是将v和vk-1粘在一起后得到的图.

证明 设x为λQ(G1)的Perron向量，由对称性，对任意的v∈V(Knk){vk-1}，可以认为x(v)=a；对任意的v∈V(Knk-1){vk-1}，x(v)=b.令S1=∑v∈V(Kn1)∪…∪V(Knk-1)x(v)，且令S2=∑v∈V(G1){vk-1}x(v)，S3=∑v∈V(Knk-1){vk-1,vk-2}x(v).

λQ(b+xk-1-a) ≥(nk+nk-1+∑v∈V(G1){vk-1}d(vk-1,v))xk-1+(2nk+nk-1+∑v∈V(G1){vk-1}d((vk-1,v)+1)-2)b-(2nk-1+∑v∈V(G1){vk-1}d((vk-1,v)+1)-nk+1)a+(S1-S3) +∑v∈V(G1){vk-1}d(vk-1,v)x(v)

>(nk+nk-1+∑v∈V(G1){vk-1}d(vk-1,v))xk-1+(2nk+nk-1+∑v∈V(G1){vk-1}d((vk-1,v)+1)-2)b-(2nk-1+∑v∈V(G1){vk-1}d((vk-1,v)+1)-nk+1)a

>(nk+nk-1+∑v∈V(G1){vk-1}d(vk-1,v))xk-1+(2nk-1+∑v∈V(G1){vk-1}d((vk-1,v)+1)-nk+1)(b-a)

>(2nk-1+∑v∈V(G1){vk-1}d((vk-1,v)+1)-nk+1)(b+xk-1-a).

由引理4.1可知，λQ(G1)>2nk-1+∑v∈V(G1){vk-1}d((vk-1,v)+1)-nk+1，这意味着b+xk-1-a>0，则

λQ(G)-λQ(G1) ≥xT(QD(G)-QD(G1))x

=(S2+S1)2+(S2+xk-1)2-(S2+a)2

>0.

这表明λQ(G)>λQ(G1).

假定v1,v2,…,vs分别是非平凡完全图G1与k-T正则G2,…,GS上的一个点.让G表示将这s个点分别粘在Km上后得到的图，让G2表示将这s个点都粘在Km上同一个点u后得到的图.则得到如下结论.

引理4.3 让G与G2如上定义，并且满足m>2n1，那么就有λQ(G)≥λQ(G2)，等式成立当且仅当G≅G2.

证明 设x为QD(G2)的Perron向量，由对称性，对任意的v∈V(Km){u}，认为x(v)=e；对任意的v∈V(G1){u},x(v)=f.令S=∑v∈(V(G2)…∪V(GS)){u}x(v)，注意到m>2n1，由相应的特征方程得到

λQ(x(u)+f-e) ≥S+(m-2n1)e+(n1+m-1)x(u)+(n1+2m-2)f

>S+x(u)+f-e>x(u)+f-e.

由引理4.1，λQ(G2)-1>0，结合上式得到x(u)+f-e>0.继而有

λQ(G)-λQ(G2) ≥xT(QD(G)-QD(G2))x

>(S+f)2+(S+x(u))2-(S+e)2

>f2+x(u)2-e2+2S(x(u)+f-e)>0.

则λQ(G)>λQ(G2).

让Ku,2,…,2,n-k+1表示具有n个点、k(k≥2)个团的团星中只有一个团的点数大于2的团星.

λQ(G)-λQ(Ku,2,…,2,n-k+1) ≥xT(QD(G)-QD(Ku,2,…,2,n-k+1))x

得到λQ(G)>λQ(Ku,2,…,2,n-k+1).

将引理4.2、引理4.3与引理4.4合并，得到如下结论.

[1]Aouchiche M,Hansen P.Two Laplacians for the distance matrix of a graph[J].Linear Algebra Appl,2013(439): 21-33.

[2]Aouchiche M,Hansen P.Some properties of the distance Laplacian eigenvalues of a graph[J].Czechoslovak Mathe matical Journal,2014(3):751-761.

[3]Xing R,Zhou B.On the distance and distance signless Laplacian spectral radii of bicyclic graphs[J].Linear Algebra Appl,2013(12):3955-3963.

[4]Xing R,Zhou B,Li J.On the distance signless Laplacian spectral radius of graphs[J].Linear and Multilinear Algebra,2014(62):1377-1387.

[5]Niu A,Fan D and Wang G.On the distance Laplacian spectra of bipartite graphs[J].Discrete Appl. Math,2015(186): 207-213.

[6]Liu H,Zhou B.On the distance Laplacian spectral radius of graphs[J].Linear Algebra Appl,2015(475):65-275.

[7]Lin H,Liu R,Lu X.The inertia and energy of the distance matrix of a connected graph[J].Linear Algebra and its Applications,2015(467):29-39.

[8]Aouchiche M,Hansen P.The distance spectra of a graphs:A survey[J].Linear Algebra Appl,2014(458):301-386.

[9]Liu H,Lu M.Bounds On the distance signless Laplacian spectral radius in terms of clique number[J].Linear and Multilinaer Algebra,2015(63):1750-1759.

[10]Nath M,Paul S.On the distance Laplacian spectra of graphs[J].Linear Algebra Appl,2014(460):97-110.

[11]Ning W,Ouyang L,Lu M.Distance spectral radius of trees with fixed number of pendant vertices[J].Linear Algebra Appl,2013(439):2240-2249.

Distance Signless Laplacian Spectral Radius of Has Been Transformed Clique Path of Clique Trees

ZHU Yin-fen1, HU Wei-min2,FENG Xiao-yun1

(1.College of Mathematics Sciences,Xinjiang Normal University,Urumqi Xinjiang 830017,China; 2.College of Mathematics Statistics,Yili Normal University,Yining Xinjiang 835000,China)

Suppose that the vertex set of a connected graphGisV(G)={v1,v2,…,vn} andD(G)=(dij) is the distance matrix ofG, wheredijis distances betweenviandvj.Then we denote the sum of distances betweenviand all other vertices ofG. LetTr(G) be then×ndiagonal matrix with its (i,i)- entry equal toTrG(vi). ThenQD(G)=Tr(G)+D(G) is the distance signless Laplacian matrix ofG.The largest eigenvalues ofQD(G), denoted byλQ(G),is distance signless Laplacian spectral radius ofG.In this paper we characterize extremal graphs with the maximal and minimum distance signless Laplacian spectral radius of transformed clique path among clique trees.

distance signless Laplacian spectral radius; clique trees;k-Tregular graph

2017-03-14

国家自然科学基金项目“基于图的谱的研究”(11461071)；自治区高校科研计划重点项目“基于少数民族地区高校数学专业分类教学改革的思考与探索”(XJEDU2014I040)；新疆师范大学研究生科技创新项目“基于图的谱的研究”(XSY201602012)。

朱银芬(1991- )，女，硕士研究生，从事图论与组合数学研究。

胡卫敏(1968- )，男，教授，硕士生导师，从事应用数学研究。

O157.5

A

2095-7602(2017)08-0001-05