變換為團(tuán)路的團(tuán)樹的距離無符號拉普拉斯譜半徑

朱銀芬，胡衛(wèi)敏，馮小云

(1.新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，新疆烏魯木齊 830017；2.伊犁師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，新疆伊寧 835000)

變換為團(tuán)路的團(tuán)樹的距離無符號拉普拉斯譜半徑

朱銀芬1，胡衛(wèi)敏2，馮小云1

(1.新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，新疆烏魯木齊 830017；2.伊犁師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，新疆伊寧 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的距離無符號拉普拉斯譜半徑.本文分別確定了變換為團(tuán)路的團(tuán)樹中具有最大與最小的距離無符號拉普拉斯譜半徑的極圖.

距離無符號拉普拉斯譜半徑；團(tuán)樹；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]引入了圖的距離拉普拉斯譜與距離無符號拉普拉斯譜的概念，并且在文獻(xiàn)[2]中證明了在點數(shù)為n的樹中星圖Sn具有最小距離拉普拉斯譜半徑.近年來，關(guān)于距離拉普拉斯譜與距離無符號拉普拉斯譜的研究已經(jīng)有了長足的進(jìn)展.Xing R與Zhou B[3]唯一確定了雙圈圖中具有最小距離譜半徑與最小距離無符號拉普拉斯譜半徑的圖.Xing R，Zhou B和Li J[4]分別確定了在樹、單圈圖、雙圈圖、給定懸掛點數(shù)與固定連通度的連通圖中具有最小距離無符號拉普拉斯譜半徑的圖.牛愛紅，樊丹丹與王國平[5]得到了固定連通性與匹配數(shù)的雙圈圖中具有最小距離拉普拉斯譜半徑的極圖.Lin H和Zhou B[6]刻畫了在固定懸掛點數(shù)與邊連通性的圖中具有最小的距離拉普拉斯譜半徑的唯一圖的特性.

圖G的一個沒有割點的最大的連通子圖叫作圖G的一個塊.若這個塊是完全圖，則稱這個塊為圖G的團(tuán).若圖G的每個塊都是團(tuán)，稱G為團(tuán)樹.若將一個團(tuán)樹中的每個團(tuán)都用一條邊替換后得到一個路或者星，那么稱這個團(tuán)樹為團(tuán)路或者團(tuán)星.Lin H，Liu R和Lu X[7]分別確定了固定團(tuán)數(shù)的團(tuán)樹中具有最大和最小的距離譜半徑的團(tuán)樹及最大與最小的距離能的團(tuán)樹.本文分別刻畫了變換為團(tuán)路的團(tuán)樹具有最大與最小的距離無符號拉普拉斯譜半徑的極圖.

2 k-T正則連通圖與團(tuán)樹的距離無符號拉普拉斯矩陣

讓Jm×n表示m×n階的所有元素都為1的矩陣.特別地，當(dāng)m=n時，用Jm代替Jm×m，讓In表示n階單位矩陣.

定理2.1 設(shè)G1是一個連通的k-T正則圖，將完全圖Kt中的一個點與G1中的一個點u粘在一起得到的圖記為G，那么det(QD(G))與點u的選擇無關(guān).

證明 設(shè)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的選擇無關(guān).

3 變換為團(tuán)路的團(tuán)樹最大距離無符號拉普拉斯譜半徑的極圖

設(shè)連通圖G的點集V(G)={v1,v2,…,vn}，λQ(G)對應(yīng)的正的單位向量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).

如果一個團(tuán)路的所有割點構(gòu)成的路P=v1v2…vk-1，那么就稱vivi+1對應(yīng)的團(tuán)為這個團(tuán)路的第i+1個團(tuán)(i=1,2,…,k-2)；特別地，稱v1左邊的團(tuán)為第1個團(tuán)，稱vk-1的右邊的團(tuán)為第k個團(tuán).讓Pn1…nk表示具有k(k≥2)個團(tuán)，且第i個團(tuán)的點數(shù)為ni(i=1,…,k)的團(tuán)路.

引理3.1 讓Pn1,…,nk(k≥2)如上定義，ut是Pn1…nk(k≥2)上的一個點，其中，當(dāng)2≤t≤k-1時，ut∈V(Knt)；當(dāng)t=1,k時，ut∈V(Knt){v1,vk-1}.設(shè)H是一個連通的k-T正則圖，ut與H中的點v粘在一起后得到圖Ht.那么，對于任意的t,2≤t≤k-1，有min{λQ(H1),λQ(Hk)}>λQ(Ht).

證明 設(shè)QD(Ht)的λQ(Ht)對應(yīng)的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òu)，那么記為G?H，n個點k個團(tuán)的團(tuán)路Pn1,…,nk與團(tuán)星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)

等式成立當(dāng)且僅當(dāng)Pn1,…,nk?Pm,2,…,2,n-m-k+3.

證明 如果k≤2，則結(jié)論是成立的.接下來，我們認(rèn)為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，則完成證明.否則，繼續(xù)進(jìn)行上述變換.容易看到，經(jīng)過有限次的上述變換，最終得到一個同構(gòu)于Pm,2,…,2,n-m-k+3的圖.前面的論證說明了λQ(Pm,2,…,2,n-m-k+3)>λQ(G).

定理3.3 讓G是一個具有n個點k個團(tuán)的已經(jīng)變換為團(tuán)路的團(tuán)樹，那么一定存在某個m,m≥3，使得λQ(Pm,2,…,2,n-m-k+3)≥λQ(G)，等式成立當(dāng)且僅當(dāng)G?Pm,2,…,2,n-m-k+3.

4 變換為團(tuán)路的團(tuán)樹的最小距離無符號拉普拉斯譜半徑的極圖

設(shè)v是連通的k-T正則圖G1中的一個點，Pn1,…,nk(k≥2)如第二部分定義.讓G是將v和V(Knk){vk-1}中的任意點粘在一起后得到的圖，而G1是將v和vk-1粘在一起后得到的圖.

證明 設(shè)x為λQ(G1)的Perron向量，由對稱性，對任意的v∈V(Knk){vk-1}，可以認(rèn)為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后得到的圖.則得到如下結(jié)論.

引理4.3 讓G與G2如上定義，并且滿足m>2n1，那么就有λQ(G)≥λQ(G2)，等式成立當(dāng)且僅當(dāng)G?G2.

證明 設(shè)x為QD(G2)的Perron向量，由對稱性，對任意的v∈V(Km){u}，認(rèn)為x(v)=e；對任意的v∈V(G1){u},x(v)=f.令S=∑v∈(V(G2)…∪V(GS)){u}x(v)，注意到m>2n1，由相應(yīng)的特征方程得到

λ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，結(jié)合上式得到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)個團(tuán)的團(tuán)星中只有一個團(tuán)的點數(shù)大于2的團(tuán)星.

λ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合并，得到如下結(jié)論.

[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

國家自然科學(xué)基金項目“基于圖的譜的研究”(11461071)；自治區(qū)高?？蒲杏媱澲攸c項目“基于少數(shù)民族地區(qū)高校數(shù)學(xué)專業(yè)分類教學(xué)改革的思考與探索”(XJEDU2014I040)；新疆師范大學(xué)研究生科技創(chuàng)新項目“基于圖的譜的研究”(XSY201602012)。

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

胡衛(wèi)敏(1968- )，男，教授，碩士生導(dǎo)師，從事應(yīng)用數(shù)學(xué)研究。

O157.5

A

2095-7602(2017)08-0001-05