第二类型双圈图的距离矩阵论文

图论中邻接矩阵的应用作者：刘亚国， LIU Ya-guo作者单位：河源职业技术学院,广东,河源,517000刊名：忻州师范学院学报英文刊名：JOURNAL OF XINZHOU TEACHERS UNIVERSITY年，卷(期)：2008，24(2)被引用次数：0次1.阮哓青.周义仓数学建模引论 20052.胡运权运筹学教程 19983.王朝瑞图论 19851.期刊论文何梅芝.HE Mei-zhi双圈图的邻接矩阵的奇异性-湖南城市学院学报（自然科学版）2006,15(3)连通的双圈图(即边数比顶点数多一个的连通简单图)恰有3种类型,其中2种类型的图的邻接矩阵的奇异性问题业已解决.现给出第三种类型的双圈图的邻接矩阵是奇异的充要条件.2.学位论文亓静双圈图的邻接谱半径2006在图论中，为了研究图的性质，人们引进了各种各样的矩阵，诸如图的邻接矩阵，关联矩阵，距离矩阵，拉普拉斯矩阵等等，这些矩阵与图都有着自然的联系，代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质反映出来，这里所指的矩阵的代数性质，主要指矩阵的特征值。

在上面所提到的矩阵中，最重要的有两个：图的拉普拉斯矩阵和邻接矩阵图的拉普拉斯矩阵的特征值和邻接矩阵的特征值都是图的在同构下的不变量，而图的邻接矩阵及其特征值是代数图论的一个基本的被广泛研究的课题．在过去的几十年中，人们对图的邻接矩阵的特征值已经进行了大量的研究。

本文的研究主要是对双圈图的邻接谱半径的研究．何常香等人通过对双圈图进行收缩、夺邻、嫁接等运算，找出了双圈图中邻接谱半径前三大的图，并给出了它们的邻接谱半径。

本文考虑点数n≥12的双圈图，推广了上述结论，找出了双圈图中前五大邻接谱半径，并给出了相应的双圈图。

图的邻接谱半径是指图的邻接矩阵的最大特征值，在本文的第二章中利用广义夺邻定理以及嫁接运算，收缩内部路中边等技巧，研究了阶数为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.。

树、单圈图和双圈图改进的第二Zagreb指标秦忠芳;袁利;赵飚【摘要】文章采用了类似Ji s等(2014)的方法,研究了树、单圈图、双圈图的改进的第二Zagreb指标,通过四个图变换(其中图变换1,2是严格增该指标的变换,图变换3,4是严格减该指标的变换)严格论证,分别得出了树、单圈图、双圈图的极大极小值.%In this paper,we will use the similar way (Ji S,2014)to study the trees,unicyclic and bicyclic graphs with the second reformulated Zagreb indices,we strictly demonstrate by four graph operations (graph operation 1,2 which strictly increase this index and graph operation 3,4 which strictly decrease this index ),then we determine the maximum and minimum indices for the second reformulated Zagreb indices of trees,unicyclic and bicyclic graphs,respectively.【期刊名称】《曲阜师范大学学报（自然科学版）》【年(卷),期】2017(043)004【总页数】6页(P15-20)【关键词】改进的第二Zagreb指标;树;单圈图;双圈图;图变换【作者】秦忠芳;袁利;赵飚【作者单位】新疆大学数学与系统科学学院,830046,新疆维吾尔自治区乌鲁木齐市;新疆大学数学与系统科学学院,830046,新疆维吾尔自治区乌鲁木齐市;新疆大学数学与系统科学学院,830046,新疆维吾尔自治区乌鲁木齐市【正文语种】中文【中图分类】O157.5Zagreb indices is one of the most important topological indices, as a pair of molecular descriptors, introduced in [4,5] and they found significant applications in chemistry, such as QSPR and QSAR studies [1,7,5], the recent Zagreb indices results refer to [8-12].Let G=(V,E) be a simple connected graph with vertex set V and edge set E. The first and second Zagreb index of G is defined aswhere d(u) is the degree of vertex u in G.Milievi et al. in 2004 reformulated the Zagreb indices in terms of edge-degrees instead of vertex-degrees aswhere d(e) denotes the degree of the edge e in G, which is defined byd(e)=d(u)+d(v)-2 with e=uv, and e～f means the edges e and f are adjacent. Recently, the upper and lower bounds on EM1(G) and EM2(G) were presented in [2,13,14].In this paper, we characterize the extremal properties of the second reformulated Zagreb indices. In section 2, we present some graph operations which strictly increase or decrease the second reformulated Zagreb indices. In section 3, we determine the maximum and minimum for the second reformulated Zagreb indices of trees, unicyclic and bicyclic graphs, respectively.In order to easily exhibit our results, we introduce some graph-theoretical notations. Let G=(V,E) be a simple graph.For v∈V and e∈E, let N(v) be theset of all neighbors of v in G. G-v be a subgraph of G by deleting vertex v, and G-e be a subgraph of G by deleting edge e, let G0 be a nontrivial graph, let u·v denot the fusing two vertices u and v of G.First, we introduce two graph operations which strictly increase the second reformulated Zagreb index.Operation 2.1 Let G0 be a nontrivial simple graph, u and v its vertices with dG0(u)=x,dG0(v)=y, Pl=v1(u)v2… vl(v) is a nontrivial l-1-length path V(G0)∩ V(Pl)={u=v1,v=vl}, let G=G0∩ Pl, G′=G-{v1v2,v2v3,…,vl-1vl}+{w=(u·v)v1,wv2,…,wvl} as shown in figure 1.Lemma 2.1 If G′ is obtained from G by operation 2.1 as shown in fig. 1, thenProof As shown in fig.1, dG0(u)=x and dG0(v)=y, while w is a new vertex by fusing u and v with dG′=x+y+l-1 with l≥ 2. If l=2, by the definition of EM2, the number of 2-length path by w vertex over u, v vertices of the sum of the number of 2-length path, anddG′(w)=x+y+1,dG′(w)>dG0(u),dG′(w)>dG0(v), so EM2(G′)>EM2(G). We now consider the case l≥3, according to the definition of EM2, we have∑dG(vivi+1)dG(vi+1vi+2) =(x+y+l-2)2-2x-2y-4(l-4)>0.(vs≠ vt,vsand vt∈{v1,v2,…,vl-1})(The interested reader can use mathematical induction to prove).Therefore, the proof is complete.Remark 2.1 Repeating the Operation 2.1 case of l=2 and l≥3, any tree can changed into a star, any unicyclic and bicyclic graph can be respectively changed into triangle and double triangle such that other edges becomependent edge.Remark 2.2 As shown in fig.2, let uv be an edge of connected graph G with dG(v)≥2, suppose that {v,w1,w2,…,wt} are all the neighbors of vertex u while w1,w2,…,wt are pendent vertices, we only make the operation 1 useful for uv edge, then we get G′,G′=G-{uw1,uw2,…,uwt}+{vw1,vw2,…,vwt}, by lemma 2.1, we can easily get the following resultsOperation 2.2 Let G0 be a nontrivial connected graph and u and v are a pair of equivalent in G0 with dG0(u)=dG0(v)=x. Let G be the graph obtained by attaching Sk+1,Sl+1 at the vertices u and v of G0 with k≥ l, respectively. G′=G-{vv1,vv2,… vvl}+{uv1,uv2,… uvl},as shown in fig.3 Lemma 2.2 If G′ is obtained from G by operation 2.2, as shown in fig.3, thenProof With dG0(u)=dG0(v)=x>0 and k≥ l≥1, by the d efinition of EM2, we haveEM2(G′)- EM2(G)>dG′(wiu)dG′(uwj)-dG(uiu)dG(uuj)-dG(viv)dG(vvj)=(x+k+l-1)2-(x+k-1)2-(x+l-1)2>(x+2k-1)2-2(x+k-1)2>0.(wi≠ wj, wi, wj∈{u1,…,uk,v1,…,vl}, ui≠ uj, ui, uj∈{u1,…,uk},vi≠ vj,vi,vj∈{v1,…,vl}) Hence, the result holds.Operation 2.3 Let G0 be a nontrivial connected graph and v is a given vertex in G0 with dG0(v)=x, let G be a graph obtained from G0 by attaching at v two paths P:vu1u2… uk of length k and Q:vw1w2… wl of length l. G′=G-vw1+ukw1, as shown in fig.4.Lemma 2.3 I f G′ is obtained from G by operation 2.3, as shown in fig.4,thenProof By the definition of EM2, we haveEM2(G)- EM2(G′)>dG(u1v)dG(vw1)+dG(vw1)dG(w1w2)+dG(vu1)dG(u1u2)+ dG(uk-2uk-1)dG(uk-1uk)-dG′(vu1)dG′(u1u2)-dG′(uk-2uk-1)dG′(uk-1uk)-dG′(uk-1uk)dG′(ukw1)=(x+2)2+4(x+2)+2-2(x+1)-8=(x+3)2-3>0.Hence, the result holds.Operation 2.4 Let G0 be a nontrivial simple graph, Pt=u1u2… ut is a nontrivial t-1-length path V(G0)∩ V(Pt)={ul}, let G=G0∩ Pt, x and y be two neighbors of u1 different from in Pt, if G′=G-(Pt-u1)+u1u2+u2u3+… uty as shown in fig.5.Lemma 2.4 If G′ is obtained from G by operation 2.4, as shown in fig.5, thenProof Suppose dG(x)=x,dG(y)=y, by the definition of EM2, we haveEM2(G)- EM2(G′)>dG(xu1)dG(u1y)+dG(xu1)dG(u1u2)+dG(yu1)dG(u1u2)+ dG(ut-2ut-1)dG(ut-1ut)>-dG′(xu1)dG′(u1u2)-dG′(u1u2)dG′(u2u3)-dG′(ut-1ut)dG′(uty)-dG′(ut-2ut-1)dG′(ut-1ut)=(x+1)(y+1)+x+y>0.Hence, the result holds.First, we define some notations which will be using in the following theorem description.Let Pn,Cn and Sn be the path, the cycle and the star with order n,respectively. Let Pnk,l,m be the graph obtained by connectingtwo cycles Ck and Cm with a path Pl with k+l+m-2=n. Cn(p,q) be the graph just contains two cycles Cp and Cq having a common vertex withp+q-1=n. Cn(r,l,t) be the graph which the cycles Cr and Cl have a common path of length t with r+l-t=n.Theorem 3.1 Let G be a acyclic connected graph with n(n≥ 5) vertices. Then we havethe lower bound attains on G≅ Pn and the upper bound is attains on G≅Sn.Proof Since G is a acyclic graph with n vertices, assuming that EM2(G) is the largest, if G isn't a star, there is a path Pl and l≥3, we select any two vertices on the path Pl to execute operation 2.1, then we get a new acyclic graph G′, by lemma 2.1 we know the EM2(G′)>EM2(G), so we obtain a contradiction since EM2(G) is the largest, then we get the uniquely maximum acyclic graph Sn with respect to EM2.Meanwhile, assuming that EM2(G) is the smallest, if G isn't a path, there is a vertex v and dG(v)=k≥3, G-v has k br anches, namely {G1,G2,…,Gk}. Let m=max{|G1|,|G2|,…,|Gk|}=|Gk|, the v vertex ensures maximum value of m, then all {G1,G2,…,Gk-1} are the path, otherwise, we can find a vertex v' anddG(v')=l≥3 in {G1,G2,…,Gk-1}, G-v' has l branches {H1,H2,…,Hl}, letn=max{|H1|,|H2|,…,|Hl|}, is there n≥ m, we obtain a contradiction since v make m maximum, so we can perform operation 2.3 on the v vertex, we can get a new acyclic graph G′, by lemma 2.3, EM2(G′)<EM2(G), that's contradictory. then we get the uniquely minimum acyclic graph Pn with respect to EM2.Theorem 3.2 Let G be a unicyclic graph with n(n≥ 5) vertices. Then we have the lower bound attains on G≅ Cn and the upper bound is attains on G≅ . Proof Since G is a unicyclic graph with n vertices, G contains a uniquely cycle Cl, first, by lemma 2.1, it can turn the pendent trees on the G into the pendent edges and it's EM2 is increased strictly, second, by lemma 2.2, all pendent edges can be moved to one vertex and it's EM2 is also increased strictly, third, by lemma 2.1, it can turn the cycle Cl into the 3-length cycle and the other edges become pendent edges in one vertex of the 3-length cycle. So we get the uniquely maximum graph (see, fig.6)with respect to EM2. Meanwhile, by lemma 2.3, it can turn the pendent trees on the pendent path and it's EM2 is decreased strictly, then by lemma 2.4, the pendent path can into Cl and make it longer, the EM2 is also decreased strictly, repeat these processes, we deduce the minimum graph is Cn.In this paper, the four operations and remark 2.2 are equivalent to the five operations in the literature[3], by theorem 3.1, theorem 3.2 and the similar approach to the literature[3], we can get the following theorem, since the proof is the similar to the literature[3], we no longer write.(The interested reader can view the literature[3]).Theorem 3.3 Let G be a bicyclic graph with n(n≥ 5) vertices. Then we have the lower bound attains on G∈{Pnk,l,m:l≥3}∪{Cn(r,l,t):t≥3} and the upper bound is attains on G≅ .By simply caculation, we have that EM2(Cn(p,q))=4n+108,EM2(Pnk,l,m)=4n+58 if l=2, EM2(Pnk,l,m)=4n+54, otherwise;EM2(Cn(r,l,t))=4n+58 if t=2, EM2(Cn(r,l,t))=4n+54, otherwise.[1] Milievi A, Nikoli S, Trinajsti N. On reformlated Zagreb indices[J].Mol. Divers, 2004,8:393-399.[2] Ili A, Zhou B. On reformlated Zagreb indices[J]. Discr Appl Math, 2012,160:204-209.[3] Ji S, Li X, Huo B. On reformulated Zagreb Indices with respect to acyclic, unicyclic and bicyclic graphs[J]. MATCH Commun Math Comput Chem, 2014, 72:723-732.[4] Gutman I, Trinajs ti N. Graph Theory and Molecular Orbitals Total π-electron Energy of Alternant Hydrocarbons[J]. Chem Phys Lett, 1972, 17:535-538.[5] Todeschini R, Consonni V. Handbook of MolecularDescriptors[M],Wiley-VCH, Weinheim. 2000.[6] Ballaban A T. From Chemistory Topology to Three-Geometry[M].Plenum Press, New York, 1997.[7] Devillers J, Balaban A T. Topologicl Indicies and Related Desriptors in QSAR QSPR[M]. Gordon Breach, Amsterdam. 1999.[8] Das K C, Xu K, Gutma I. On Zagreb and Harary indices[J].MATCH Commun Math Comput Chem, 2013, 70:301-314.[9] Da Fonseca C M, Stevanovi D. Further properties of the second Zagreb idex[J]. MATCH Commun Math Comput Chem, 2014, 72:655-668.[10] Gutman I, Furtula B, Elphick C. Three New/Old Vertex-Degree-based Topological Indices[J]. MATCH Commun Math Comput Chem, 2014,72:617-632.[11] Xu K, Das K C, Balachandran S. Maximizing the Zagreb indices of(n,m)-graphs[J].MATCH Commun Math Comput Chem, 2014, 72:641-654.[12] Zhong L, Xu K. Inequalities between vertex-edge-based topoligical indices[J].MATCH Commun Math Comput Chem, 2014, 71:627-642. [13] Zhou B, Trinajsti N. Some properties of the reformulated Zagreb indices[J]. Math Chem, 2010, 48:714-719.[14] De N. Some bounds of reformlated Zagreb indices[J].Appl Math Sci, 2012, 6:5005-5012.。

双圈图的Wiener极性指数胡云云;欧见平【摘要】连通图G的Wiener极性指数是它的距离等于3的点对数,通过引入图变换,本文确定了双圈图的极小Wiener极性指数,并刻画了极图.两个圈点不交的双圈极图也得到了刻画.【期刊名称】《五邑大学学报（自然科学版）》【年(卷),期】2017(031)003【总页数】6页(P8-12,19)【关键词】双圈图;Wiener极性指数;Wiener指数【作者】胡云云;欧见平【作者单位】五邑大学数学与计算科学学院,广东江门 529020;五邑大学数学与计算科学学院,广东江门 529020【正文语种】中文【中图分类】O157.5本文所考虑的图都是简单连通图. 图的两个顶点和之间的距离记为或者，它表示连接这两点的最短路的长度. 图的Wiener极性指数定义为它的距离等于3的无序点对的数目[1]. 图的Wiener极性指数表示为：1998年，Lukovits和Linert[2]应用Wiener极性指数定量论证了许多含圈和不含圈的碳氢化合物的结构性质关系. Hosoya发现了Wiener极性指数的一个物理化学解释[3]. 文献[4]得到了Wiener极性指数和Zagreb指数之间的关系，同时确定了前两个具有最小的Wiener极性指数的单圈图，文献[5]确定了树的最小和最大Wiener极性指数，文献[6]确定了含个悬挂点的树的最大Wiener极性指数，并刻画了极图. 在文献[7-8]中，作者研究了单圈图和六角系统的Wiener极性指数，并刻画了极图. 本文确定了双圈图的极小Wiener极性指数，并刻画了极图，同时也研究了点不交的双圈图的极小Wiener极性指数，并刻画了极图.先介绍一些符号和术语，用或者表示点在图中的邻域，表示点在图中的度. 如果，则称点为悬挂点. 图的围长是指此图的最短圈的长度. 用，和分别表示点数为的圈，星和路. 用表示含个点的双圈图，它的两个圈的长度分别为和，这两个圈不含公共顶点（点不交）. 对图的任意满足的顶点，如果不连通（此时称是图的割点)，并且树是它的一个连通分支，则由点和树的并导出的树称为在点的一个悬挂树，记作. 点上的所有悬挂树的并记作. 设和是两个连通图，点，是两个度至少为3的点，是至少含有2个顶点的树，的一个悬挂点与粘合，另一个悬挂点与粘合，得到图，把称为图的桥树，记作. 其余未定义的符号和术语，请参见文献[9].设是两个整数. 用边分别将和个顶点连接到路的两个端点上，得到图[10]. 当时，星图可以记为. 用表示所有点数为的树的集合. 根据文献[10]中的定理2.2和2.3，得到下列引理1.引理1[10] 若树含个顶点，则，等号成立当且仅当；如果则，等号成立当且仅当，其中且.引理2 设是一个连通图，是它的一个含个点的悬挂树. 如果是将中的变换为路得到的图，那么，等号成立当且仅当，其中，在的邻点的度为2.证明令，. 用表示中到距离为3的点数. 因为并且，所以据引理1得. 因为，据式（1）得. 注意到蕴含. 如果直径并且不是路，那么，并且. 由于，所以如果直径但是，或者但，那么根据引理1有，并且至少其中一个不等式严格成立. 据式（1）也有. 证毕.引理3 令是一个连通图，是图的一个桥树. 如果那么，其中是将图的变换为连接顶点和的路得到的图.证明令. 因为，则不空. 设和是的两个连通分支，其中由点和中含的邻点的分支的并导出的子图，类似定义. 令，，，. 用表示中到的距离等于3的点数，表示中到的距离等于3的点数. 那么，由于，根据引理1得等号成立当且仅当，并且. 如果上述最后一个条件成立，那么点或者在有最大度，因而其中一个顶点的度至少为3. 这表明上述两个条件不可能同时成立，所以. 证毕. 用表示含个顶点的双圈图，它的两个最短圈分别含有和个顶点，这两个圈含有公共路，的其中一个端点上有个悬挂点.证明设图是含有最小Wiener极性指数的极图. 因为，所以它的直径. 从而的围长. 且它的2个最短圈含有一条公共路. 首先，如果，那么这两个圈含有唯一的公共点. 所以，它们的围长都是3. 如果还有其他顶点，那么这些顶点一定是悬挂点，并且与这个公共点相邻，因此.其次，如果，那么这两个最短圈的围长分别是3,3或者3,4. 如果分别是3,4，不可能还有其他顶点，从而. 如果分别是3,3，那么其他顶点都只能与的其中一个端点相邻，所以.最后，如果，那么图的两个最短圈长分别是4,5，或者是4,4，任何其中一种情形下，图都不可能含有其他顶点. 所以，或者. 证毕.为了确定圈不交的双圈图的最小Wiener极性指数，我们还要引进一些其他的符号和术语. 用表示含有顶点，最大度为的单圈图的集合. 设是一个圈，. 先在点上连接个孤立顶点，. 然后，将一个星图的一个1度点与重合，这颗星有个顶点，得到的图记为，其中表示此图的点数；或者将个孤立点连接在上，得到的图记作；或者将的一个邻点的度为2的1度点与重合，得到的图记为. 易见，对所有成立；第二种情形下，；其他两种情形下. 而且，，或者，或者对某个成立. 参考下列图1.引理4[4]298 如果是一个阶的单圈图，那么，等号成立当且仅当.引理5[4]302 设是一个阶的单圈图. 如果，那么，等号成立当且仅当.令是阶的单圈图的圈. 是两个单圈图，其中，. 用表示下列双圈图的集合，这些双圈图是将的一个端点与的一个2度点粘合，另一个端点与的一个2度点粘合，当时这个2度点是.引理6 令是一个含个顶点的双圈图，它的圈是点不交的. 如果它的唯一的桥树是，那么，等号成立当且仅当.证明设是双圈极图，具有极小Wiener极性指数，圈是点不交的，桥树是，其中，，是的连通分支. 用表示导出的子图. 则，根据引理4和引理5，或者，其中. 注意到，我们得到：对任意给定的单圈图，要将最小化，据式（2）只需求得下列线性规划式（3）的最优解，其中，是非负整数.根据引理4和5，是式（3）的两个可行解. 所以，式（3）的可行域是的一个子集. 因为，上下平移直线，则可行域中落在这些平行直线上的最低点是. 所以，式（3）的最优解是，. 结合引理3可知，对任意给定单圈图，极小当且仅当，并且，. 是的一个2度点，当时，这个2度点就是中的.类似推理可得，和是同型的图. 所以，引理成立. 证毕.引理8 设是含个顶点的双圈图，它的圈是点不交的. 如果它唯一的桥树有个顶点，则，等号成立当且仅当.证明设是满足引理条件的双圈极图. 因为，根据引理6可知：的唯一桥树是，它的连接顶点为和，不妨设，，其中，是的两个非空连通分支. 令，. 那么，根据引理5和6，或者，其中，. 注意到，对任意给定单圈图，要将极小化，据式（4）只需求下列线性规划的最优解，其中，是非负整数.根据引理4和5，是式（5）的两个可行解. 所以，式（5）的可行域是的某个子集. 上下平行移动直线，易见，可行域中落在平行直线上的最低点是. 所以，式（4）的最优解是，. 结合引理3可得，对任意给定单圈图，极小当且仅当，并且，，点是它的一个2度顶点，当时，此2度顶点就是中的顶点.类似推理可知，是与同型的图. 所以，证毕.定理2 若是含个顶点的双圈图，且它的圈是点不交的，那么，等号成立当且仅当并且.证明根据引理6和引理7，定理显然成立. 证毕.[1] WIENNER H. Structural determination of paraffin boiling points [J]. Amer Chem Soc, 1947, 69(1): 17-20.[2] LUKOVITS I，LINERT W. Polarity-numbers of cycle-containing structures [J]. Chem Inform Comput Sci, 1947, 38(4): 715-719.[3] ROUVRAY D H, KING R B. Topology in chemistry-discrete mathematics of molecules [M]. [S.l.]: Horwood Pub, 2002.[4] LIU Muhuo, LIU Bolian. On the Wiener polarity index [J]. MATCH Commun Math Comput Chem, 2011, 66(1): 293-304.[5] DU Wenxue, LI Xueliang, SHI Yongtang. Algorithms and extremal problem on Wiener polarity index [J]. MATCH Commun Math Comput Chem, 2009, 62(1): 235-244.[6] DENG Hanyuan, XIAO Hui. The maximum Wiener polarity index oftrees with pendants [J]. App Math Lett, 2010, 23(6): 710-715.[7] BEHMARAMA A, YOUSEFI-AZARI H, ASHRAFI A R. Wiener polarity index of fullerenes and hexagonal systems [J]. App Math Lett, 2012, 25(10): 1510-1513.[8] HOU Huoquan, LIU Bolian, HUANG Yufen. The maximum Wiener polarity index of unicyclic graphs [J]. Appl Math Comput, 2012, 218(20): 10149-10157.[9] BANDY J B A, MURTY U S R. Graph theory [M]. London: Springer, 2008.[10] LIU Bolian, HOU Huoquan, HUANG Yufen. On the Wiener polarity index of trees with maximum degree or given number of leaves [J]. Comput Math Appl, 2010, 60(7): 2053-2057.。

几类化学图的基于距离的拓扑指标李银灿;梁晓东【摘要】在化学图论中,基于距离的拓扑指标是很重要的一类.该文主要讨论了4个基于距离的拓扑指标,Wiener指标,Hyper-Wiener指标,Harary指标和RCW指标,并总结推导出了Pn,硅酸盐链和n长Kn链关于上述4个指标的计算公式.【期刊名称】《曲阜师范大学学报（自然科学版）》【年(卷),期】2019(045)001【总页数】5页(P23-27)【关键词】Wiener指标;Hyper-Wiener指标;Harary指标;RCW指标;硅酸盐链;n 长Kn链【作者】李银灿;梁晓东【作者单位】新疆大学数学与系统科学学院,830046,新疆维吾尔自治区乌鲁木齐市;新疆大学数学与系统科学学院,830046,新疆维吾尔自治区乌鲁木齐市【正文语种】中文【中图分类】O157.51 引言令G=(V,E)是一个连通图,其中V(G)表示G的顶点集，E(G)表示G的边集.图G中的u,v两顶点间的距离是指u,v两顶点间最短路的长度,记为dG(u,v).图G中各顶点之间最长的路称为G的直径,记为d[1].本文中,用Cn，Pn，Kn分别表示圈,路和n阶完全图,其他未定义的符号和术语参见文献[2,3].一个图可以通过多项式,各类矩阵或指标等不同的方面去认识.有关基于距离的拓扑指标的研究开始于1947年[4].第一个基于距离的拓扑指标是由Harold Wiener提出的Wiener指标W(G),是用来计算一些烷类的沸点.各类基于距离的拓扑指标的计算是基于距离矩阵或与之相关的距离基矩阵.早期对于基于距离的拓扑指标的研究,主要针对的是树,单圈图,双圈图等[5,6],而对于网络的研究较少.一些网络的拓扑结构在化学分子结构方面有着相应的体现,例如由SiO4形成的硅酸盐链等,可以从不同的方面去研究这些网络的拓扑性质.Wiener 指标的定义为在1993年,由Milan Randi[7]定义了另一个基于距离的拓扑指标,即 Hyper-Wiener 指标:在1992年,由 Mihali Trinajst[8]首先定义了 Harary 指标H(G),现在 Harary 指标的定义[9,10]为在2000年,由 Ivanciuc[11,12]定义了RCW(G)(Reciprocal Complementary Wiener)指标:本文中,将运用这些基于距离的拓扑指标来研究Pn,硅酸盐链,n长Kn链等化学图的拓扑性质.2 主要结果2.1 路图Pn是一条n-1长的路,其顶点数为n,边数为n-1.图Pn也可以看作是n-1个K2相连的情形.根据点对间距离的不同,可以进行如下计数.表1 路Pn基于距离的点对计数距离12...n-1点对数n-1n-2 (1)从 Wiener 指标的定义,我们不难得到:命题2.1 若图Pn是一条n-1长的路,则它的Wiener 指标为定理2.2 若图Pn是一条n-1长的路,则它的 Hyper-Wiener 指标证明表1列出了Pn基于距离的点对计数,运用 Hyper-Wiener 指标的计算公式,可得Pn的 Hyper-Wiener 指标如下:对于化学图 Harary 指标的计算,需要运用调和级数的欧拉公式:其中c为欧拉常数0.57721…定理2.3 若图Pn是一条n-1长的路,则它的 Harary 指标其中c为欧拉常数0.57721…证明由表1,运用 Harary 指标的计算公式,不难得到由欧拉公式,其中c为欧拉常数0.57721…定理2.4 若图Pn是一条n-1长的路,则它的RCW 指标RCW(Pn)=n-1.证明由表1,且由于Pn的直径d=n-1,运用RCW指标计算公式,可得2.2 硅酸盐链n长的硅酸盐链是由n个四面体按线性链接构成的,记为CSn,其顶点数为3n+1,边数为6n.CSn也可以看作是由n个K4线性链接构成.n长的硅酸盐链可见图1,其基于距离的点对计数可见表2.图1 n长硅酸盐链CSn表2 CSn基于距离的点对计数距离12...k...n点对数6n9(n-1)...9(n-(k-1)) (9)定理2.5 若图CSn为n长硅酸盐链,则证明由表2给出的图CSn基于两点间距离的点对计数,运用Wiener 指标的计算公式,可得定理2.6 若图CSn为n长硅酸盐链,则证明由表2,运用Hyper-Wiener指标的计算公式,可得WW(CSn)定理2.7 若图CSn为n长硅酸盐链,则其中c为欧拉常数0.57721…证明由表2,运用Harary指标的计算公式,不难得到由欧拉公式,其中c为欧拉常数0.57721…定理2.8 若图CSn为n长硅酸盐链,则RCW(CSn)=9n-3.证明由表2,且由于CSn的直径d=n,运用RCW指标的计算公式,可得2.3 n长Kn链基于上面的情形,我们可以将有关计算推广到n个Kn线性链接构成的图中,可将此图记为G,其顶点数为(n-1)n+1n,边数为该图基于距离的点对计数,可见表3.表3 n长Kn链G基于距离的点对计数距离12…k…n点对数n(n-1)2n(n-1)3…(n-1)2(n-(k-1))…(n-1)2定理2.9 若图G为n长Kn链,则证明由表3给出的图G基于距离的点对计数,运用Wiener指标的计算公式,可得定理2.10 若图G为n长Kn链,则证明由表3,运用Hyper-Wiener指标的计算公式,可得定理2.11 若图G为n长Kn链,则其中c为欧拉常数0.57721…证明由表3,运用Harary指标的计算公式,不难得到其中c为欧拉常数0.57721…定理2.12 若图G为n长Kn链,则证明由表3,且由于G的直径d=n,运用RCW指标的计算公式,可得参考文献：【相关文献】[1] Deza E, Deza M M. Dictionary of Distances [M]. ELsevier Science Ltd, 2006.[2] Bondy J A, Murtywrited U S R. Graph Theory with Applications [M]. The Macmillan Press Ltd, 1976, 28(1) : 237-238.[3] Harary F. Graph theory [M]. Addison-Wesley, 1969. 67-128.[4] Wiener H. Structural determination of paraffin boiling points [J]. Journal of theAmerican Chemical Society, 1947, 69(1) : 17-20.[5] Dobrynin A A, Entringer R, Gutman I. Wiener Index of Trees: Theory and Applications [J]. Acta Applicandae Mathematica, 2001, 66(3) : 211-249.[6] Eliasi M, Raeisi G, Taeri B. Wiener index of some graph operations [M]. Elsevier Science Publishers B V, 2012.[7] Randic M. Novel molecular descriptor for structure-property studies [J]. Chemical Physics Letters, 1993, 211(4-5) : 478-483.[8] Mihalic Z, Trinajstic N. A graph-theoretical approach to structure-property relationships [J]. Journal of Chemical Education, 1992, 69(9) : 701.[9] Plavši D, Nikoli S, Trinajsti N, et al. On the Harary index for the characterization of chemical graphs [J]. Journal of Mathematical Chemistry, 1993, 12(1) : 235-250.[10] Ivanciuc O, Balaban T S, Balaban A T. Design of topological indices. Part 4. Reciprocal distance matrix, related local vertex invariants and topological indices [J]. Journal of Mathematical Chemistry, 1993, 12(1): 309-318.[11] Ivanciuc O. QSAR comparative study of Wiener descriptors for weighted molecular graphs [J]. Journal of Chemical Information Computer Sciences, 2000, 40(6) : 1412. [12] Entringer R C, Jackson D E, Snyder D A. Distance in graphs [J]. Czechoslovak Mathematical Journal,1976,26(2):283-296.[13] Hayat S, Imran M. Computation of topological indices of certain networks [J]. Applied Mathematics Computation, 2014, 240(4) : 213-228.。

第二小距离特征值在给定区间中所确定的图翟丹丹【摘要】令G=(V,E)是一个具有n个顶点的简单无向图.对于任意一个n阶简单无向图,它有n个距离特征值.本文主要研究其中第二小距离特征值.利用了禁用子图的方法,刻画了在区间λn?1(D(G))∈[?2.4295,0]中的所有树,以及满足λn?1(D(G))∈[?2,0]的所有单圈图和双圈图.【期刊名称】《工程数学学报》【年(卷),期】2018(035)004【总页数】11页(P468-478)【关键词】第二小距离特征值;树;单圈图;双圈图【作者】翟丹丹【作者单位】华东理工大学数学系,上海 200237【正文语种】中文【中图分类】O157.51 IntroductionAll graphs mentioned are simple connected graphs,undirected,loop free and having no multiple edges.Considering a connected graphG=(V,E),while V={v1,v2,···,vn}is its vertex set and E is its edge set.The order of G is the number n=|V|of its vertices and its size is the number m=|E|ofits edges.For vi,vj∈V(G),the distance dG(vi,vj)or dijfor short,it is def i ned to be the length(i.e.the number of edges)of the shortest path between viand vjin G.The diameter of G is the maximal distance between any two vertices,denoted by d(G).The distance matrix of G is denoted byD(G)=(dij)n×n.The characteristic polynomial of D(G)is denoted byΦ[D(G),λ]=det(D(G)− λI).Since D(G)is a real symmetric,nonnegativ e and irreducible matrix,all of its eigenvalues must be real[1],and can be ordered as λ1(D(G))≥ λ2(D(G))≥ ···≥ λn(D(G)).The largest eigenvalue λ1(D(G))is called the distance spectral radius of G,λn−2(D(G)),λn−1(D(G))andλn(D(G))are said to be the third sma llest,the second smallest and the least distance eigenvalue of G,respectively.A graph is{H1,H2,···,Hk}-free if it contains no induced subgraph isomorphic to any Hifor i=1,2,···,k.A connected graph G with|E(G)|=n−1 is a tree,denoted by T.Let an nvertex connected graph G with|E(G)|=n and|E(G)|=n+1 be a unicyclic and bicyclic graph,respectively.Recall that Pn,Cnand Kndenoted the path,the cycle and the complete graph with n vertices,respectively.The girth g(G)is the length of the shortest cycle in G.Let Kn1,n2,···,nkdenote the complete k-partite graph.The union of two graphs G1and G2is the graph G1∪G2with vertex set V(G1)∪V(G2)and edge set E(G1)∪E(G2).The complete productG1∨G2of graphs G1and G2is the graph obtained from G1∪G2by joining every vertex of G1with every vertex of G2.The research of distance eigenvalues of connected graphs dates back to the classical work of Edelberg,Edelberg et al[2],Graham andLov´asz[3],Graham and Pollack[4].The distance spectral radius of graphshave been studied by researchers for many years.For many results related to the distance spectral radius reader can see[5-10].Recently,there are some results about the third smallest,the second smallest and the least distance eigenvalue shown in many references.Yu[11]had found all the conn ected graphs with λn(D(G)) ∈ [−2.383,0]and all the trees with λn(D(G)) ∈ [−3.4142,0].Lin and Zhou[12]improved the conclusion about the trees and obtained the trees withproved that if G is a connected graph with n vertices,then λn(D(G)) ≤ −1,with equality h olding if and only if G ∼=Kn,and λn(D(G)) ≤ −2,with equality holding if and only if G ∼=Kn1,n2,···,nkand G?Kn.Lin et al[14]discussed that if G is a connected graph with n ≥ 4,then λn−1(D(G))≤ −1,with equality holding if and only if G and if G is a connecte d graph with n(n ≥ 7)vertices,then λn−2(D(G)) ≤ −1.In this paper,we determine trees with λn−1(D(G))∈ [−2.4295,0],unicyclic and bicyclic graphs with λn−1(D(G))∈ [−2,0],respectively.2 PreliminariesLemma 1 Let A be n×n Hermitian matrices and B be a principa l submatrix of A of order m.If λ1(A)≥ λ2(A)≥ ···≥ λn(A)is the eigenvalues of A andµ1(B)≥µ2(B)≥ ···≥ µm(B)is the eigenvalues of B,thenApplying Lemma 1 to the distance matrix of a graph,we have the following result.Lemma 2 Let G be a simple connected graph of order n with distance eigenvalues λ1(D(G))≥ λ2(D(G))≥ ···≥ λn(D(G)),H is a induced subgraph of G of order m with distance eigenvaluesµ1(D(H))≥ µ2(D(H))≥ ···≥µm(D(H)).Then3 Trees with λn−1(D(T)) ∈ [−2.4295,0]For some examples of trees with λn−1(D(T)) ∈ [−2.4295,0],see Figure 1. Figure 1: Trees and forbidden subgraphsLemma 3 Let T be a tree of order n and D(T)be the distance matrix of T.If λn−1(D(T))∈ [−2.4295,0],then T is T∗-free,where T∗={P7,T1,T2,T3}.Proof By contradiction,we assume that T contains one of T∗as a induced subgraph,then D(T)contains one of D(P7)and D(Ti)for i=1,2,3 as a principal submatrix.By a simple calculation,From Lemma 2,we have λn−1(D(T))< −2.4295.It is a contradiction withλn−1(D(T))∈[−2.4295,0].Hence the result is proved.Let Jn×mand0n×mbe respectively the all-one and the all-zero n × m matrices.Let Jn=Jn×n,1n=J1×nand0n=01×n.Lemma 4 If T∈{P6,T4(a,b),T5(a,b)}is a tree of order n,thenProof For convenience,let T4and T5denote T4(a,b)andT5(a,b),respectively.By a direct calc ulation,λ5(D(P6))= −2.4295 ∈[−2.4295,0].Now the characteristic polynomial of the matrix D(T4)is given bywhereThenLetIt is easy to see that if a=0 or b=0,then T4(a,b)∼=T5(1,b)orT4(a,b)∼=T5(a,1).So,we may assume that a≥1 and b≥1.Note thatThrough the existence theorem for roots of unitary quadraticfunction,there exist two real numbers t1,t2(t1<t2)such that t1< −2,t2>0 and f ′′′(t1)=f ′′′(t2)=0.Thus we have f′′′(t)>0 in(−∞,t1)and(t2,+∞),and f′′′(t)<0 in(t1,t2),which means f′′(t)is increasing in(−∞,t1)and(t2,+∞),and decreasing in(t1,t2).Since f′′(0)<0,f′′(−2)>0,again by the monotonicity of function and the existence theorem for roots,there are real numbersx1,x2,x3(x1<x2<x3)such thatThen f′′(t)<0 in(−∞,x1)and(x2,x3),and f′′(t)>0 in(x1,x2)and(x3,+∞),so we get that f′(t)is increasing in(x1,x2)and(x3,+∞),and decreasingin(−∞,x1)and(x2,x3).Since f′(0)<0,f′(−2)<0,so by a similar analysis,there exist real numbers y1,y2,y3,y4(y1<y2<y3<y4)such thatandIt follows that f′(t)<0 in(y1,y2)and(y3,y4),and f′(t)>0in(−∞,y1),(y2,y3)and(y4,+∞),which means f(t)is increasingin(−∞,y1),(y2,y3)and(y4,+∞),and decreasing in(y1,y2)and(y3,y4).It follows from f(0)<0 and f(−2)>0 that λn−1(D(T4))∈ [−2.4295,0].By the same way as D(T4),the characteristic polynomial of D(T5)is given byThen by a similar discussion for Φ[D(T5),t],we have λn−1(D(T5)) ∈[−2.4295,0]and the result follows.Theorem 1 If T is a tree of order n and D(T)be the distance matrix of T,then λn−1(D(T))∈ [−2.4295,0]if and only if T ∈ {P6,T4(a,b),T5(a,b)}.Pro of If T∈{P6,T4(a,b),T5(a,b)},then by Lemma 4,the result holds.For converse,by Lemma 3,we get that T is T∗-free,then d(T)≤ 5.If d(T)=5,then T∼=P6,if d(T)=4,d(T)=3 and d(T)=2,then T∼=T4(a,b),T∼=T5(a,b)andT∼=T5(a,0),respectively.Thus we complete the proof.By a straightforward calculation,the unicyclic and bicyclic graphs have the similar conclusions.In the following,we will determine unicyclic and bicyclic graphs with4 Unicyclic graphs with λn−1(D(G))∈ [−2,0]For some examples of unicyclic graphs with λn−1(D(G))∈ [−2,0],see Figure 2.Figure 2:Unicyclic graphs and forbidden subgraphsLemma 5 Let G be a unicyclic graph of order n and D(G)be the distance matrix of G.If λn−1(D(G))∈ [−2,0],then G is G∗-free,where G∗={P6,T3,G1,G2,G3,G4,G5}.Proof By Lemmas 3 and 4,G is{P6,T3}-free.By contradiction,we may assume that G contains one of{G1,G2,G3,G4,G5}as an induced subgraph,thenD(G)must contains one of D(Gi)for i=1,2,3,4,5 as a principal submatrix.By a simple calculation,By Lemma 2,we have λn−1(D(G))< −2.It is a contradiction with λn−1(D(G)) ∈[−2,0].The proof is complete.Lemma 6 If G∈{G6,G7,G8,G9,G10}is a unicyclic graph of order n,thenProof By a straightforward calculation,we haveBy a similar discussion in Lemma 4 for Φ[D(Gi),t](i=6,7,8,9,10),we haveλn−1(D(G))∈ [−2,0].Thus we complete the proof.Theorem 2 If G is a unicyclic graph of order n and D(G)be the distance matrix of G,then λn−1(D(G))∈ [−2,0]if and only if G ∈ {G6,G7,G8,G9,G10}. Proof The sufficient part is obvious by Lemma 6.So we only need to prove the necessity.By Lemma 5,P6and G4are forbidden subgraphs of G,thend(G)≤4 and g(G)≤4.Since G is{T3,G1,G2,G3,G5}-free,so we get that ifg(G)=3,d(G)≤4,then G∈{G6,G7,G8},and if g(G)=4,d(G)≤4,thenG∈{G9,G10}.Hence the result is proved.5 Bicyclic graphs with λn−1(D(G)) ∈ [−2,0]Let Cpand Cqbe two vertex-disjoint cycles.Suppose that v1is a vertex of Cpand vlis a vertex of Cq.An∞-graph,denoted by∞(p,l,q),is obtained from Cpand Cqby joining v1and vlby a path v1v2···vlof length l−1,where l≥ 1,l=1means identifying v1with vl.Let Pp,Pland Pqbe three vertex-disjoint paths,where min{p,l,q}≥2 and at most one of them is 2.A θ-graph,denoted by θ(p,l,q),is obtained from Pp,Pland Pqby identifying the three initial vertices and terminal vertices of them,respectively,see Figure 3.Figure 3: Graphs ∞(p,l,q)and θ(p,l,q)It is well-known that the connected bicyclic graphs can be partitioned into two types:the type of graphs which contain an∞-graph as an induced subgraph,and the other type of graphs which contain a θ-graph as ani nduced subgraph.A graph∞(p,l,q)(or θ(p,l,q)),denoted by BG,is called the base-graph of the corresponding bicyclic graph G which contains it as an induced subgraph.The following two lemmas can be easily get by analogous calculations and proofs of trees and unicyclic graphs,see Figure 4.Lemma 7 Let G be a bicyclic graph of order n and D(G)be the distance matrix of G.If λn−1(D(G))∈ [−2,0],then G is G∗-free and G∗∗-free,whereFigure 4:Bicyclic graphs and forbidden subgraphsLemma 8 If G∈{Gi,Gk,Gl,Gm,Gn,Go,Gp,Gq,Gr,Gs,Gt,Gu,Gv,Gw,Gx,Gy}is a bicyclic graph of order n,then λn−1(D(G))∈ [−2,0].Proof By a straightforward calculation,we haveBy a similar discussion in Lemma 4 for Φ[D(Gi),t](i=l,n,p,q,r,s,t,u,v,w,x,y),we have λn−1(D(G))∈ [−2,0].This completes the proof.Theorem 3 If G is a bicyclic graph of order n and D(G)be the distance matrix of G,then λn−1(D(G))∈ [−2,0]if and only ifProof The sufficient part is obvious by Lemma 8.So we only need to prove the necessity.By Lemma 7,G is G∗-free and G∗∗-free,then d(G)≤ 4 andg(G)≤ 4.Thus we discuss the following two cases.Case 1 G contains an∞-graph as an induced subgraph.Then BG ∈ {∞(3,3,3),∞(3,2,3),∞(3,1,3),∞(3,2,4),∞(3,1,4),∞(4,1,4)}.So we have G∈{Gj,Gk,Gl,Gm,Gn,Go}.Case 2 G contains a θ-graph as an induced subgraph.Then BG ∈ {θ(3,2,3),θ(3,2,4),θ(3,3,3)}.So we have G ∈{Gp,Gq,Gr,Gs,Gt,Gu,Gv,Gw,Gx,Gy}.Thus we complete the proof. References:【相关文献】[1]Cvetkovi´c D,Doob M,Sachs H.Spectra of Graphs—Theory and Application(3rd Edition)[M].Heidelberg-Leipzig:Johann Ambrosius Barth Verlag,1995[2]Edelberg M,Garey M R,Graham R L.On the distance matrix of a tree[J].Discrete Mathematics,1976,14(1):23-39[3]Graham R L,Lov´asz L.Distance matrix polynomials of trees[J].Advances in Mathematics,1978,29(1):60-88[4]Graham R L,Pollack H O.On the addressing problem for loop switching[J].Bell System Technical Journal,1971,50(8):2495-2519[5]Ili´c A.Distance spectral radius of trees with given matching number[J].Discrete Applied Mathematics,2010,158(16):1799-1806[6]Indulal G.Sharp bounds on the distance spectral radius and the distance energy ofgraphs[J].Linear Algebra and Its Applications,2009,430(1):106-113[7]Lin H,Yang W,Zhang H,et al.Distance spectral radius of digraphs with given connectivity[J].Discrete Mathematics,2012,312(11):1849-1856[8]Merris R.The distance spectrum of a tree[J].Journal of Graph Theory,1990,14(3):365-369[9]Yu G,Wu Y,Zhang Y,et al.Some graft transformations and its application on a distance spectrum[J].Discrete Mathematics,2011,311(20):2117-2123[10]Zhang X.On the distance spectral radius of some graphs[J].Linear Algebra and Its Applications,2012,437(7):1930-1941[11]Yu G.On the least distance eigenvalue of a graph[J].Linear Algebra and Its Applications,2013,439(8):2428-2433[12]Lin H,Zhou B.On least distance eigenvalues of trees,unicyclic graphs and bicyclic graphs[J].Linear Algebra and Its Applications,2014,443(1):153-163[13]Lin H,Hong Y,Wang J,et al.On the distance spectrum of graphs[J].Linear Algebra and Its Applications,2013,439(6):1662-1669[14]Lin H,Zhai M,Gong S.On graphs with at least three distance eigenvalues lessthan−1[J].Linear Algebra and Its Applications,2014,458(10):548-558。

一类双圈图关于两种拓扑指标的排序田文文;田双亮【摘要】The Merrifield-Simmons index and Hosoya index of the class of bicyclic graphs G m,kn,p,q are investigated, and their orderings with respect to these two topological indices are obtained.%研究了一类双圈图G m,kn,p,q的Merrifield-Simmons指标和Hosoya指标，并给出了该类双圈图关于这两种拓扑指标的排序。

【期刊名称】《计算机工程与应用》【年(卷),期】2015(000)018【总页数】4页(P52-55)【关键词】双圈图;Merrifield-Simmons指标;Hosoya指标;排序【作者】田文文;田双亮【作者单位】西北民族大学数学与计算机科学学院，兰州 730030;西北民族大学数学与计算机科学学院，兰州 730030【正文语种】中文【中图分类】O157.5Hosoya指标是由日本化学家Haruo Hosoya于1971年在文献[1]中提出并进行研究的，它表示图G中所有匹配的数目，记为μ(G)，该指标与物质的沸点、熵、化学键的计算和化学结构等有着密切的联系。

Merrifield-Simmons指标是在1989年由美国化学家Richard E.Merrifield和Howard E.Simmons在文献[2]中引入的化学拓扑指标，它表示图G中所有独立集的数目，记为σ(G)，该指标与物质的沸点有着密切的联系。

这两个拓扑指标在结构化学中有着重要的意义，它们常常被用来描述有机化合物的物理化学特征与药理特征，且有着较为广泛的应用，相关的应用参见文献[2-4]。

文献[5]中研究了单圈图中最大的Merrifield-Simmons 指标和最小的Hosoya指标；文献[6]中单圈图关于Merrifield-Simmons指标和Hosoya指标的排序；文献[7-8]中确定了双圈图的最大和最小的Merrifield-Simmons指标；文献[9]中确定了双圈图的最小的Hosoya指标；文献[10]中确定了给定最大度的双圈图的最小的Hosoya指标；文献[11]中研究了给定悬挂顶点的树关于Merrifield-Simmons指标和Hosoya指标的排序；文献[12]中研究了关于Hosoya指标和Merrifield-Simmons指标的极值树；文献[13]中研究了一类双圈图的两种指标的排序。

某种双圈图的L(2,1)-标号的岛序列雒金梅;左连翠【摘要】通过构造洞指数ρ(G)≥1的一类双圈连通图得到了容许至少两个不同岛序列的连通图.【期刊名称】《天津师范大学学报（自然科学版）》【年(卷),期】2012(032)001【总页数】4页(P13-16)【关键词】岛序列;轻点;重点;2-稀疏图;洞指数;路覆盖数【作者】雒金梅;左连翠【作者单位】天津师范大学数学科学学院,天津300387;天津师范大学数学科学学院,天津300387【正文语种】中文【中图分类】O157.5L（2，1）－标号是类似于频率分配的顶点标号问题.图G的一个L（2，1）－标号是从G 的顶点集V（G）到非负整数集｛0，1，…，k｝的一个函数f，满足：如果d（x，y）＝1，则｜f（x）－f（y）｜≥2；如果d（x，y）＝2，则｜f（x）－f（y）｜≥1.其中d（x，y）表示顶点x和y之间的距离.标号问题可用来模仿无线电分配［1］.图G 的使用集合｛0，1，…，k｝（未必是所有的元素）中的元素进行标号的一个L（2，1）－标号叫做一个k标号.使得G有一个k标号的最小的k称为G的λ数，用λ（G）表示.一个λ（G）标号简记为λ标号.称一个k标号有洞h（0＜h＜k），如果h在这个标号中没有被使用.G的所有λ（G）标号的洞的个数的最小值叫做G的洞指数，用ρ（G）表示.不难看出，如果一个λ（G）标号恰有ρ（G）个洞，那么任意两个洞是不连续的［2］.一个有ρ（G）个洞的图G 的一个给定λ标号的岛是指用于标号的连续整数的极大集合.一个有ρ（G）个洞的图G的一个给定λ标号的岛序列是指岛基数按不减顺序的有序排列（允许基数重复）.Georges J.P.等提出洞指数ρ（G）≥1、有两个不同岛序列的连通图是否存在的问题［2］.Adams S.S.证明了2－稀疏树的补图容许至少两个不同的岛序列［3］.本研究给出了另一类容许两个不同岛序列的连通图.定义1 图G的一个路覆盖是指G中包含G的所有顶点的点不交的路的集合.图G的路覆盖数用c（G）来表示，是G的具有最少路数的一个路覆盖中路的数目.恰有c（G）条路的一个路覆盖称为G的最小路覆盖.定义2 一个图称为2－稀疏图如果它不包含相邻的且度大于2的顶点对.图中的一个顶点称为重点，如果它的度大于2，否则称为轻点，其中一度点称为叶子点.因此一个图是2－稀疏图如果它不包含任何相邻的重点对.下面的引理给出了路覆盖和轻点或重点之间的联系.为方便，用GC表示图G的补图.引理1［3］如果v是2－稀疏图G的一个重点，那么v是G的每个最小路覆盖中的一个内点.引理2［3］设G 是有m（m≥1）条边，n个顶点，p个叶子点的一个连通2－稀疏图.如果G不是圈，那么c（G）＝p＋m－n.引理3［3］设G是一个有n个顶点的图，那么c（GC）≥2当且仅当λ（G）＝n ＋c（GC）－2.引理4［3］设G是一个有n个顶点的图，且λ（G）≥n－1，那么ρ（G）＝c（GC）－1.图G的一个藤S定义为G中的一条极大路，且满足一个端点是叶子点，其余点在S中为轻点.在给出主要结果之前，需要下面的引理.引理5 设e为一个双圈2－稀疏图G中与两个轻点关联的一条边，如果e不在任意一个圈中，那么e包含在G的每个最小路覆盖中.证明设u和w为与e关联的两个轻点.假设存在G的不包含e的一个最小路覆盖，因为u和w为轻点，那么在这个最小路覆盖中存在以u为端点的路P和以w为端点的路Q，并且边e既不在P中，也不在Q中.由于e不在任意一个圈中，P和Q 是不同的，因此P＋Q＋e是一条路.用P＋Q＋e取代原来的路P和Q，得到了路数更少的G的一个路覆盖，与假设矛盾，因此e包含在G的每个最小路覆盖中.引理6 设G是一个有m（m≥1）条边，n个顶点，p个叶子点的连通2－稀疏图.如果G不是圈且p＋m－n≥2，那么证明由引理2知c（G）＝p＋m－n≥2，由引理3知由于p＋m－n≥2，因此有p＋m－2≥n，因此由引理4知ρ（GC）＝c（G）－1＝p＋m－n－1.引理6确定了某类非圈连通2－稀疏图的λ数和洞指数之间的关系.定理1 设G是一个有m（m≥1）条边，n个顶点，p（p≥2）个叶子点的双圈连通2－稀疏图，G中每个圈中的顶点个数比每个藤中的顶点个数至少多2，且G中无偶圈，那么GC容许至少两个不同的岛序列.证明p≥2，通过对p进行归纳来证明.首先证明p＝2时成立.当p＝2时，由引理2可知c（G）＝p＋m－n＝2＋m－n，因为G是双圈图，故m＝n＋1，所以c（G）＝3.由引理3可知λ（GC）＝n＋c （G）－2＝n＋3－2＝n＋1.由引理4知ρ（GC）＝c（G）－1＝3－1＝2.考虑G中两个圈的位置关系，分两种情况讨论.情况1 两个圈是点不交的.情况1.1 两个叶子点分别在两个圈上.图1给出了G的两个最小路覆盖（P1，P2，P3）和（P′1，P′2，P′3），其中P1 为以两个叶子点为端点的最长路.P1＝u1u2…ul1，P2＝v1v2…vl2，P3＝w1w2…wl3；P′1＝x1x2…xl′1，P′2＝y1y2…yl′2，P′3＝z1z2 …zl′3 .图1的两个最小路覆盖导出了GC的恰有ρ（GC）＝2个洞的两个λ（GC）标号f1 和f2，其中：f1（ui）＝i－1，i＝1，2，…，l1；f1（vi）＝l1＋i，i＝1，2，…，l2；f1（wi）＝l1＋l2＋1＋i，i＝1，2，…，l3；f2（xi）＝i－1，i＝1，2，…，l′1；f2（yi）＝l′1＋i，i＝1，2，…，l′2；f2（zi）＝l′1＋l′2＋1＋i，i＝1，2，…，l′3.由于P1为以两个叶子点为端点的最长路，所以有l1∉｛l′1，l′2，l′3｝，因此由f1 导出的岛序列不同于由f2导出的岛序列，故GC容许两个不同的岛序列.为方便，在以下任何已知情况下，均用（P1，P2，P3）和（P′1，P′2，P′3）表示图G 的两个最小路覆盖，用l1，l2，l3 和l′1，l′2，l′3 表示对应于路覆盖（P1，P2，P3）和（P′1，P′2，P′3）中每条路的顶点个数.情况1.2 两个叶子点悬挂在同一个圈的同一点上.图2给出了G的两个最小路覆盖（P1，P2，P3）和（P′1，P′2，P′3）.图2的两个最小路覆盖导出了GC的恰有ρ（GC）＝2个洞的两个λ（GC）标号f1 和f2（标号规则同情况1.1）.由于G中每个圈中的顶点个数比每个藤中的顶点个数至少多2，故有l′2＞l1.由图2可得l2＜l′2＞l1＞l′1，并且l3＝l′3.若l1＝l′3，则l1＝l3，l′2＞l1＝l′3.那么在｛l1，l2，l3｝中有l1＝l3，而在｛l′1，l′2，l′3｝中l′1≠l′3，l′1≠l′2，l′2≠l′3.若l1≠l′3，由l′1＜l1＜l′2 显然有l1∉｛l′1，l′2，l′3｝.综上可知，由f1导出的岛序列不同于由f2导出的岛序列，从而GC容许两个不同的岛序列.情况1.3 两个叶子点悬挂在同一个圈的不同点上.图3给出了G的两个最小路覆盖（P1，P2，P3）和（P′1，P′2，P′3），其中P1 为以两个叶子点为端点的最长路，P′1为以两个叶子点为端点的路，且P1≠P′1.图3的两个最小路覆盖导出了GC的恰有ρ（GC）＝2个洞的两个λ（GC）标号f1 和f2（标号规则同情况1.1）.由图3有l1＞l′1，l3＝l′3，所以l1＋l2＝l′1＋l′2，l2＜l′2＜l1（P1 为以两个叶子点为端点的最长路）.若l′2＝l3，则l′2＝l′3，l1＞l′2＝l3＞l2，因此有l1＞l3＞l2.所以｛l1，l2，l3｝中元素互不相同，而在｛l′1，l′2，l′3｝中有l′2＝l′3.若l′2≠l3，由l2＜l′2＜l1 知l′2∉｛l1，l2，l3｝.综上可知，由f1导出的岛序列不同于由f2导出的岛序列，从而GC容许两个不同的岛序列.情况2 两个圈至少有一个公共点或一条公共边.类似情况1可给出证明，可参考附图.因此p＝2时，GC容许两个不同的岛序列.假设p＞2，对于每个有k（2≤k＜p）个叶子点的双圈2－稀疏连通图G，GC容许至少两个不同的岛序列.考虑任意一个有p（＞2）个叶子点的双圈2－稀疏连通图G，选择G的一个藤S，则G－S为有p－1≥2个叶子点的双圈2－稀疏连通图，根据归纳假设，H＝（G－S）C容许两个不同的岛序列.设g1和g2为H的有ρ（H）个洞且导出两个不同岛序列的λ（H）标号，将这两个标号延拓到S＝v1v2…vs，给vi（i＝1，2，…，s）分配标号λ（H）＋i＋1，则这两个新的标号即为GC的有ρ（H）＋1个洞的（λ（H）＋s＋1）标号.由引理6有因此GC容许两个不同的岛序列.定理2 设G是有p（p≥2）个叶子点的双圈2－稀疏连通图，且G中至少有一个圈中的顶点个数多于3，则GC是连通的.当u和z在GC中相邻时，结论显然成立.设u和z在GC中不相邻.由于v1，v2为G中的叶子点，所以u和z中至少有一个在GC中与vi（i＝1，2）相邻.若u和z在GC中都与某个vi相邻，则uviz即为GC中连通u和z的路.若u和v1在GC中相邻，z和v2在GC中相邻，由于v1，v2为G中的叶子点，且图G不为路，所以v1，v2在G中必不相邻，则在GC中必相邻，从而uv1v2z 即为GC中连通u和z的路.若u和z中恰有一点在GC中与vi（i＝1，2）相邻，而另一个在G中与vi（i＝1，2）相邻.不失一般性，假设u在GC中与vi（i＝1，2）相邻，z在G 中与vi（i＝1，2）相邻，因为v1、v2为G中的叶子点，所以vi（i＝1，2）在GC中与除z以外的所有点相邻.由于G为双圈2－稀疏连通图且G中至少有一个圈中的顶点个数多于3，故存在一个顶点w且w∉｛u，z，v1，v2｝，使得w在GC中与z相邻，显然vi（i＝1，2）与w在GC中相邻，所以uv1wz即为GC中连通u和z的路.综上可得GC是连通的.附图【相关文献】［1］ HALE W K.Frequency assignment［J］.Theory and Applications，1980，68：1497－1514.［2］ GEORGES J P，MAURO D W.On the structure of graphs with non－surjective L（2，1）－labelings［J］.SIAM J Disc Math，2005，19：208－223.［3］ ADAMS S S，TRAZKOVICH A，TROXELL D S，et al.On the island sequences with a condition at distance two［J］.Disc Appl Math，2010，158：1－7.［4］ GEORGES J P，MAURO D W，WHITTLESEY M A.Relating path coverings to vertex labelings with a condition at distance two［J］.Disc Math，1994，135：103－111.。

圈不交的双圈图的距离谱半径
朱忠熏;罗婧;卢鸿艳
【期刊名称】《中南民族大学学报（自然科学版）》
【年(卷),期】2014(033)002
【摘要】图G的距离谱半径ρ(G)是图G的距离矩阵的最大特征值.本文利用线性代数和图论的方法,先给出了一些使距离谱半径递减的图变换,然后利用这些变换确定了圈不交的双圈图中距离谱半径最小的极值双圈图,同时,给出了对应距离谱半径满足的三次方程.
【总页数】4页(P123-126)
【作者】朱忠熏;罗婧;卢鸿艳
【作者单位】中南民族大学数学与统计学学院,武汉430074;中南民族大学数学与统计学学院,武汉430074;中南民族大学数学与统计学学院,武汉430074
【正文语种】中文
【中图分类】O157
【相关文献】
1.不含三圈的双圈图的谱半径 [J], 何春阳
2.双圈图和三圈图的最大拉普拉斯分离度 [J], 余桂东;黄冬明;张午骁;汪宸
3.三圈图的无符号拉普拉斯谱半径 [J], 陈媛媛;王国平
4.恰有k个悬挂点的n阶双圈和三圈图的拟拉普拉斯谱半径 [J], 刘木伙; 谭学忠; 柳柏濂
5.单圈图与双圈图补图的Aα-谱半径 [J], 张荣;郭曙光
因版权原因，仅展示原文概要，查看原文内容请购买。

双圈图的树图
黄坤阳
【期刊名称】《泉州师范学院学报》
【年(卷),期】2003(021)004
【摘要】最大亏格、上可嵌入是图论中的两个重要概念.通过双圈图的树图的边连通度,文章证明了双圈图的树图是上可嵌入的,并给出了双圈图树图最大亏格的表达式.
【总页数】4页(P9-12)
【作者】黄坤阳
【作者单位】泉州师范学院,数学系,福建,泉州,362000
【正文语种】中文
【中图分类】O157.5
【相关文献】
1.树图与单圈图的线图的Hyper-Wiener指数 [J], 张泽清;高玉斌
2.树、单圈图和双圈图改进的第二Zagreb指标 [J], 秦忠芳;袁利;赵飚
3.树图和单圈图的调和指标 [J], 王晓
4.树、单圈图和双圈图中基于顶点度的化学指数的极值结论 [J], 姚悦丹;刘木伙;叶家昌
5.单圈图与双圈图补图的Aα-谱半径 [J], 张荣;郭曙光
因版权原因，仅展示原文概要，查看原文内容请购买。