李金溪, 楊 墁, 尤利華

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

?

給定團數(shù)的圖的距離無符號拉普拉斯譜半徑

李金溪, 楊 墁, 尤利華*

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

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

連通圖; 團數(shù); 距離無符號拉普拉斯譜半徑

Keywords：connectedgraph;cliquenumber;distancesignlessLaplacianspectralradius

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

注意到

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

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

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

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

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

圖1 從G到H的變化

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

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

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

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

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

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

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

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

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

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

圖3 從H到H1的變化

下面證明qD(H)>qD(H1). 令y是Q(H1)的Perron向量且分量yvk對應頂點vk(k=1,2,…,ω),由引理2,Uk的所有頂點有相同的Perron分量,并且用yk表示Uk中的頂點的Perron分量,其中k=1,2,…,ω. 很顯然,由y?0 可知對任意的k=1,2,…,ω,有yk>0 且yvk>0. 注意到dH(u,vi)-dH1(u,vi)=1,dH(u,vj)-dH1(u,vj)=-1,對任意的點對s和t,dH(s,t)-dH1(s,t)=0,且TH(vi)-TH1(vi)=1,TH(vj)-TH1(vj)=-1,對任意的點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 設G是團數(shù)ω(G)=ω的n階連通圖. 若ω>n/2,則qD(G)≥qD(Tn,ω),且等式成立當且僅當G?Tn,ω.

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

引理9 設ω、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]設G是團數(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)

化簡式(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 設G是n階連通圖,其團數(shù)為ω(G)=ω,則qD(G)≥qD(Tn,ω),且等式成立當且僅當G?Tn,ω.

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

子情形2.2:ω>n/2. 此時,由引理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.

【中文責編：莊曉瓊 英文責編：肖菁】

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 《華南師范大學學報(自然科學版)》網(wǎng)址：http://journal.scnu.edu.cn/n

國家自然科學基金項目(11571123); 廣東省自然科學基金項目(2015A030313377)

O151.21

A

1000-5463(2016)06-0118-06

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