图的最小特征根和拉普拉斯谱半径

图谱简介图论与组合是一门历史悠久而在近四十年又获得蓬勃发展的应用数学学科，是处理离散问题的强有力的工具，是整个离散数学的一个重要组成部分。

图论与组合包含着十分丰富的内容，按其所研究的问题的侧重点不同，可以分为图论、计数理论、组合矩阵论、最优化理论、组合设计等几个方面。

近五十年来，随着计算机科学、信息科学和系统科学的发展，图论组合及其应用的研究越来越引起人们的关注。

无论从其理论价值和实际应用的广度和深度来看，图论与组合正处于一个具有强大生命力的迅速发展的新时期。

一．图的矩阵在图论中，为了研究图的性质，人们引进了各种各样的矩阵，诸如图的邻接矩阵，拉普拉斯矩阵，规范拉普拉斯矩阵等，这些矩阵与图都有着自然的联系，代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质反映出来，这里所指的矩阵的代数性质，主要指矩阵的特征值。

图谱理论主要研究图的邻接矩阵、拉普拉斯矩阵和规范拉普拉斯矩阵的特征值及其特征向量，是当前代数图论、组合矩阵论和代数组合论共同关注的一个重要研究课题，极大地丰富和促进了图论和组合学的研究内容。

假设),(E V G =是一个无向无环的图（简单图或多重图），其中{}n v v v V ,,,21 =，{}m e e e E ,,,21 =。

定义1 G 的邻接矩阵是一个n n ⨯的矩阵n n ij a G A ⨯=)()(，其中ij a 是连接顶点i v 与j v 的边的条数。

图的邻接矩阵的特征值，是代数图论的一个基本研究课题，已经形成相当成熟的理论。

图谱的第一篇论文发表于1957 年，其结果是.定理1 令G 是n 个结点的简单连通图，则1)(1cos 2-≤≤+n G n ρπ，左边的等号成立，当且仅当G 是一路；右边的等号成立，当且仅当G 是一个完全图。

在国内该方面的研究直到1979年才出现了第一篇论文，该论文由李乔和冯克勤合写并发表在1979年的《应用数学学报》上。

代表人物: C. D. Cvetkovic.专 著：D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of graph-theory and applications, VEB Deutscher Verlag d. Wiss. Berlin, 1979; Acad. Press, New York, 1979. 1995注：1．)()(),(k ijk ij k a a A = 表示 G 中点 i v 到 j v 长为 k 的路的数目—数学归纳法。

令))(),((G E G V G =表示简单图，其中{}n v v v G V ,,,)(21 =是G 的顶点集，(G)E 是G 的边集。

)(v N G 表示G 的与点v 邻接点的集合，简记为)(v N 。

)(v d G 表示点v 的度，简记为)(v d 。

)(G ∆表示G 的最大度。

G 的邻接矩阵)()(ij a G A =是一个n n ⨯的)1,0(矩阵，其中当i v 与j v 邻接时1=ij a ；否则0=ij a 。

)(G A 的最大特征值称为G 的谱半径。

令))(),(),(()(21n v d v d v d diag G D ， =是G 的度矩阵，则)()()(G A G D G L -=称为图G 的拉普拉斯矩阵，G 的拉普拉斯特征多项式为))(det(G L xI -，记为);(x G Φ或者)(G Φ。

称)()()(G A G D G Q +=为图G 的无号拉普拉斯矩阵。

由于)(G A 、)(G L 和)(G Q 是实对称矩阵，所以它们的特征值都为实数。

)(G A 、)(G L 和)(G Q 的最大特征值分别叫做G 的谱半径（记为λ），拉普拉斯谱半径（记为ρ）和无号拉普拉斯谱半径（记为μ）。

通常我们把具有n 个点的圈，路，星图分别记为n n P C ,和1,1-n K 。

连通图G 的两点i v 和j v 之间的距离记为(,)i j dist v v 。

连通图G 的直径为G 中任意两点间距离的最大值，简记为)(G d 。

二部图，又称二分图，偶图。

指定点可以分成两个不相交的集使得在同一个集内的顶点不相邻（没有共同边）的图。

正则图指的是各顶点的度均相同的图。

令)4,(-ℜn n 表示顶点个数为n ，直径为4-n 的图的集合。

同理)3,(-ℜn n ，)2,(-ℜn n 定义如上。

如果)4,(-ℜ∈n n G 并且具有最小无号拉普拉斯谱半径，则称G 是)4,(-ℜn n 中的一个极图。

给定团数的图的距离无符号拉普拉斯谱半径李金溪;杨墁;尤利华【摘要】设G是n阶简单连通图,T(G)表示图G的点传递度对角矩阵,D(G)表示距离矩阵,G的距离无符号拉普拉斯矩阵定义为:Q(G)=T(G)+D(G),相应的谱半径(即最大特征值)记作qD(G).图G中一个相互邻接的顶点子集称为G的一个团,定义G的团数为其最大团的顶点个数,记作ω(G).图G的一个正常着色是指使得G中任意2个相邻的顶点着不同颜色的一种着色方案.在G的所有正常着色中,所需颜色数目的最小值称为G的色数,记作X(G).显见,X(G)≥ω(G).为了研究给定团数ω(G)=ω的n 阶简单连通图G中取得最小距离无符号拉普拉斯谱半径的极图,文中综合运用代数、矩阵论与图论等方法,分如下2种情形进行讨论:(1)X(G)=ω(G)=ω;(2)X(G)＞ω(G)=ω.证明了Turán图Ln.ω是团数为ω的n阶简单连通图中具有最小距离无符号拉普拉斯谱半径的唯一图.【期刊名称】《华南师范大学学报（自然科学版）》【年(卷),期】2016(048)006【总页数】6页(P118-123)【关键词】连通图;团数;距离无符号拉普拉斯谱半径【作者】李金溪;杨墁;尤利华【作者单位】华南师范大学数学科学学院,广州510631;华南师范大学数学科学学院,广州510631;华南师范大学数学科学学院,广州510631【正文语种】中文【中图分类】O151.21Key words： connected graph; clique number; distance signless Laplacian spectral radius关于图的距离谱半径的研究已经有很多年了，早期的工作可追溯到1978年[1],而距离无符号拉普拉斯谱半径是2013年才提出并研究的. 文献[2]刻画了树、单圈图和二部图中取得最小距离无符号拉普拉斯谱半径的极图,以及给定悬挂点或者连通度的连通图中取得最小距离无符号拉普拉斯谱半径的极图. 文献[3]得到了在双圈图中取得最小和第二小距离(距离无符号拉普拉斯)谱半径的极图. 2015年,文献[4]证明了图的最大、第二大距离拉普拉斯特征值和第二大距离无符号拉普拉斯特征值的猜想[5],DAS[6]证明了树中(最大度为n-2 的一棵n阶树)是取得第二小距离无符号拉普拉斯谱半径的极图.另一方面,关于给定团数的图或有向图的谱半径、拉普拉斯或无符号拉普拉斯谱半径的研究,请参看文献[7-13].所使用的方法技巧得益于文献[7]的启发,刻画了给定团数的连通图中取得最小距离无符号拉普拉斯谱半径的极图.设M是n×n矩阵,1,2,…,n为M的特征值. 一般来说,M不是对称矩阵,所以其特征值可能是复数. 不妨假设|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中最大团的顶点个数为G 的团数,记作ω(G). 定义图G 的一个正常着色是指使得G中任意2个相邻的顶点着不同颜色的一种着色方案. 在G的所有正常着色中,所需颜色数目的最小值称为G的色数,记作(G). 由于G包含一个大小为ω(G)的团,所以至少需要ω(G)种颜色来给G 正常着色,因此(G)≥ω(G).以Kn表示n阶完全图,顶点划分为V1,V2,…,Vr的完全r部图记作K|V1|,|V2|,…,|Vr|. 如果某个n阶完全r部图的顶点划分满足其每个部分的顶点个数尽可能相等,则称其为Turn图,记作Tn,r. 显然ω(Tn,r)=r.其他的定义、术语以及未提到的符号可参看文献[14-20].给出基本符号和定义后,紧接着寻求和证明在给定团数的连通图中取得最小距离无符号拉普拉斯谱半径的极图.以下所考虑的图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向量. 从而,由和Q(G)x=qD(G)x,易得.定义1[16]26 设A=(aij)、B=(bij)是n×n阶矩阵. 如果对于所有的i和j都有aij≤bij,记作A≤B. 如果A≤B并且A≠B,记作A<B. 如果对于所有的i和j都有aij<bij,记作A≪B.引理1[16]27 设A、B为n×n非负矩阵,其谱半径分别为ρ(A)、ρ(B). 如果A≤B,则ρ(A)≤ρ(B). 此外,如果A<B且B是不可约,则ρ(A)<ρ(B).根据引理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)<qD(G).引理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阶连通图,其团数为ω(G)=ω. 若其色数(G)=ω(G)=ω,则qD(G)≥qD(Tn,ω),且等式成立当且仅当G≅Tn,ω.证明以Fn,ω表示所有色数等于ω 的n 阶图的集合. 不妨设GFn,ω是所有色数为ω的n阶图中具有最小距离无符号拉普拉斯谱半径的图. 下面将证明G≅Tn,ω.由于添加边会减小距离无符号拉普拉斯谱半径,所以G必定是完全ω部图. 令V1,V2,…,Vω 是V(G) 的一个划分使得G=K|V1|,|V2|,…,|Vω|. 不失一般性,对任意的k{1,2,…,ω},假设|Vk|=nk,且|V1|≤|V2|≤…≤|Vω|.如果对任意1≤i<j≤ω,都有||Vi|-|Vj||≤1,则G≅Tn,ω. 否则,存在i,j{1,2,…,k}使得||Vi|-|Vj||>1. 不失一般性,假设|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).设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成立,故以下几个结论成立: (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<n2-1,瑞利商定理[17]及上述结论(1)～(4),可得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,∑k=3,4,…,ωnkyk,则从而,再由n1≤n2-2可得y2≥y1.综上,,这与G的定义矛盾.设G是n阶连通图,其团数为ω(G)=ω. 下面分几种情形讨论：(i) ω|n; (ii) ω>n/2; (iii) ω<n/2且(G)>ω(G)=ω. 分别证明qD(G)≥qD(Tn,ω),且等式成立当且仅当引理4(Turn’s Theorem)[7]387 设G是不含ω+1团的n阶连通图,则G的边数e(G)≤e(Tn,ω),且等式成立当且仅当G≅Tn,ω.设G为n阶连通图,G的Wiener指数是指G中所有点对的距离之和,记作σ(G). 易见,).引理5[3]3957 设G是n阶连通图,则q(G)≥4σ(G)/n,且等式成立当且仅当G 是距离正则图.引理6 设G是n阶连通图,其团数为ω(G)=ω,则(i)qD(G)≥4σ(Tn,ω)/n,且等式成立当且仅当G≅Tn,ω.(ii)若ω|n,则qD(G)≥qD(Tn,ω)=2(n+n/ω-2),且等式成立当且仅当G≅Tn,ω.证明易见G有e(G)个点对距离为1,并且有-e(G)个点对距离大于等于2. 若GTn,ω,由引理4可知).再由引理5,得因此(i)成立.若ω|n,则Tn,ω是距离正则的,从而,且). 再由(i)知(ii)成立.设ω、n是正整数且ω<n,定义G(|V1|,|V2|,…,|Vω|)是满足如下条件的n阶图:(1)完全图Kω是它的真子图,其中V(Kω)={v1,v2,…,vω};(2)完全图Kn-ω是它的真子图,其中V(Kn-ω)=V1∪V2∪…∪Vω,这里|V1|≤|V2|≤…≤|Vω|且对任意的k{1,2,…,ω},连接vk与V(Kn-ω)\Vk中的每一个顶点(图2). 显然G(|V1|,|V2|,…,|Vω|)是连通的. 若ω>n/2,则某些Vk可能为空集. 易见G(0,0,…,0,1,1,…,1)≅Tn,ω.令}. 若ω>n/2,可以看到,在n,ω中除了Tn,ω之外,其他图的团数都大于ω. 下面将证明Tn,ω是n,ω中具有最小距离无符号拉普拉斯谱半径的惟一图.引理7 设ω、n为正整数且ω>n/2,Gn,ω,则qD(G)≥qD(Tn,ω),且等式成立当且仅证明不妨设H=G(|V1|,|V2|,…,|Vω|)是集合n,ω 中具有最小距离无符号拉普拉斯谱半径的图. 若HG(0,0,…,0,1,1,…,1),那么必存在某个k{1,2,…,ω}使得|Vk|≥2. 不失一般性,我们假设i是最小的指数使得|Vi|=ni≥2,j是最大的指数使得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,ω.下面证明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,因此另一方面,注意到,,从而由式(1)和式(2),可得由qD(H1)>n,有从而yvi≥yvj,进而qD(H)≥qD(H1).若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是团数ω(G)=ω的n阶连通图. 若ω>n/2,则qD(G)≥qD(Tn,ω),且等式成立当且仅当G≅Tn,ω.证明设U={v1,v2,…,vω}是G的一个团,且记W=V(G)\U. 由于团数ω(G)=ω,从而对于V中的任意顶点来说，其最多有ω-1个邻点在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为正整数且ω≤n,则x1=q-(n+2k-4)q-(n+2k-2)x2.由式(4)和式(6),可得q2-(3n+4k-6)q+(2n2+4k2-10n-12k+4nk+2k2ω+2kω+8)=0.解方程(7),易见式(3)成立.令ω=n,由引理9可得推论3[5]30 qD(Kn)=2n-2.引理10[21] 设G是团数ω(G)≤ω的n阶连通图. 若(G)>ω且,则e(G)≤e(Tn,ω)-⎣.引理11 设G是团数ω(G)=ω的n阶连通图. 若(G)>ω且ω<n/2,则qD(G)≥qD(Tn,ω),且等式成立当且仅当G≅Tn,ω.证明令k=⎣,且GTn,ω. 下面证明qD(G)>qD(Tn,ω).由引理5和引理10,可得.显见e(Tn,ω)=(n2-n-2nk+k2ω+kω)/2,因此有为了证明qD(G)>qD(Tn,ω),由式(3)和式(8),只需证明.化简式(9),接下来证明nk(k+1)(n-ω-2kω)+[(k2ω+kω)-2(k-1)]2+(k-1)(n2+2n+4nk)>0.令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)是正确的,需证注意到ω<n/2,从而k≥2. 由k≥2和k0<ω可知式(12)是正确的.定理1 设G是n阶连通图,其团数为ω(G)=ω,则qD(G)≥qD(Tn,ω),且等式成立当且仅当G≅Tn,ω.证明因为色数(G)≥ω(G)=ω,可以分以下情形来证明.情形1:(G)=ω(G). 此时,由引理3可知结论成立.情形2: (G)>ω(G).子情形2.1: ω=n/2. 此时,由引理6可知结论成立.子情形2.2: ω>n/2. 此时,由引理8可知结论成立.子情形2.3: ω<n/2. 此时,由引理11可知结论成立.结合以上情形的讨论,结论证明完毕.【相关文献】[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.D,HANSEN P. The minimum spectral radius of graphs with a given clique number[J]. Electron Journal of Linear Algebra,2008,17:110-117.[9] LIN H Q,SHU J L,WU Y R,et al. Spectral radius of strongly connected digraphs[J]. Discrete Mathematics,2012,312:3663-3669.[10]GUO J M,LI J X,SHIU W C. The smallest Laplacian spectral radius of graphs with a given clique number[J]. Linear Algebra and Its Applications,2012,437:1109-1122.[11]HE B,JIN Y L,ZHANG X D. Sharp bounds for the signless Laplacian spectral radius in terms of clique number[J]. Linear Algebra and Its Applications,2013,438:3851-3861.[12]ZHANG J M,HUANG T Z,GUO J M. The smallest signless Laplacian spectral radius of graphs with a given clique number[J]. Linear Algebra and ItsApplications,2013,439:2562-2576.[13]HONG W X,YOU L H. Spectral radius and signless Laplacian spectral radius of strongly connected digraphs[J]. Linear Algebra and Its Applications,2014,457:93-113.[14]BONDY J A,MURTY U S R. Graph theory with applications[M]. London:Macmillan,1976.[15]BONDY J A,MURTY U S R. Graph theory[M]. New York:Springer,2008.[16]BERMAN A,ROBERT J P. Nonnegative matrices in the mathematical sciences[M]. New York:Academic Press,1979.[17]HORN R A,JOHNSON C R. Matrix analysis[M]. England:Cambridge University,1986.[18]MINC H. Nonnegative matrices[M]. New York:John Wiley and Sons Inc,1988.[19]JENSEN J B,GUTIN G. Digraphs theory[M]. New York:Springer,2001.[20]BOLLOBS B. Extremal graph theory[M]. New York:Academic Press,1978.[21]KANG M,PIKHURKO O. Maximum Kr+1-free graphs which are not r-partite[J]. Matematychni Studii,2005,24:13.。

给定直径的单圈图的拟拉普拉斯谱半径【摘要】文章研究的是单圈图的拟拉普拉斯的最大特征值（谱半径），刻画了所有阶数为，直径为的单圈图中取得最大谱半径的单圈图是。

【关键词】单圈图直径拟拉谱拉斯谱半径[abstract] this paper vestigates the signless laplacian spectral radius of unicyclic graphs and unicyclic graphs of fixed order and diameter with greatest signless laplacian spectral radius are determined.[keywords] unicyclic graphs；diameter；signless laplacian；spectral radius1.引言及预备知识设是一个阶简单连通无向图，定义g的邻接矩阵为，这里。

矩阵为图g的度对角矩阵，其中表示顶点的度。

矩阵称为g的拉普拉斯矩阵，矩阵称为g的拟拉普拉斯矩阵。

由于是一个实对称方阵，它的特征值均为实数，不妨将其排列为。

称的最大特征值称为图g的拟拉普拉斯谱半径，通常记为。

此外，文中未给出定义的一些概念可以参考文献[6][7]。

图的拟拉普拉斯谱半径的研究是近年来热门的一个课题，在给定一个图的集合，在这个集合中寻找一个谱半径的上界或下界，并刻画达到这个界的图。

即在给定条件下确定具有最大或者最小谱半径的极图。

文献[2][3][5]分别研究了在给定围长、悬挂点个数、度序列的条件下的极图。

本文研究的是在给定直径的条件下，所有单圈图取得最大拟拉普拉斯谱半径的极图。

2.引理及相关定理引理1[3] 设为图g的一条边，在边中间加上一个新的顶点之后所得的图记为，那么有：（1）若不是图g的内部路，且，则，其中是n阶圈。

（2）若是图g的内部路，且，则，其中这里是阶路的首尾两个顶点各添加两条悬挂边而得到的图。

Vol. 55 No. 3Jun. 20 21第55卷第3期20 21年6月华中师范大学学报(自然科学版)JOURNAL OF CENTRAL CHINA NORMAL UNIVERSITY (Nat Si )DOI ：1 0 )96 0 3/j. cnki. 1 00 0-119 0 . 2 021. )3. )03 文章编号：1 000-1190(2 021)03-0347-04关于图的距离无符号拉普拉斯谱半径的下界朱银芬1,王国平2**,陈星*收稿日期:2020-03-05.基金项目：国家自然科学基金项目(11461071)；新疆维吾尔自治区自然科学基金项目(2021D01A65)；新疆维吾尔自治区第三期天山英才项目；新疆工程学院科研育人项目(2019xgy702112).* 通信联系人.E-mail ： xj. wgp @163. com.(1.新疆工程学院数理学院，乌鲁木齐830029； 2.新疆师范大学数学科学学院，乌鲁木齐8300170摘 要：若一个连通图G 的点集是V(G ) * {s,s,/,s+,那么图G 的距离矩阵D(G ) * (d,,0,其中d ”表示点s 与s 之间的距离.令O g L 0表示点l 到图G 中其他所有点的距离之和，O(G )表 示 < 行 < 列位置的元素Tr G (v,0的对角矩阵.图G 的距离无符号拉普拉斯矩阵Q ”(G ) * O(G ) +D 〈G ). Q ” (G )的最大特征值*q (G )是图G 的距离无符号拉普拉斯谱半径.该文确定了给定匹配数 的％个点的图的距离无符号径的下界.关键词：距离无符号拉普拉斯矩阵；谱半径；匹配数中图分类号：O157.5 文献标志码：A 开放科学(资源服务)标志码(OSID )：如果一个连通图G 的点集是V(G ) = L 1 ,2,那么图G 的距离矩阵D (G ) = (d ”)，其中d ”表示点L ,与L ”之间的距离.令O g L )表示点 L 到图G 中其点的距离之和，O(G )表示对角线位置的元素是Tr ；L )的对角矩阵.G 的距矩阵及距号拉普拉斯矩阵分别被表示为Q d (G ) = Tr(G)—D(G )与Q ”(G ) = O(G )+D(G ),它们的最大特征值*Q (G ) M *q (G )分别是图G 的距径与距 号 径.Aouchiche 和Hansen 在文献中引入了图的距与距号 的念,并 文献[2)中证明了树中 具 小距径.近年来,关于距离拉与距号的研究已经有了长足的进展.Xing 与Zhou 旧 了双圈图中具有最小距径与 小距 号径的一图.文献确定了在树、单圈图、双圈图、给定悬挂点数与连通度的图中具 小距号拉径的图.Liu 与Lu ()确定了 团数的 距号 径 的 Lin 和Zhou ()刻画了 悬挂点数与边连通度的图中具 小的距 径的 一 的特牛爱红等⑺确定了 数或给定连通度的二部图中具小距 径的极图.本文确定了给定匹配数的图的距离无符号拉径的下1引理先给岀一些已知的结果.引理1(1)图G 是连通图，若L > 1(G ),那么*q(G + uv ) <*q (G ).引理2(1) 设图G 是％阶连通图,那么*q (G )(*Q (K ”)= 2(% —1).设图G 是”个点的完全图将其记作K %,其补 图记作K ；;若G 1与G 是点不相交的两个图，用G 1V G 表示将G 1中的每一个点连接G 中的每一个点所得到的引理 3[z ] *Q (K > V K %_”) = 2n — m .引理4() 设人 与R 是％阶实对称矩,那么*% (R 2) + * (R 1) * * (R 1 + A 2 ),其中*,(R )是A 的第”大特征值.引理5() 设A 是％阶实对称矩阵,M 是A 的s (s <%)阶主子阵.那么*,+%—s (A ) **”)) **,(A )(1 *”*s ),其中* (A )是A 的第i 大特征值.若有X 7 V(G ),那么图G 的子图G —X 是将图；的乂中的点与X 点相关联的边同时册 到的 G 的一个 是 G 中 相 的边的合,那么所有匹配中含有最大的边数 G 的匹48华中师范大学学报(自然科学版)第55卷配数.若图G的某个连通分支的点数是奇数，那么称这个连通分支是图G的奇连通分支；否则，称这个连通分支是偶连通分支.引理6(-10]如果图；是匹配数为>的”阶，那么%—2>=max*(;—X)—丨X丨：X U3(&)},其中s(G—X)是图G—X的奇连通分支数.引理7(11)如果图G是连通图，那么*q(G) >*Q(G).2定理及推论如果图G]和同构，记之为G1二将匹配数为m的％阶连通简单图的集合记作G m.下面给出本文的主要结果•定理1设图g+g>，那么i)若m=L2」，则*q(G)(2(%—1),等式成立当且仅当G@K%.ii)若1*m*L2」一1,则*q(G)>2%—m.证明i)设m=L21由引理2得*q G)( *p(K%)=2(%—1).若 G@K%,则由引理1知*p(G)*q(,K n)•ii)设1*m*L2」一1由引理6,存在某个X。

图的拉普斯系数和无号拉普拉斯谱半径图的拉普斯系数和无号拉普拉斯谱半径图论作为离散数学的一个分支，研究的是图以及其性质与特性。

在图论中，有两个重要的概念，分别是图的拉普斯系数和无号拉普拉斯谱半径。

首先，我们先介绍一下图的拉普斯系数（Laplacian coefficients）。

对于一个无向图G，如果它存在n个顶点和m条边，那么它的拉普斯矩阵L是一个n×n的矩阵，定义如下：L = D - A其中，D是一个对角矩阵，其对角线上的元素是每个顶点的度数（即与该顶点相连的边的条数），A是邻接矩阵，表示图中的边的连接关系。

图的拉普斯系数与图的连通性密切相关。

一个图的拉普斯系数可以帮助我们了解图的连通性，分析图中的节点间的相互关系。

这在社交网络分析、电力网络分析等领域有着重要的应用。

接下来，我们来介绍一下无号拉普拉斯谱半径（unsigned Laplacian spectral radius）。

对于图G的拉普拉斯矩阵L，它的特征值可以排列为0=λ0 ≤ λ1 ≤ ⋯ ≤ λn-1。

无号拉普拉斯谱半径的定义如下：rL = max{ |λi| }其中，|λi|表示特征值λi的绝对值，rL表示特征值的最大绝对值。

这个值通常用来衡量图的稳定性。

无号拉普拉斯谱半径与图的几何性质有密切关系。

无号拉普拉斯谱半径较小的图往往具有良好的耐受性和鲁棒性，它们对于随机扰动和攻击有很好的抵抗能力。

因此，在通信网络、生物网络等领域中，无号拉普拉斯谱半径的研究有着重要的意义。

总结起来，图的拉普斯系数和无号拉普拉斯谱半径提供了图论领域中对于图的连通性和稳定性的分析工具。

通过研究它们的数学特性和几何特性，可以帮助我们更好地理解和分析图的结构和性质。

在实际应用中，它们被广泛运用于社交网络分析、电力网络分析等领域，对于设计和优化网络结构、提高网络的稳定性具有重要的意义。

然而，尽管图的拉普斯系数和无号拉普拉斯谱半径在图论领域有着重要的地位，但它们的深入研究还有很大的空间。

谱半径平均度证明要证明一个有向图的谱半径与平均度存在关系，需要从图论和线性代数两个方面进行证明。

1. 图论证明：设有向图G的邻接矩阵为A，G中共有n个顶点。

邻接矩阵的元素a[i][j]表示顶点i到顶点j的有向边的权重，如果没有边连接i和j，则a[i][j]=0。

图G的度矩阵D是一个对角矩阵，其对角线元素d[i][i]表示顶点i的度数。

那么，G的拉普拉斯矩阵L=D-A。

根据图论中拉普拉斯矩阵的性质，拉普拉斯矩阵具有以下两个性质：（1）拉普拉斯矩阵是一个实对称矩阵。

（2）拉普拉斯矩阵的最小特征值为0，其对应的特征向量为1的倍数。

由于G是有向图，拉普拉斯矩阵不一定是对称矩阵，但是可以通过构造一个新的矩阵H，使得H=QT LQ是一个对称矩阵，其中Q是一个辅助矩阵。

所以我们考虑证明H的最小特征值为0。

由于L=D-A，所以有DL=L+DL。

考虑H的一个特征向量x，对应特征值为λ。

则有：Hx=(QT LQ)x=QT(DL-A)Qx = QTDLQ-QTAQx = λx即：DLQx-λQx - QTAQx = 0令y=Qx，则上述等式可变形为：DLy-λy-QTAy = 0左右乘以QT：QTLQTDLy-λQTLQy - QTLQTAy = 0由于QTLQ是对称矩阵，所以有：QTLQTDLy-λQTLQy - QTLQTAy = 0即：D(Ly)-λ(Ly)-AT(Ly) = 0所以我们可以得到，y是拉普拉斯矩阵DL−λI−AT的特征向量。

由于图G的谱半径是拉普拉斯矩阵的最大特征值，我们可以得到λ的范围为0 ≤ λ ≤ Δ(G)，其中Δ(G)表示G的最大度数。

2. 线性代数证明：由于拉普拉斯矩阵L是实对称矩阵，所以它的特征值一定是实数。

我们知道，对于一个对称矩阵，存在n个正交归一的特征向量，它们对应的特征值构成一个实数集合。

设G的特征值为λ1,λ2,...,λn，则谱半径ρ(G)=max{|λ1|,|λ2|,...,|λn|}。

三类图的拉普拉斯谱半径的极限点李静花;何常香【摘要】The Laplacian characteristic polynomials of the structures of graphs combined with corresponding Laplace matrices were studied. The limit points of the Laplacian spectral radii were provided according to the properties of Laplacian characteristic polynomials. For three types of graphs, the existence of limit points of the Laplacian spectral radii was proved and it was determined when n→∞,the Laplacian spectral radius of a graph is the largest root of certain equation by using some Laplacian characteristic polynomials of the graphs after coalescent operations and considering the upper and lower bounds of Laplacian spectral radii of the graphs.%将图的结构与对应的拉普拉斯矩阵相结合,研究其拉普拉斯特征多项式.根据拉普拉斯特征多项式的特征求出了图的拉普拉斯谱半径的极限点.利用图经粘连运算后的拉普拉斯特征多项式以及图的拉普拉斯谱半径的上界和下界,证明了三类图的拉普拉斯谱半径的极限点的存在性,证明了n→∞时图类的拉普拉斯谱半径是某方程的最大根.【期刊名称】《上海理工大学学报》【年(卷),期】2018(040)002【总页数】6页(P121-126)【关键词】拉普拉斯谱半径;极限点;粘连【作者】李静花;何常香【作者单位】上海理工大学理学院,上海 200093;上海理工大学理学院,上海200093【正文语种】中文【中图分类】O157.51 问题的提出设为阶简单连通图，其中，是图的点集合，是图的边集合。

含割边的连通图最小距离无符号拉普拉斯谱半径查淑萍;李路遥;高芳【摘要】Among all the connected graphs on n vertices with cut edges, the unique graph with minimum distance signless Laplacian spectral radius is characterized by using the relations of eigenvalue and eigenvector. On this basis, a lower bound of the distance signless Laplacian spectral radius of connected graphs on vertices with cut edges is determined.%在所有含割边的n阶连通图中，利用特征值与特征向量的关系，刻画了具有最小距离无符号拉普拉斯谱半径的图的结构，在此基础上，给出了含割边的n阶连通图的距离无符号拉普拉斯谱半径的一个下界。

【期刊名称】《池州学院学报》【年(卷),期】2016(030)003【总页数】3页(P23-25)【关键词】图;割边;距离无符号拉普拉斯矩阵;谱半径【作者】查淑萍;李路遥;高芳【作者单位】池州学院数学与计算机学院，安徽池州 247000;池州学院数学与计算机学院，安徽池州 247000;池州学院数学与计算机学院，安徽池州 247000【正文语种】中文【中图分类】O157本文中，我们只考虑简单的连通图G=（V（G），E（G），这里V（G）表示图G的顶点集，E（G）表示图G的边集，其中||V（G）称为图G的阶数。

图G的距离矩阵，记作D（G），定义为D（G）=（duv）u，v∈V（G），其中duv表示顶点u和v之间的距离（即G中连接u和v的最短路的长度）。

其广泛应用涉及很多领域，如通讯网络的设计［1］，图的嵌入理论［2-4］以及分子稳定性［5-6］等。

同济大学理学院硕士学位论文图的拉普拉斯谱半径的讨论姓名：***申请学位级别：硕士专业：应用数学指导教师：***20070501图的拉普拉斯谱半径的讨论作者：方敏学位授予单位：同济大学理学院1.何常香代数图论和Ramsey理论中若干问题的研究[学位论文]20062.王兴科某些图的谱半径与代数连通度[学位论文]20093.王平代数图论中的两个问题--Cayley图和紧图[学位论文]20004.袁西英图的特征值[学位论文]20075.张丽图的拉普拉斯谱的一些极值和排序问题[学位论文]20076.郭继明图的拉普拉斯特征值[学位论文]20067.吴翠芳关于图的谱和拉普拉斯谱[学位论文]20058.潘永亮图的Laplace谱[学位论文]20019.丁尚文图的最大和次小拉普拉斯特征值[学位论文]200810.史伟图的拉普拉斯特征值与全控制参数[学位论文]2007引用本文格式：方敏图的拉普拉斯谱半径的讨论[学位论文]硕士 2007华中科技大学硕士学位论文“假”的生产及其逻辑——对“华南虎事件”的分析姓名：张斌申请学位级别：硕士专业：社会学指导教师：吴毅20080603摘要“华南虎事件”是2007年公众关注的焦点，本研究起始于这样一个疑问：“华南虎事件”中陕西省有关方面为何要造假？本研究以故事的形式将事件较为完整地呈现出来，通过对事件的参与者陕西省林业厅、地方政府、评审专家、周正龙、官僚系统、网络、傅德志、新闻媒体、国家林业局等在事件中的表现的描述，揭示了他们背后的结构性力量，并由此逐渐呈现出了整个事件的逻辑。

本研究最终将这一逻辑用“体制性造假”来概括。

体制性造假是受到体制逼迫的产物，是地方政府在面临体制的困境时不得不为的选择，而为了达到体制性造假的目的，地方政府又充分利用其所掌握的体制资源和力量来造假，“华南虎事件”讲述的也就是地方政府在体制困境之下如何“趋利避害”的故事。

体制性造假受到网络、媒体、公众等的制约，造假将使政府公信力受损，但造假又不得不为，因此地方政府凭借体制对专家的控制来造假。

[转]图像处理中的拉普拉斯算⼦原⽂地址为：5.5.2 拉普拉斯掩模锐化（1）1．基本理论拉普拉斯算⼦是最简单的各向同性微分算⼦，具有旋转不变性。

⼀个⼆维图像函数 的拉普拉斯变换是各向同性的⼆阶导数，定义为：（5-11）为了更适合于数字，将该⽅程表⽰为离散形式：（5-12）另外，拉普拉斯算⼦还可以表⽰成模板的形式，如图5-9所⽰。

图5-9（a）表⽰离散拉普拉斯算⼦的模板，图5-9（b）表⽰其扩展模板，图5-9（c）则分别表⽰其他两种拉普拉斯的实现模板。

从模板形式容易看出，如果在图像中⼀个较暗的区域中出现了⼀个亮点，那么⽤拉普拉斯运算就会使这个亮点变得更亮。

因为图像中的边缘就是那些灰度发⽣跳变的区域，所以拉普拉斯锐化模板在边缘检测中很有⽤。

⼀般增强技术对于陡峭的边缘和缓慢变化的边缘很难确定其边缘线的位置。

但此算⼦却可⽤⼆次微分正峰和负峰之间的过零点来确定，对孤⽴点或端点更为敏感，因此特别适⽤于以突出图像中的孤⽴点、孤⽴线或线端点为⽬的的场合。

同梯度算⼦⼀样，拉普拉斯算⼦也会增强图像中的噪声，有时⽤拉普拉斯算⼦进⾏边缘检测时，可将图像先进⾏平滑处理。

图5-9 拉普拉斯的4种模板图像锐化处理的作⽤是使灰度反差增强，从⽽使模糊图像变得更加清晰。

图像模糊的实质就是图像受到平均运算或积分运算，因此可以对图像进⾏逆运算，如微分运算能够突出图像细节，使图像变得更为清晰。

由于拉普拉斯是⼀种微分算⼦，它的应⽤可增强图像中灰度突变的区域，减弱灰度的缓慢变化区域。

因此，锐化处理可选择拉普拉斯算⼦对原图像进⾏处理，产⽣描述灰度突变的图像，再将拉普拉斯图像与原始图像叠加⽽产⽣锐化图像。

拉普拉斯锐化的基本⽅法可以由下式表⽰：这种简单的锐化⽅法既可以产⽣拉普拉斯锐化处理的效果，同时⼜能保留背景信息，将原始图像叠加到拉普拉斯变换的处理结果中去，可以使图像中的各灰度值得到保留，使灰度突变处的对⽐度得到增强，最终结果是在保留图像背景的前提下，突现出图像中⼩的细节信息。

一类特殊图的最小特征值孙威;余桂东;芦兴庭;王振东【摘要】图的邻接矩阵是表示顶点之间相邻关系的矩阵,它的最小特征值被定义为图的最小特征值,图的最小特征值是解析图的结构性质的重要概念。

本文讨论了一类特殊图类的最小特征值,并刻画了此类图最小特征值达极小的唯一图。

【期刊名称】《安庆师范大学学报：自然科学版》【年(卷),期】2017(023)003【总页数】3页(P32-34)【关键词】图;补图;邻接矩阵;最小特征值【作者】孙威;余桂东;芦兴庭;王振东【作者单位】安庆师范大学数学与计算科学学院,安徽安庆246133【正文语种】中文【中图分类】O157.5设G=(V,E)是一个顶点集为V={v 1,v2,…,vn}和边集为E={e1,e2,∙∙∙e n}的n阶简单图,顶点v∈V的邻域定义为NG(v)={u :uv∈E},顶点v∈V的度定义为 d(v)= | NG(v) |。

若∀v∈G ，d(v)=n-1，则称 G为完全图,记为 Kn。

记Gc=(V,Ec)为图G=(V,E)的补图,其中Ec={x y:x,y∈V,x≠y,xy∉E} 。

图G的度对角矩阵为D(G)=diag(d(v1),d(v2),…,d(vn)),其中 d(vi)是顶点vi的度数,i=1,2,…,n。

图G的邻接矩阵记为A(G)=(aij)n×n,如果vivj∈E,则 aij=1;否则aij=0.图G的无符号拉普拉斯矩阵记为Q(G)=D(G)+A(G)。

图G的拉普拉斯矩阵记为L(G)=D(G)-A(G)。

因为A(G),Q(G),L(G)是实对称矩阵，因此它们的特征值是实数,故可排序。

这里不妨设 A(G)的n个特征值从小到大排列为λ1(G)≤λ2(G)≤…≤λn(G)。

A(G)的特征值被称为图G的特征值。

A(G)的最大特征值λn(G)称为图G的谱半径,记作λ(G)。

A(G)的最小特征值λ1(G)称为图G的最小特征值,记作λmin(G),其对应的特征向量称作G的第一特征向量。

距离拉普拉斯光谱半径的下限在n个顶点图中的匹配数字Fenglei Tian, Dein Wong ,1, Xiaobin MaDepartment of Mathematics, China University of Mining and Technology,Xuzhou 221116, PR China摘要：最近，Niu等人（2015）[10]在具有给定匹配数的n个顶点二分图之间确定了具有最小距离拉普拉斯光谱半径的极值图。

然而，一个更自然的问题是开放的：在具有给定匹配数m的所有n顶点图中，它们的距离拉普拉斯光谱半径的下限如何以及哪些图最小化距离拉普拉斯光谱半径？在这篇文章中，我们完全解决了这个问题。

通过将每个孤立顶点连接到Km的所有顶点的m（n-m）个边加入，通过Km ，Kn-m表示从完整图Km和n-m个孤立顶点获得的图。

令G为阶数n和匹配数m的连通图，ρL（G）为G的距离拉普拉斯光谱半径。

在本文中，我们证明如果m = n2，则ρL（G）≥n，具有相等的只有当G = Kn;如果1≤m≤n2-1，则ρL（G）≥2n-m，当且仅当GΓ相等时，其中Γ表示由Km Kn-m组成的n个顶点图以及从Km Kn-m获得的所有可能的图形，通过删除Km的一些边缘。

关键词：距离拉普拉斯矩阵光谱半径；匹配号码。

文章历史：收到2016年3月2日；接受2016年6月15日；在线提供2016年6月23日由R. Brualdi提交。

1、介绍对于任意图G来说，通过图G所对应矩阵的特征多项式直接计算图的特征值，由于矩阵阶数较高，几乎是不能实现的.人们只对很少一部分的图，例如:完全图，完全二部图，完全多部图的特征值直接计算可以得到。

人们已经给出了图的各种运算，例如:联，直积和字典序积，冠图，边冠图，邻接冠图，收缩点(边)邻接冠图，基于R一运算的R一点冠图和R一边冠图等图相应的谱，建立起图运算后的”大图”和”原图”之间的特征多项式和特征值之间的关系，能够用顶点个数较少的图的特征值计算出顶点个数较多的图的特征值。