變換為團路的團樹的距離無符號拉普拉斯譜半徑

朱銀芬，胡衛敏，馮小云

(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)；自治區高?？蒲杏媱澲攸c項目“基于少數民族地區高校數學專業分類教學改革的思考與探索”(XJEDU2014I040)；新疆師范大學研究生科技創新項目“基于圖的譜的研究”(XSY201602012)。

朱銀芬(1991- )，女，碩士研究生，從事圖論與組合數學研究。

胡衛敏(1968- )，男，教授，碩士生導師，從事應用數學研究。

O157.5

A

2095-7602(2017)08-0001-05