給定團(tuán)數(shù)的圖的距離無符號(hào)拉普拉斯譜半徑

李金溪, 楊 墁, 尤利華

(華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院， 廣州 510631)

?

給定團(tuán)數(shù)的圖的距離無符號(hào)拉普拉斯譜半徑

李金溪, 楊 墁, 尤利華*

(華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院， 廣州 510631)

設(shè)G是n階簡(jiǎn)單連通圖,T(G)表示圖G的點(diǎn)傳遞度對(duì)角矩陣,D(G)表示距離矩陣,G的距離無符號(hào)拉普拉斯矩陣定義為：Q(G)=T(G)+D(G),相應(yīng)的譜半徑(即最大特征值)記作qD(G). 圖G中一個(gè)相互鄰接的頂點(diǎn)子集稱為G的一個(gè)團(tuán),定義G的團(tuán)數(shù)為其最大團(tuán)的頂點(diǎn)個(gè)數(shù),記作ω(G). 圖G的一個(gè)正常著色是指使得G中任意2個(gè)相鄰的頂點(diǎn)著不同顏色的一種著色方案. 在G的所有正常著色中,所需顏色數(shù)目的最小值稱為G的色數(shù),記作(G). 顯見,(G)≥ω(G). 為了研究給定團(tuán)數(shù)ω(G)=ω的n階簡(jiǎn)單連通圖G中取得最小距離無符號(hào)拉普拉斯譜半徑的極圖,文中綜合運(yùn)用代數(shù)、矩陣論與圖論等方法,分如下2種情形進(jìn)行討論:(1)(G)=ω(G)=ω;(2)(G)>ω(G)=ω. 證明了Turn圖Tn,ω是團(tuán)數(shù)為ω的n階簡(jiǎn)單連通圖中具有最小距離無符號(hào)拉普拉斯譜半徑的唯一圖.

連通圖; 團(tuán)數(shù); 距離無符號(hào)拉普拉斯譜半徑

Keywords：connectedgraph;cliquenumber;distancesignlessLaplacianspectralradius

另一方面,關(guān)于給定團(tuán)數(shù)的圖或有向圖的譜半徑、拉普拉斯或無符號(hào)拉普拉斯譜半徑的研究,請(qǐng)參看文獻(xiàn)[7-13].

所使用的方法技巧得益于文獻(xiàn)[7]的啟發(fā),刻畫了給定團(tuán)數(shù)的連通圖中取得最小距離無符號(hào)拉普拉斯譜半徑的極圖.

設(shè)M是n×n矩陣,1,2,…,n為M的特征值. 一般來說,M不是對(duì)稱矩陣,所以其特征值可能是復(fù)數(shù). 不妨假設(shè)|1|≥|2|≥…≥|n|. 把M的特征值的模的最大值|1|定義為M的譜半徑,記為ρ(M). 由Perron-Frobenius定理可知:若M是非負(fù)矩陣,則其譜半徑ρ(M)是M的一個(gè)特征值; 若M是非負(fù)不可約矩陣,則其譜半徑ρ(M)=1是單根.

設(shè)G=(V(G),E(G))是連通圖,其頂點(diǎn)集為V(G)={v1,v2,…,vn},邊集為E(G). 對(duì)于任意的u,vV(G),以G中連接u、v的最短路的長(zhǎng)度表示u、v兩者之間的距離,記作dG(u,v)或duv. 對(duì)于任意的uV(G),以頂點(diǎn)u到G中其他所有頂點(diǎn)的距離的和表示頂點(diǎn)u的傳遞度(transmission),記作TG(u). 如果G中所有點(diǎn)的傳遞度相等,即TG(v1)=TG(v2)=…=TG(vn),稱圖G是距離正則圖.

G的距離矩陣是n×n矩陣,記作D(G)=(dij),其中dij=dvivj. 顯見，連通圖G的距離矩陣是非負(fù)不可約矩陣，其距離譜半徑定義為其距離矩陣D(G)的譜半徑,即為D(G)的最大特征值,記作ρD(G). 事實(shí)上,頂點(diǎn)vi的傳遞度TG(vi)是D(G)的第i行的行和,其中1≤i≤n. 稱對(duì)角矩陣T(G)=diag(TG(v1),TG(v2),…,TG(vn))為G的點(diǎn)傳遞度對(duì)角矩陣. AOUCHICHE和HANSEN[5]定義G的距離無符號(hào)拉普拉斯矩陣為：Q(G)=T(G)+D(G). 顯見Q(G)是非負(fù)不可約的、對(duì)稱的、半正定的. 定義連通圖G的距離無符號(hào)拉普拉斯譜半徑是其距離無符號(hào)拉普拉斯矩陣Q(G)的譜半徑,即為Q(G)的最大特征值,記作qD(G).

V(G)中相互鄰接的頂點(diǎn)子集是圖G的一個(gè)團(tuán),定義G中最大團(tuán)的頂點(diǎn)個(gè)數(shù)為G的團(tuán)數(shù),記作ω(G). 定義圖G的一個(gè)正常著色是指使得G中任意2個(gè)相鄰的頂點(diǎn)著不同顏色的一種著色方案. 在G的所有正常著色中,所需顏色數(shù)目的最小值稱為G的色數(shù),記作(G). 由于G包含一個(gè)大小為ω(G)的團(tuán),所以至少需要ω(G)種顏色來給G正常著色,因此(G)≥ω(G).

以Kn表示n階完全圖,頂點(diǎn)劃分為V1,V2,…,Vr的完全r部圖記作K|V1|,|V2|,…,|Vr|. 如果某個(gè)n階完全r部圖的頂點(diǎn)劃分滿足其每個(gè)部分的頂點(diǎn)個(gè)數(shù)盡可能相等,則稱其為Turn圖,記作Tn,r. 顯然ω(Tn,r)=r.

其他的定義、術(shù)語以及未提到的符號(hào)可參看文獻(xiàn)[14-20].

給出基本符號(hào)和定義后,緊接著尋求和證明在給定團(tuán)數(shù)的連通圖中取得最小距離無符號(hào)拉普拉斯譜半徑的極圖.

以下所考慮的圖G為n階簡(jiǎn)單連通圖,其頂點(diǎn)集為V(G)={v1,v2,…,vn},邊集為E(G),顯見Q(G)=(qij)是不可約的、非負(fù)的、對(duì)稱的和半正定的. 由Perron-Frobenius定理,qD(G)是單根并且有一個(gè)正的單位特征向量x=(x1,x2,…,xn)Tn與之對(duì)應(yīng),這里x被稱作Q(G)的Perron向量. 從而,由

定義1[16]26設(shè)A=(aij)、B=(bij)是n×n階矩陣. 如果對(duì)于所有的i和j都有aij≤bij,記作A≤B. 如果A≤B并且A≠B,記作A

引理1[16]27設(shè)A、B為n×n非負(fù)矩陣,其譜半徑分別為ρ(A)、ρ(B). 如果A≤B,則ρ(A)≤ρ(B). 此外,如果A

根據(jù)引理1及Q(G)和qD(G)的定義,可得以下以圖的語言來描述的推論.

推論1 設(shè)G是n階圖,H是G的生成子圖,H和G均是連通的. 則

(i)qD(H)≥qD(G).

(ii) 如果H是G的真子圖，則qD(H)> qD(G).

推論2[2]1379設(shè)G為連通圖,u、v是G中任意2個(gè)不鄰接的頂點(diǎn),G+uv表示G添加邊uv,則qD(G+uv)

引理2 設(shè)G為連通圖,x=(x1,x2,…,xn)T是Q(G)的Perron向量,NG(v)是G中與頂點(diǎn)v相鄰的點(diǎn)集,vr,vsV(G). 若NG(vr){vs}=NG(vs){vr},則xr=xs.

證明 記U=V(G){vr,vs}. 由NG(vr){vs}=NG(vs){vr}及G的連通性,可知對(duì)任意的vtU有drt=dst,進(jìn)而,由

可得TG(vr)=TG(vs).

注意到

故(qD(G)+drs-TG(vr))(xr-xs)=0.再由qD(G)>TG(vr),可得xr=xs.

引理3 設(shè)G是n階連通圖,其團(tuán)數(shù)為ω(G)=ω. 若其色數(shù)(G)=ω(G)=ω,則qD(G)≥qD(Tn,ω),且等式成立當(dāng)且僅當(dāng)G?Tn,ω.

證明 以Fn,ω表示所有色數(shù)等于ω的n階圖的集合. 不妨設(shè)GFn,ω是所有色數(shù)為ω的n階圖中具有最小距離無符號(hào)拉普拉斯譜半徑的圖. 下面將證明G?Tn,ω.

由于添加邊會(huì)減小距離無符號(hào)拉普拉斯譜半徑,所以G必定是完全ω部圖. 令V1,V2,…,Vω是V(G) 的一個(gè)劃分使得G=K|V1|,|V2|,…,|Vω|. 不失一般性,對(duì)任意的k{1,2,…,ω},假設(shè)|Vk|=nk,且|V1|≤|V2|≤…≤|Vω|.

如果對(duì)任意1≤i1. 不失一般性,假設(shè)|V1|≤|V2|-2(即n1≤n2-2). 記H=K|U1|,|U2|,…,|Uω|,這里U1=V1∪{u},其中uV2,U2=V2{u}且對(duì)任意的k{3,…,ω},均有Uk=Vk(圖1). 顯見HFn,ω. 下面,將證明qD(G)>qD(H).

圖1 從G到H的變化

設(shè)y為Q(H)的Perron向量. 由引理2可知Uk的所有頂點(diǎn)具有相同的Perron分量. 用yk表示Uk中頂點(diǎn)的Perron分量,其中k=1,2,…,ω. 顯見，由于Perron向量y?0,故對(duì)任意的k{1,2,…,ω}有yk>0. 注意到對(duì)任意viV1,有dG(u,vi)-dH(u,vi)=-1成立,對(duì)任意vjV2{u}=U2, 有dG(u,vj)-dH(u,vj)=1成立,且對(duì)任意的點(diǎn)對(duì)vs和vt,有dG(vs,vt)-dH(vs,vt)=0成立,故以下幾個(gè)結(jié)論成立: (1)TG(u)-TH(u)=n2-n1-1;(2)對(duì)任意viV1,有TG(vi)-TH(vi)=-1;(3)對(duì)任意vjV2{u}=U2,有TG(vj)-TH(vj)=1;(4)對(duì)任意vtV(G)(V1∪V2),有TG(vt)-TH(vt)=0.

再由n1≤n2-2

qD(G)-qD(H)≥yT(Q(G)-Q(H))y=

下面證明y2≥y1. 注意到

qD(H)y1=(n+n1-1)y1+2n1y1+(n2-1)y2+

∑k=3,4,…,ωnkyk,

qD(H)y2=(n+n2-3)y2+(n1+1)y1+2(n2-2)y2+

∑k=3,4,…,ωnkyk,

則

qD(H)y1-qD(H)y2=(n+2n1-2)y1-(n+2n2-6)y2,

設(shè)G是n階連通圖,其團(tuán)數(shù)為ω(G)=ω. 下面分幾種情形討論：(i)ω|n; (ii)ω>n/2; (iii)ωω(G)=ω. 分別證明qD(G)≥qD(Tn,ω),且等式成立當(dāng)且僅當(dāng)G?Tn,ω.

引理4(Turn’sTheorem)[7]387設(shè)G是不含ω+1團(tuán)的n階連通圖,則G的邊數(shù)e(G)≤e(Tn,ω),且等式成立當(dāng)且僅當(dāng)G?Tn,ω.

引理5[3]3957設(shè)G是n階連通圖,則q(G)≥4σ(G)/n,且等式成立當(dāng)且僅當(dāng)G 是距離正則圖.

引理6 設(shè)G是n階連通圖,其團(tuán)數(shù)為ω(G)=ω,則

(i)qD(G)≥4σ(Tn,ω)/n,且等式成立當(dāng)且僅當(dāng)G?Tn,ω.

(ii)若ω|n,則qD(G)≥qD(Tn,ω)=2(n+n/ω-2),且等式成立當(dāng)且僅當(dāng)G?Tn,ω.

圖2 G(|V1|,|V2|,…,|Vω|)中一個(gè)ω團(tuán)和一個(gè)(n-ω)團(tuán)

Figure 2 Anω-clique and an (n-ω)-clique inG(|V1|,|V2|,…,|Vω|)

證明 不妨設(shè)H=G(|V1|,|V2|,…,|Vω|)是集合n,ω中具有最小距離無符號(hào)拉普拉斯譜半徑的圖. 若HG(0,0,…,0,1,1,…,1),那么必存在某個(gè)k{1,2,…,ω}使得|Vk|≥2. 不失一般性,我們假設(shè)i是最小的指數(shù)使得|Vi|=ni≥2,j是最大的指數(shù)使得Vj=?(事實(shí)上,這樣的j一定存在,因?yàn)榱頗1=G(|U1|,|U2|,…,|Uω|),其中V(Kω)={v1,v2,…,vω},U=U1∪U2∪…∪Uω=V(Kn-ω),且存在某個(gè)頂點(diǎn)uVi使得Ui=Vi{u},Uj={u},而對(duì)任意的k{1,2,…,ω}{i,j}均有Uk=Vk(圖3). 顯見,H1n,ω.

圖3 從H到H1的變化

下面證明qD(H)>qD(H1). 令y是Q(H1)的Perron向量且分量yvk對(duì)應(yīng)頂點(diǎn)vk(k=1,2,…,ω),由引理2,Uk的所有頂點(diǎn)有相同的Perron分量,并且用yk表示Uk中的頂點(diǎn)的Perron分量,其中k=1,2,…,ω. 很顯然,由y?0 可知對(duì)任意的k=1,2,…,ω,有yk>0 且yvk>0. 注意到dH(u,vi)-dH1(u,vi)=1,dH(u,vj)-dH1(u,vj)=-1,對(duì)任意的點(diǎn)對(duì)s和t,dH(s,t)-dH1(s,t)=0,且TH(vi)-TH1(vi)=1,TH(vj)-TH1(vj)=-1,對(duì)任意的點(diǎn)v,TH(v)-TH1(v)=0. 從而由瑞利商定理,可得

qD(H)-qD(H1)≥yT(Q(H)-Q(H1))y=

(yvi+yvj+2yj)(yvi-yvj).

下面證明yvi≥yvj. 注意到

從而,qD(H1)(yvi-yvj)=(n+ni-3)yvi-(n-1)yvj+(ni-1)yi-yj. 又由ni≥2 可知n+ni-3≥n-1,ni-1≥1,因此

(qD(H1)-(n-1))(yvi-yvj)≥yi-yj.

(1)

另一方面,注意到

(2)

由式(1)和式(2),可得

若qD(H)=qD(H1),則yvi=yvj,yi=yj且y也是Q(H)的Perron向量. 所以,0=qD(H)(yvi-yvj)=(n+ni-2)yvi-(n-2)yvj+niyi>0,矛盾. 因此，qD(H)>qD(H1),這也與H的定義矛盾. 證明完畢.

引理8 設(shè)G是團(tuán)數(shù)ω(G)=ω的n階連通圖. 若ω>n/2,則qD(G)≥qD(Tn,ω),且等式成立當(dāng)且僅當(dāng)G?Tn,ω.

證明 設(shè)U={v1,v2,…,vω}是G的一個(gè)團(tuán),且記W=V(G)U. 由于團(tuán)數(shù)ω(G)=ω,從而對(duì)于V中的任意頂點(diǎn)來說，其最多有ω-1個(gè)鄰點(diǎn)在U中. 這就意味著在圖的同構(gòu)的意義下,存在W的某個(gè)劃分V1∪V2∪…∪Vω,使得G是G(|V1|,|V2|,…,|Vω|)的生成子圖. 再由推論1和引理7,有qD(G)≥qD(G(|V1|,|V2|,…,|Vω|))≥qD(Tn,ω),且等式成立當(dāng)且僅當(dāng)G?Tn,ω.

引理9 設(shè)ω、n為正整數(shù)且ω≤n,則

x1=q-(n+2k-4)q-(n+2k-2)x2.

(6)

由式(4)和式(6),可得

q2-(3n+4k-6)q+(2n2+4k2-10n-12k+4nk+

2k2ω+2kω+8)=0.

(7)

解方程(7),易見式(3)成立.

令ω=n,由引理9可得

推論3[5]30qD(Kn)=2n-2.

引理10[21]設(shè)G是團(tuán)數(shù)ω(G)≤ω的n階連通圖. 若(G)>ω且,則e(G)≤e(Tn,ω)-?.

由引理5和引理10,可得

顯見e(Tn,ω)=(n2-n-2nk+k2ω+kω)/2,因此有

(8)

為了證明qD(G)>qD(Tn,ω),由式(3)和式(8),只需證明

(9)

化簡(jiǎn)式(9),接下來證明

nk(k+1)(n-ω-2kω)+[(k2ω+kω)-2(k-1)]2+

(k-1)(n2+2n+4nk)>0.

(10)

令n=kω+k0,其中0≤k0<ω. 那么由式(10),有

4(k-1)2+kω[(k-1)(kω-2)+k0(k-3)]+

(k2+2k-1)k02+2k0(2k+1)(k-1)>0.

(11)

為了證明式(11)是正確的,需證

(k-1)(kω-2)+k0(k-3)>0.

(12)

注意到ω

定理1 設(shè)G是n階連通圖,其團(tuán)數(shù)為ω(G)=ω,則qD(G)≥qD(Tn,ω),且等式成立當(dāng)且僅當(dāng)G?Tn,ω.

子情形2.1:ω=n/2. 此時(shí),由引理6可知結(jié)論成立.

子情形2.2:ω>n/2. 此時(shí),由引理8可知結(jié)論成立.

子情形2.3:ω

結(jié)合以上情形的討論,結(jié)論證明完畢.

[1] GRAHAM R L,LOVSZ L. Distance matrix polynomials of trees[J]. Department of Mathematics,1978,29:60-88.

[2] XING R D,ZHOU B,LI J P. On the distance signless Laplacian spectral radius of graphs[J]. Linear and Multilinear Algebra,2014,62:1377-1387.

[3] XING R D,ZHOU B. On the distance and distance signless Laplacian spectral radii of bicyclic graphs[J]. Linear Algebra and Its Applications,2013,439:3955-3963.

[4] TIAN F L,WONG D,ROU J L. Proof for four conjectures about the distance Laplacian and distance signless Laplacian eigenvalues of a graph[J]. Linear Algebra and Its Applications,2015,471:10-20.

[5] AOUCHICHE M,HANSEN P. Two Laplacians for the distance matrix of a graph[J]. Linear Algebra and Its Applications,2013,439:21-33.

[6] DAS K C. Proof of conjectures on the distance signless Laplacian eigenvalues of graphs[J]. Linear Algebra and Its Applications,2015,467:100-115.

[7] ZHAI M Q,YU G L,SHU J L. Clique number and distance spectral radii of graphs[J]. Ars Combinatoria,2012,104:385-392.

[9]LINHQ,SHUJL,WUYR,etal.Spectralradiusofstronglyconnecteddigraphs[J].DiscreteMathematics,2012,312:3663-3669.

[10]GUOJM,LIJX,SHIUWC.ThesmallestLaplacianspectralradiusofgraphswithagivencliquenumber[J].LinearAlgebraandItsApplications,2012,437:1109-1122.

[11]HEB,JINYL,ZHANGXD.SharpboundsforthesignlessLaplacianspectralradiusintermsofcliquenumber[J].LinearAlgebraandItsApplications,2013,438:3851-3861.[12]ZHANGJM,HUANGTZ,GUOJM.ThesmallestsignlessLaplacianspectralradiusofgraphswithagivencliquenumber[J].LinearAlgebraandItsApplications,2013,439:2562-2576.

[13]HONGWX,YOULH.SpectralradiusandsignlessLaplacianspectralradiusofstronglyconnecteddigraphs[J].LinearAlgebraandItsApplications,2014,457:93-113.

[14]BONDYJA,MURTYUSR.Graphtheorywithapplications[M].London:Macmillan,1976.

[15]BONDYJA,MURTYUSR.Graphtheory[M].NewYork:Springer,2008.

[16]BERMANA,ROBERTJP.Nonnegativematricesinthemathematicalsciences[M].NewYork:AcademicPress,1979.

[17]HORNRA,JOHNSONCR.Matrixanalysis[M].England:CambridgeUniversity,1986.

[18]MINCH.Nonnegativematrices[M].NewYork:JohnWileyandSonsInc,1988.

[19]JENSENJB,GUTING.Digraphstheory[M].NewYork:Springer,2001.

[20]BOLLOBSB.Extremalgraphtheory[M].NewYork:AcademicPress,1978.

[21]KANGM,PIKHURKOO.MaximumKr+1-freegraphswhicharenotr-partite[J].MatematychniStudii,2005,24:13.

【中文責(zé)編：莊曉瓊 英文責(zé)編：肖菁】

The Distance Signless Laplacian Spectral Radii of Graphs with Given Clique Number

LIJinxi,YANGMan,YOULihua*

(School of Mathematicsal Sciences South China Normal University, Guangzhou 510631, China)

LetGbe a simple connected graph, T(G)bethediagonalmatrixofvertextransmissionofGandD(G)bethedistancematrixofG,thedistancesignlessLaplacianmatrixofGisthen×nmatrixdefinedasQ(G)=T(G)+D(G),andthedistancesignlessLaplacianspectralradiusofG,denotedbyqD(G).Recallthatacliqueofagraphisasetofmutuallyadjacentverticesandthecliquenumberω(G)isthenumberofverticesinthelargestcliqueinG.Thechromaticnumber(G) is the smallest number of colors needed to color the vertices ofGsuch that any two adjacent vertices have different colors. It is clear that(G)≥ω(G). In order to look for what’s the extremal graph with the minimal distance signless Laplacian spectral radius among all simple connected graphs with given clique numberω, this paper investigates the following two cases by combining the methods in the graph theory, algebra and matrix theory: (1)(G)=ω(G)=ω; (2)(G)>ω(G)=ω, and shows that Turn graphTn,ωis the unique graph having the minimal distance signless Laplacian spectral radius among all simple connected graphs withnvertices and given clique numberω.

2015-10-28 《華南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)》網(wǎng)址：http://journal.scnu.edu.cn/n

國家自然科學(xué)基金項(xiàng)目(11571123); 廣東省自然科學(xué)基金項(xiàng)目(2015A030313377)

O151.21

A

1000-5463(2016)06-0118-06

*通訊作者:尤利華,教授,Email:ylhua@scnu.edu.cn.