双圈图补图的距离谱半径_李远菁.pdf

设图 G 是一个简单连通图，点 vi和 vj之间最短路径的长度称为点 vi和 vj在图 G 中的距离，记作 dG(vi,vj)图 G 的距离矩阵为 D(G)=(dG(vi,vj)nn 距离矩阵 D(G)特征值的模的最大值称为图 G 的距离谱半径 在 n 阶双圈图补图中刻画了距离谱半径最大的极图关键词：双圈图；补图；距离谱半径DOI：10.13568/ki.651094.651316.2022.05.19.0003中图分类号：O157.5文献标识码：A文章编号：2096-7675(2023)02-0184-07引文格式：李远菁,李丹,刘康.双圈图补图的距离谱半径J.新疆大学学报(自然科学版)(中英文),2023,40(2):184-190+221.英文引文格式：LI Yuanjing,LI Dan,LIU Kang.The distance spectral radius of the complements of bicyclicgraphsJ.Journal of Xinjiang University(Natural Science Edition in Chinese and English),2023,40(2):184-190+221.The Distance Spectral Radius of the Complements of Bicyclic GraphsLI Yuanjing,LI Dan,LIU Kang(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)Abstract：Let G be a simple connected graph.The distance between vertices viand vjin the graph G,denotedby dG(vi,vj),is the length of the shortest path from vito vj,and D(G)=(dG(vi,vj)nnis the distance matrix ofG.The distance spectral radius of G is defined as the maximum module of eigenvalues of distance matrix D(G).We characterize the extremal graph among the complements of bicyclic graphs with n-order which maximizes thedistance spectral radius.Key words：bicyclic graphs;complements of graphs;distance spectral radius0引 言设G=(V(G),E(G)是一个简单连通图,其中V(G)是图G的顶点集,E(G)是图G的边集.图G的顶点数定义为n=|V(G)|,边数定义为m=|E(G)|.图G的补图为Gc=(V(Gc),E(Gc),其中V(Gc)=V(G),E(Gc)=vivj|vivj/E(G),vi,vj V(G).设vi,vj V(G),若vivj E(G),则vi,vj在图G中相邻,记作vivj;否则vi,vj在图G中不相邻,记作vivj.图G中与点v相邻的顶点集称为点v在图G中的邻集,记作NG(v).NGv=NG(v)v称为点v在图G中的闭邻集.dG(v)=|NG(v)|称为点v在图G中的度.点vi和vj之间最短路径的长度称为点vi和点vj在图G中的距离,记作dG(vi,vj).图G中任意两点之间距离的最大值称为图G的直径,记作diam(G).图G的邻接矩阵为A(G)=(aij)nn,其中当vivj时,aij=1,否则aij=0.图G的距离矩阵为D(G)=(dG(vi,vj)nn.图G的距离特征多项式为PG()=|InD(G)|.距离矩阵D(G)的特征值集合称为图G的距离谱,记1(D(G)2(D(G)n(D(G)是图G的距离谱的一个排序.矩收稿日期：2022-05-19基金项目：国家自然科学基金“关于图的距离矩阵的相关特征值的研究”（11901498）作者简介：李远菁（1997-），女，硕士生，从事图谱理论的研究通讯作者：李丹（1988-），女，博士，副教授，主要从事图谱理论的研究，E-mail:第2期李远菁，等：双圈图补图的距离谱半径185阵M特征值的模的最大值称为矩阵M的谱半径.显然,图G的距离矩阵D(G)是非负不可约的,D(G)的最大特征值就是图G的距离谱半径,记作(G).若连通图G的边数与点数有如下关系:m=n+1,则称图G是一个双圈图.本文用Bn表示n阶双圈图的集合.Cn,Pn,K1,n1和Tp,q(p+q=n2)分别表示n阶的圈、路、星和双星.设h,l,k是任意非负整数且h k 3,Ch和Ck分别是包含点u和点v的两个点不相交的圈,Pl+1是u,v之间的一条路,图Dh,l,k是由圈Ch,Ck和路Pl+1组成的图.设P,P是顶点u,v之间的两条不同的路,若V(P P)=u,v,则称P,P是连接u,v的两条内部点不相交的路.设h,l,k是任意正整数,图h,l,k是由连接u,v的三条内部点不相交的路Ph+1=uu1uh1v,Pl+1=uu1ul1v和Pk+1=uu1uk1v组成的图.本文用Dn表示将图Dh,l,k的点上粘上一些悬挂树的n阶图集合,n是将图h,l,k的点上粘上一些悬挂树的n阶图集合.显然,Bn=Dnn.设p,q是任意正整数,图2,1,2u(p,q)是在图2,1,2的u点上粘接双星树Tp1,q得到的图,且dTp1,q(u)=p,dTp1,q(u)=q+1.图2,1,2uv(p,q)是在图2,1,2的u点上粘接星K1,p,且在v点上粘接星K1,q得到的图,且dK1,p(u)=p,dK1,q(v)=p.设n6是任意正整数,图3,1,2u(n5)是在图3,1,2的u点上粘接星K1,n5得到的图,且dK1,n5(u)=n5.近年来,对于图的距离谱研究受到了广泛关注.Indulal1给出了距离谱半径的一些下界,并刻画出达到这些界的极图;Ilic2证明了一种使距离谱半径减小的图变换,并在给定匹配数的n阶树中刻画了距离谱半径达到最小的极图;在有r个悬挂点的n阶连通图中,Bose等3刻画了距离谱半径的极小图;Lin等4刻画了最小距离特征值为2的所有连通图,并给出了只有三个不同距离特征值且距离谱半径不是整数的所有直径为2的连通图;在有完美匹配的单圈图中,Zhang5确定了距离谱半径分别达到最大和最小的极图;Li6刻画出了最小距离特征值在区间(1+17)/2,1)1,12)的所有连通图,其中是x3x23x+1=0的最小根,并证明了最小距离特征值大于等于(1+17)/2的连通图是由它们的距离谱确定的.相对图的距离谱研究,图的补图的距离谱研究很少.在n阶树的补图中,Lin等7刻画了距离谱半径分别达到最大和最小的极图,并且刻画了最小距离特征值分别达到最大和最小的极图;Qin等8在n阶单圈图的补图中刻画了距离谱半径达到最大的极图,且给出了直径为3的单圈图的补图的最小距离特征值达到最大的极图.本文主要研究n阶双圈图的补图的距离矩阵,在Bn中不考虑图D3,0,3,D3,0,3u(n5),2,1,2,2,2,2和2,1,2u(n4).设G是一个n阶连通图且Gc连通,若diam(G)4,则D(Gc)=JnIn+A(G),否则D(Gc)JnIn+A(G).令S=G|GBn,n7,diam(G)=3且D(Gc)JnIn+A(G),则S中共有21类图,见图1.图 1S 中的 21 类图186新疆大学学报（自然科学版）（中英文）2023年1预备知识引 理19若M是n阶非负不可约矩阵且n2,那么以下命题成立:（1）矩阵M的谱半径(M)0且(M)是矩阵M的单根;（2）矩阵M有属于特征值(M)的正特征向量;（3）矩阵M的所有非负特征向量都属于特征值(M).引 理210设M=(mij)是一个n阶非负矩阵,(M)是距阵M的谱半径,Ri(M)表示矩阵M第i行的行和.则minRi(M)|1in(M)maxRi(M)|1in.如果M是不可约矩阵,那么等号成立当且仅当R1(M)=R2(M)=Rn(M).在本节中,将给出两种图变换来帮助完成本文.引 理38(图变换1)设图G是一个连通图,uv是图G的一条非悬挂割边.设图G1是通过收缩图G的边uv为一点u并使点u与点v连接成悬挂边得到的图,如图2所示,则(Gc1)(Gc).图 2图 G 和图 G1引 理4(图变换2)设图GBnS且n7,点u,v是图G圈上的两点.设X是属于(Gc)的Perron向量.设S1=vi|i=1,2,sNG(v)NGu.若S1=,构造图G1=G1isvvi+1isuvi.若图Gc1是连通的且xuxv,则(Gc1)(Gc).证明注意到图G1仍然是双圈图以及D(Gc)=JnIn+A(G).若图Gc1连通,则D(Gc1)JnIn+A(G1).对任意z S1,有(Gc1)(Gc)XTD(Gc1)XXTD(Gc)XXTA(G1)XXTA(G)X=2(xuxv)zS1xz0,若(Gc1)=(Gc),则X也是属于(Gc1)的Perron向量.由点u的特征等式可得0=(Gc1)xu(Gc)xu=(D(Gc1)D(Gc)X)u(A(G1)A(G)X)u=zS1xz0,产生矛盾.因此,当xuxv时,(Gc1)(Gc).2主要结果引 理5设图G Dn(DnS),X是属于(Gc)的Perron向量.对于任意的正整数n 7,必然存在Gn,若图Gc是连通图,则(Gc)(Gc).第2期李远菁，等：双圈图补图的距离谱半径187证明设Ch,Ck是图G中分别包含点u,v的两个点不相交的圈,Pl+1是连接u,v的路.设u V(Ch),vV(Ck)且u=u,v=v,uNCh(u)u和vNCk(v)v.若xuxv,则将Ck上的边vv去掉,并添加新边uv,可得新图G1n.由引理4可知(Gc1)(Gc).若xu(Gc).因此,必然存在图Gn,使得(Gc)(Gc).引 理6设图Gn(nS).对于任意的正整数n7,必然存在图GS,使得(Gc)(Gc).证明设图G中连接u,v的三条内部点不相交的路为Ph+1=uu1uh1v,Pk+1=uu1uk1v和Pl+1=uu1ul1v.不失一般性,假设hkl1,k2.情形1 h=k=2,l=1.(1)假设u,v,u1,u1中只有一个点粘有悬挂树T.若u V(T)或v V(T).不妨设uV(T),因为图Gn(nS),所以T不是星和双星.对T的非悬挂割边反复进行图变换1,最终可得图2,1,2u(p,q)S.由引理3可知(c2,1,2u(p,q)(Gc).若u1 V(T)或u1 V(T).不妨设u1 V(T),因为图G n(nS),所以T非星.对T的非悬挂割边反复进行图变换1,最终可得图2,1,2u1(n4)S.由引理3可知(c2,1,2u1(n4)(Gc).(2)假设u,v,u1,u1中至少有两个点粘有悬挂树.若图G中存在非星悬挂树,则对悬挂树的非悬挂割边反复进行图变换1,可将悬挂树变换成星,得到的新图记为G1.由引理3可知(Gc1)(Gc).若图G1 S,则结论成立.否则,若图G1上的点u,v都粘有悬挂星,通过比较点u,v对应于(Gc1)的Perron向量中分量的大小,运用图变换2,将分量较小的点连接的悬挂边去掉并使分量较大的点与这些悬挂点相邻,记此时的图为G2.由引理4可知(Gc2)(Gc1).若图G2 S,则结论成立.否则,图G2上的点u,u1都粘有悬挂星,通过比较点u,u1对应于(Gc2)的Perron向量中分量的大小,运用图变换2,可得图2,1,2uu1(p,q)S或图2,1,2u1u1(p,q)/S.由引理4可知(c2,1,2uu1(p,q)(Gc2)和(c2,1,2u1u1(p,q)(Gc2).对图2,1,2u1u1(p,q)上的点u1,u1运用图变换2,通过比较点u1,u1对应于(c2,1,2u1u1(p,q)的Perron向量中分量的大小,可得图2,1,2u1(n4)S.由引理4可知(c2,1,2u1(n4)(c2,1,2u1u1(p,q).综上可知结论成立.若图G1上的点u,v只有一个点粘有悬挂星,不妨假设点u,u1都粘有悬挂星,对点u,u1运用图变换2,最终可得图2,1,2u1(n4)S或图2,1,2uu1(p,q)S.由引理4可知(c2,1,2u1(n4)(Gc1)和(c2,1,2uu1(p,q)(Gc1).结论仍然成立.若图G1上的点u,v都不粘有悬挂星,则图G1=2,1,2u1u1(p,q).由上面分析可得结论仍然成立.情形2 h=k=l=2.(1)假设u,u1,u1,u1,v中只有一个点粘有悬挂树T.因为图Gn(nS),所以T非星.对T的非悬挂割边反复进行图变换1,最终可得图2,2,2u(n5)S或图2,2,2u1(n5)S.由引理3可知(c2,2,2u(n5)(Gc)和(c2,2,2u1(n5)(Gc),结论成立.(2)假设u,u1,u1,u1,v中至少有两个点粘有悬挂树.对图G进行与情形1中(2)类似的图变换,最终可得图2,2,2u(n5)S或图2,2,2u1(n5)S或图2,2,2uu1(p,q)S.由引理4可知结论成立.情形3 h=3,k=2,l=1.(1)假设u,v,u1,u2,u1中只有一个点粘有悬挂树T.若T是星,因为图Gn(nS),显然图G=3,1,2u1(n5).对图3,1,2u1(n5)圈上的任意两点运用图变换2,通过比较这两点对应于(c3,1,2u1(n5)的Perron向量中分量的大小,将分量较小的点连接的邻边去掉并使分量较大的点与这些邻点相连,可得图3,1,2u(n5)S或图2,1,2uu1(p,q)S或图D3,0,3u1(n5)S或图2,1,2u1u1(n5,1)/S(由情形1可知(c2,1,2u1(n4)(c2,1,2u1u1(n5,1).由引理4可知结论成立.若T非星,对T的非悬挂割边反复进行图变换1,最终可得图3,1,2u(n5)S或图3,1,2u1(n5)S或图3,1,2u1(n5)/S.由引理3可知结论成立.(2)假设u,v,u1,u2,u1中至少有两个点粘有悬挂树.对图G进行与情形1中(2)类似的图变换,最终可得图3,1,2u(n5)S或图3,1,2u1(n5)S或图3,1,2uu1(p,q)S或图3,1,2uv(p,q)S或图3,1,2u1(n5)/S(1)中的图).由引理4可知结论成立.情形4 h=k=3,l=1.(1)假设u,v,u1,u2,u1,u2中只有一个点粘有悬挂树T.若T是星,因为图Gn(nS),显然图G=3,1,3u1(n6).对图3,1,3u1(n6)圈上的任意两点运用图变换2,通过比较这两点对应于(c3,1,3u1(n6)的Perron向量中分量的大小,将分量较小的点连接的邻边去掉并使分量较大的点与这些邻点相连,可得图D3,0,3uu1(p,q)S或图3,1,2u(n5)S或图3,1,3u(n6)S或图2,2,2uu1(p,q)S或图3,1,2u1(n5)S或图3,1,2uu1(p,q)S或图3,1,2u1(n5)/S(情形3中的图)或图3,1,2uu2(p,q)/S(情形3中的图)或图3,1,2uu1(p,q)/S(情形3中的图)或图2,2,2u1u1(p,q)/S(情形2中的图)或图3,1,2u1u1(p,q)/S(情形3中的图).由情形2和3的分析可知结论成立.若T非星,对T的非悬挂割边反复进行图变换1,最终可得188新疆大学学报（自然科学版）（中英文）2023年图3,1,3u(n6)S或图3,1,3u1(n6)/S.由引理3可知结论成立.(2)假设u,v,u1,u2,u1,u2中至少有两个点粘有悬挂树.对图G进行与情形1中(2)类似的图变换,最终可得图3,1,3u(n6)S或图3,1,3uv(p,q)S或图3,1,3u1(n6)/S(1)中的图).由引理4可知结论成立.情形5 h4,k 2,l=1.对图G圈上的任意两点运用图变换2,通过比较这两点对应于(Gc)的Perron向量中分量的大小,将分量较小的点连接的邻边去掉并使分量较大的点与这些邻点相连,不断进行上述的图变换,最终可得图G3 2,1,2(情形1中的图)或图G4 2,2,2(情形2中的图)或图G5 3,1,2(情形3中的图)或图G63,1,3(情形4中的图).由引理4可知结论成立.情形6 h 3,k 2,l=2.不断对图G进行与情形5类似的图变换,最终可得图G7 2,1,2(情形1中的图)或图G82,2,2(情形2中的图)或图G93,1,2(情形3中的图)或图G103,1,3(情形4中的图).由引理4可知结论成立.情形7 hkl3.不断对图G进行与情形5类似的图变换,最终可得图G112,1,2(情形1中的图)或图G12 2,2,2(情形2中的图)或图G13 3,1,2(情形3中的图)或图G14 3,1,3(情形4中的图).由引理4可知结论成立.综上所述,必然存在图GS,使得(Gc)(Gc).引 理7对于任意正整数n6,p,q.则(c2,1,2uv(p,q)(c2,1,2u(p,q).证明令S2=N2,1,2u(p,q)(u)u.设X是属于(c2,1,2u(p,q)的Perron向量,若xvxu,则(c2,1,2uv(p,q)(c2,1,2u(p,q)XTD(c2,1,2uv(p,q)XXTD(c2,1,2u(p,q)X=2xvzS2xz+2xvxu2xuzS2xz2xuxu=2(xvxu)(zS2xz+xu)0,若(c2,1,2uv(p,q)=(c2,1,2u(p,q),则X也是属于特征值(c2,1,2uv(p,q)的Perron向量.由点v的特征等式可得0=(c2,1,2uv(p,q)xv(c2,1,2u(p,q)xv=(D(c2,1,2uv(p,q)D(c2,1,2u(p,q)X)v=zS2xz+xu0,产生矛盾.因此,当xv xu时,(c2,1,2uv(p,q)(c2,1,2u(p,q).当xv(c2,1,2u(p,q).引 理8对于任意正整数n,p,q,其中n6且p+q=n4.则(c2,1,2uv(n5,1)(c2,1,2uv(p,q),等号成立当且仅当q=1.证明设X是属于(c2,1,2uv(p,q)的Perron向量,不失一般性,设xuxv.令wN2,1,2uv(p,q)(v)u,u1,u1且S3=N2,1,2uv(p,q)(v)u,u1,u1,w.若q=1,则(c2,1,2uv(n5,1)(c2,1,2uv(p,q)XTD(c2,1,2uv(n5,1)XXTD(c2,1,2uv(p,q)X=2(xuxv)zS3xz0,若(c2,1,2uv(n5,1)=(c2,1,2uv(p,q),则X也是属于特征值(c2,1,2uv(n5,1)的Perron向量.由点u的特第2期李远菁，等：双圈图补图的距离谱半径189征等式可得0=(c2,1,2uv(n5,1)xu(c2,1,2uv(p,q)xu=(D(c2,1,2uv(n5,1)D(c2,1,2uv(p,q)X)u=zS3xz0,产生矛盾.因此,(c2,1,2uv(n5,1)(c2,1,2uv(p,q),等号成立当且仅当q=1.注1设n8,p,q为任意正整数,与引理7和引理8的方法类似,可得(Dc3,1,3u(n6)(Dc3,1,3uv(p,q),(c3,1,2u(n5)(c3,1,2uv(p,q),(c3,1,3u(n6)(c3,1,3uv(p,q),min(Dc3,0,3uu1(n6,1),(Dc3,0,3u1(n5)(Dc3,0,3uu1(p,q),min(Dc3,0,4u(n6),(Dc3,0,4u1(n6)(Dc3,0,4uu1(p,q),min(c2,1,2uu1(n5,1),(c2,1,2u1(n4)(c2,1,2uu1(p,q),min(c3,1,2u(n5),(c3,1,2u1(n5)(c3,1,2uu1(p,q),min(c2,2,2u(n5),(c2,2,2u1(n5)(c2,2,2uu1(p,q).定理1设图GBn且n8.若图Gc连通,则(c2,2,2u(n5)(Gc),等号成立当且仅当G=2,2,2u(n5).证明由引理5和6可知,要确定Bcn中距离谱半径达到最大的极图只需要考虑S中的图的补图.由引理7,引理8和 注1可知只需要考虑以下几类图:Dc3,0,3uu1(n6,1),Dc3,0,3u1(n5),Dc3,0,4u(n6),Dc3,0,4u1(n6),Dc3,1,3u(n6),c2,1,2u1(n4),c2,1,2uv(n5,1),c2,1,2uu1(n5,1),c3,1,2u(n5),c3,1,2u1(n5),c2,2,2u(n5),c2,2,2u1(n5)以及c3,1,3u(n6).它们对应的距离特征多项式如下:PDc3,0,3uu1(n6,1)()=(+1)n7(+2)1(),PDc3,0,3u1(n5)()=(+1)n6(+2)2(),PDc3,0,4u(n6)()=(+1)n6(+2)3(),PDc3,0,4u1(n6)()=(+1)n7(+2)4(),PDc3,1,3u(n6)()=(+1)n7(+2)25(),Pc2,1,2u1(n4)()=(+1)n5(+2)6(),Pc2,1,2uv(n5,1)()=(+1)n57(),Pc2,1,2uu1(n5,1)()=(+1)n68(),Pc3,1,2u(n5)()=(+1)n69(),Pc3,1,2u1(n5)()=(+1)n610(),Pc2,2,2u(n5)()=(+1)n411(),Pc2,2,2u1(n5)()=(+1)n412(),Pc3,1,3u(n6)()=(+1)n7(+2)13(),190新疆大学学报（自然科学版）（中英文）2023年其中1()=6+(n+5)5+(7n+3)4(11n+41)3(n+89)2+(3n37)+6,2()=5+(n+4)4(6n+1)3(3n+52)2+(11n91)+4n18,3()=5+(n+4)4(6n+6)3(4n+46)2+(3n43)+6,4()=6+(n+5)5+(7n+3)4+(577n)3+(157+13n)2+(101+15n)+6,5()=5+(n+3)4(3+5n)3+(n39)2+(6n28)+12,6()=4+(3n)3+(95n)2+(53+n)+6n46,7()=5+(n+5)4+(7n+2)3(10n+52)2+(4n124)+6n64,8()=6+(n+6)5+(8n+7)4(17n+44)3(6n+152)2+(8n146)+3n35,9()=6+(n+6)5+(28n)4(16n+64)3(5n+169)2+(8n148)+3n35,10()=6+(n+6)5+(78n)4+(4615n)3+(175+5n)2+(204+26n)+12n72,11()=4+(4n)3+(126n)2+(642n)+6n64,12()=4+(4n)3+(76n)2+(58n)+8n68,13()=5+(n+5)4+(7n+3)3+(9n41)2+(4n106)+6n60.断言1(c2,2,2u(n5)(c2,1,2u1(n4).设Pc2,2,2u(n5)()Pc2,1,2u1(n4)()=(+1)n5f1(),其中f1()=53+(n5)2+(4n+24)6n+28,f1()=152+(2n10)4n+24,f1()=30+2n10.令1=(c2,1,2u1(n4).由于D(c2,1,2u1(n4)的最小行和不小于n,由引理2可得1n.当n时,f1()f1(n)=28n100,即f1()随严格单调递减.由f1()的单调性可知,f1()f1(n)=13n214n+240,即f1()随严格单调递减.由f1()的单调性可知,f1()f1(n)=4n39n2+18n+280.因此,f1(1)0.Pc2,2,2u(n5)(1)(c2,1,2u1(n4).断言2(c2,1,2u1(n4)(c3,1,2u(n5).设Pc2,1,2u1(n4)()Pc3,1,2u(n5)()=(+1)n6f2(),其中f2()=103+(4n54)2+(12n96)+9n57,f2()=302+(8n108)+12n96,f2()=60+8n108.令2=(c3,1,2u(n5).由于D(c3,1,2u(n5)的最小行和不小于n,由引理2可得2n.当n时,f2()f2(n)=52n1080,即f2()随严格单调递减.由f2()的单调性可知,f2()f2(n)=22n296n90,即f2()随严格单调递减.由f2()的单调性可知,f2()f2(n)=6n3 42n2 87n 57 0.因此,Pc2,1,2u1(n4)(2)Pc3,1,2u(n5)(2)0,即Pc2,1,2u1(n4)(2)(c3,1,2u(n5).与断言1和断言2的方法类似,通过不断比较最终可得(c2,2,2u(n5)(Gc),等号成立当且仅当G=2,2,2u(n5).定 理2设图GBn且图Gc连通.对于任意正整数n5,有以下命题成立:（1）当n=5时,(Gc)(c3,1,2),等号成立当且仅当G=3,1,2;（2）当n6时,(Gc)(c2,2,2u(n5),等号成立当且仅当G=2,2,2u(n5).(下转第221页)第2期王喜敏，等：基于混合算法的多机器人协作任务均衡规划研究22115XU X,CHEN H L.Adaptive computational chemotaxis based on field in bacterial foraging optimizationJ.Soft Computing,2014,18(4):797-807.16NAKAGAKI T,YAMADA H,TOTHA.Maze-solving by an amoeboid organismJ.Nature,2000,407(6803):470.17JOHANNSON A,ZOU J.A slime mold solver for linear programming problemsC/Conference on Computability in Europe.Cambridge:Springer,2012.18KE L.A brain storm optimization approach for the cumulative capacitated vehicle routing problemJ.Memetic Computing,2018,10(4):411-421.19李蒙蒙,秦伟,刘艺,等.结合头脑风暴优化的混合蚁群优化算法J.计算机应用,2021,41(8):2412-2417.20XUE Y,ZHANG Q,ZHAO Y.An improved brain storm optimization algorithm with new solution generation strategies forclassificationJ.Engineering Applications of Artificial Intelligence,2022,110:104677.21南丽君,陈彦如,张宗成.改进的自适应大规模邻域搜索算法求解动态需求的混合车辆路径问题J.计算机应用研究,2021,38(10):2926-2934.22陈嘉朋,张宏立,王聪,等.改进狼群算法求解多目标柔性作业车间调度问题J.新疆大学学报(自然科学版)(中英文),2022,39(1):42-48+73.23WANG Y Z,CHEN Y,LIN Y.Memetic algorithm based on sequential variable neighborhood descent for the minmax multipletraveling salesman problemJ.Computers&Industrial Engineering,2017,106:105-122.24聂清彬,蔡婷,张莉萍,等.一种面向成本驱动的云资源调度策略研究J.新疆大学学报(自然科学版),2016,33(4):454-458.25岳倩宇.多机器人任务规划方法研究D.天津:天津大学,2018.26高平安,蔡自兴,余伶俐.多移动机器人负载均衡任务规划算法J.高技术通讯,2009,19(5):501-505.责任编辑：张自强(上接第190页)证明当n=5时,Bn=3,1,2,2,1,2u1(1),且(c3,1,2)=8.288 2,(c2,1,2u1(1)=7.459 3,命题(1)显然成立.当6 n 7时,在Bcn中通过MATLAB计算可得距离谱半径达到最大的极图是图c2,2,2u(n5).由定理1可知,当n8时,(c2,2,2u(n5)(Gc),等号成立当且仅当G=2,2,2u(n5),故命题(2)成立.参考文献：1INDULAL G.Sharp bounds on the distance spectral radius and the distance energy of graphsJ.Linear Algebra and its Appli-cations,2009,430(1):106-113.2ILIC A.Distance spectral radius of trees with given matching numberJ.Discrete Applied Mathematics,2010,158(16):1799-1806.3BOSE S S,NATH M,PAUL S.Distance spectral radius of graphs with r pendent verticesJ.Linear Algebra and its Applications,2011,435(11):2828-2836.4LIN H Q,HONG Y,WANG J F,et al.On the distance spectrum of graphsJ.Linear Algebra and its Applications,2013,439(6):1662-1669.5ZHANG X L.On the distance spectral radius of unicyclic graphs with perfect matchingsJ.Electronic Journal of Linear Algebra,2014,27:569-587.6LI D,MENG J X.The graphs with the least distance eigenvalue at least(1+17)/2J.Linear Algebra and its Applications,2016,493:358-380.7LIN H Q,DRURY S.The distance spectrum of complements of treesJ.Linear Algebra and its Applications,2017,530:185-201.8QIN R,LI D,CHEN Y Y,et al.The distance eigenvalues of the complements of unicyclic graphsJ.Linear Algebra and itsApplications,2020,598:49-67.9PILLAI S U,SUEL T,CHA S H.The Perron-Frobenius theorem:some of its applicationsJ.IEEE Signal Processing Magazine,2005,22(2):62-75.10HORN R A,JOHNSON C R.Matrix analysisM.Cambridge:Cambridge University Press,1985.责任编辑：赵新科