链图的距离特征值.pdf

2024年3 月Mar.,2024DOI:10.15960/ki.issn.1007-6093.2024.01.009这筹学学报(中英文)Operations Research Transactions第2 8 卷第1 期Vol.28.No.1链图的距离特征值吕雪征1马梦郁1,t摘要，如果一个图G不包含2 K2，C3 及Cs作为导出子图，称其为链图。在所有点数和边数给定的连通二部图中，链图具有最大的谱半径，这使得链图在图谱理论中占有一席之地。本文研究了连通链图距离特征值的分布情况。对于点数为n的连通链图G=G(t，,t h;S1,s h)，我们证明了-2 是G的重数为n2 h 的距离特征值，且G有h1 个距离特征值小于2 和h1 个距离特征值大于2。关键词链图，距离特征值，合理划分中图分类号0 2 2 1.22010 数学分类号90 C47,90C26,90C30The distance spectra of chain graphs*LYU XuezhenglAbstract A graph is called a chain graph if it does not contain induced 2K2,C3or Cs.In spectral graph theory,chain graphs feature as graphs whose largest eigenvaluewithin the connected bipartite graphs of fixed order and size is maximal.In this paper,we consider the distance eigenvalues of a connected chain graph G.We present that-2is an eigenvalue of G=G(ti,.,th;$1,.,sh),with multiplicity n-2h.And furthermore,there are exactly h-1 eigenvalues less than-2 and exactly h+1 eigenvaluesgreater than-2.Keywords chain graphs,distance spectrum,equitable partitionChinese Library Classification O221.22010 Mathematics Subject Classification 90C47,90C26,90C30设是一个顶点集为=u 1,U 2,，U n】的连通图。顶点u；和u;之间的距离用d(ui,s）来表示（或记作 di,s)。点u的邻域是所有与点u;相邻的点的集合，记作 N(V),即N(V)=ujld(ui,ui）=1)。图G的距离矩阵记作D(G),D(G)是一个nn矩阵，其(i,i)-元是d(ui,us）（1 i,i n)。我们称距离矩阵D(G)的特征值为图 G 的距离特征值,用1 Q2On来表示D(G)的n个特征值。关于距离矩阵的背景及更多应用的内容可参考文献1 。Aouchiche 等2 给出了图的距离矩阵及其谱性质的一些结果。关于综述图的距离特征值研究的新进展可见文献3 。MA Mengyul,t收稿日期：2 0 2 0-1 2-2 5*基金项目：国家自然科学基金（No.11971479)1.中国人民大学数学学院，北京 1 0 0 8 7 2;School of Mathematics,Renmin University of China,Beijing100872,China+通信作者E-mail:1期1简介如果一个图不包含2 K2，C3 及Cs作为其导出子图，我们称之为链图。我们首先引用文献4 中的内容，介绍连通链图的构造并给出本文需要用到的一些符号。任何一个连通链图G的顶点集都可以分为不相交的两部分，每一部分又可以被分为h个不相交的非空子集合Ui,Un和Vi,Vh，其中U,V(i=1,h)均为独立点集且U;(i=1,h)中的所有质点均与集谷U中的所有质点相邻因此如果EUu（或u E Vh+1,u e V),则 Nc(u)C Nc(u)(NG(u)C Nc(u)。记 ti=IUil,si=IVl,i=1,h，则链图G可表示为G(t1,，t h;S1,，s h)。图1 展示了一个链图的示意图。有关链图的更多内容，可参阅最近的论文3，5 和其中引用的参考文献。2008年，Bell等5 发现在所有点数和边数给定的连通二部图中，链图的邻接矩阵（或拉普拉斯矩阵，无符号拉普拉斯矩阵）的谱半径是最大的。链图的这个重要性质使得它在图谱理论中占有重要的地位，而在文献4 中，链图有另外一个名字：双嵌套图（DoubleNested Graph)，简称DNG。链图在现实生活中具有广泛的应用，比如生态网络中考虑的就是具有嵌套性质的图；链图还可应用于某些经济网络模型中（详细内容可参阅文献6 )。2016年，Alazemi 等7 研究了链图的邻接矩阵的特征值分布，他们证明了链图的邻接矩阵在【-，0）和（0,寻】中没有特征值，这也就表明任何链图的最小正特征值都大于号。2 0 2 0 年，Alazemi 和Das等1 8 研究了链图的能量和拉普拉斯能量，他们找出了链图能量的一些上界和下界以及拉普拉斯能量的下界，并且证明了在所有n阶连通链图中，星图具有最小能量，同时也确定了在所有n条边的n阶链图中具有最大拉普拉斯能量的链图。阈值图（threshold graph）不包含2 K2,C2及C4作为其导出子图,Lu等9 刻画了阈值图的距离特征值的分布,Lou 等1 0 给出了所有具有不同特征值的阈值图并确定了阈值图的HOMO-LUMO指数。在本文中，我们研究了连通链图的距离特征值，证明了-2 是其重数为n2 h 的距离特征值，而且G恰有 h1 个距离特征值小于-2,而有 h+1个距离特征值大于一2。2连通链图的距离特征值为了刻画连通链图的距离特征值的分布，我们首先给出要用到的一些概念和引理。2.1合理划分矩阵的合理划分有非常丰富的内容，也是图谱理论中一个非常有用的工具1 1 。假设A是一个nn 的实对称矩阵，其行指标和列指标集合用X=1,n)来表示。设链图的距离特征值ti=UiGIVil=81t2=|U2lIV2/=82th-1=|Uh-1lCIVh-1l=Si-1th=IUlOIVil=Sh图1 G(ti,th;s1,sh)113114I：X=XiU.UXh 是X的一个划分。此时矩阵A可以写为其中Ai,，是由A的X；行和X,列导出的子矩阵（1 i,h)。用 bi,j表示子矩阵Ai.的行和的平均值，则称Bh=（b i.3）h x h 是矩阵A在划分下的商矩阵。如果每一个子块Ai,的行和都是常数，则称这个划分是一个合理划分。下面介绍的关于合理划分的商矩阵的有关结论在我们的证明中将发挥十分重要的作用。引理1（1 2 ，Theorem9.1.1）设A是一个实对称矩阵，II是A的一个合理划分，A在I下的商矩阵为Bh，那么商矩阵Bh的特征多项式能够整除A的特征多项式。设G 是一个n 阶连通链图,D 是G的距离矩阵,I:V=ViU.UVh 是G的顶点集的一个划分，用Di表示由D的V 行和V,列（1 i,jh）导出的子矩阵。那么对于任意的一点ueV,其在Di中所对应的行和是uevd(u,)。因此，如果对于任意的1i,jh,V,都有vevd(u,u)的值是一个与的选择无关的常数时，则划分I是 D 的一个合理划分。此时我们也称该划分 II 是一个G的距离合理划分。因此，利用引理1，我们可以得到以下关于距离矩阵的结果。推论 1 设 D(G)是连通图 G 的距离矩阵,II 是 D(G)的一个合理划分，且 D(G)在II下的商矩阵是Bh，那么Bh 的特征多项式能够整除 D(G)的特征多项式。2.2相关引理接下来的两个引理对后面结论的证明也十分重要，其中一个是著名的交错定理，其应用十分广泛，另一个引理有用则是因为链图的特殊结构。引理2(1 2 ,Theorem9.3.3)设M是一个nn 的埃尔米特矩阵，0 1(M)Q2(M).n(M)是M 的所有特征值；设H 是M 的一个mm的主子矩阵，ui(H)2(H)m(H）是H的所有特征值，那么H和M的特征值满足关系式：on-m+i(M）i(H);(M)(1im)。引理 3(1 3 ,Lemma 3.5)设G 是一个连通图,S V(G)且ISI=q。如果S 是一个独立集,且对任意的点u,ES都有 N(u)=N(u),那么-2 是G的距离特征值且重数至少是q-1。2.3主要结果现在我们开始研究连通链图。我们使用前面介绍的符号，假定G=G(t1,th;S1,.Sh）是一个连通链图，其中 si,t；1（1 i,j h,h 1)，并记t=ti+th，s=S1+Sh，因此G包含s+t个顶点。由链图的特殊结构可得图G的一个很自然的划分：II:V(G)=U i U Vh U U 2 U Vh-1 U.U U h U Vi。接下来我们将证明I是G的一个距离合理划分。注意到图G的直径不超过3，根据 G的结构，对uEU；且u,我们有：吕雪征，马梦郁A1,1A1,hA=.Ah,1.Ahh(2,aEUk,1kh,d(u,a)=1,EVh,i+kh+1,(3,EVh,i+kh+2,28卷1期从而有d(u,2)=2(tj-1),i=j,aEUj2tj，显然这些值均与u的选取无关。类似地，对V且,我们有：d(u,ac)=从而有i+ih+1,2d(0,2)=ti，il3tj,i+jh+2,aEU;显然这些值也均与的选取无关。这也就表明I是G的一个距离合理划分，且 D(G)在此划分下的商矩阵为如下矩阵Bh。2(t1-1)t12t1Bh=t12t1t1由推论1 可知，Bh 的所有特征值都是G的距离特征值，所以我们会重点分析Bh的特征值的分布情况。我们先证明下面两个结论。引理42 是图G的一个距离特征值，且其重数至少是n2 h。证明注意到顶点集合U和V,中分别有t，s；（1 i j h)个独立点，而且对于任意的u,Ui,p,qV,我们有 N(u)=N(),N(p)=N(q)。根据引理3,U,的存在说明-2 是G的重数至少是t;-1的距离特征值，V,的存在说明-2 是G的重数至少是sj二1 的距离特征值。设U;=ui1,ui2,ut,V,=(uj1,j2,ig(1ijh)。下面我们说明由任意U，或V,导出的属于特征值2 的特征向量都是线性无关的。对2 0,入1+入2=2($1+t1)0,其中入1入2为B1+212的特征值。显然入1 0 并且入0。这也就表明B1的特征值都大于-2,结论显然成立。假设结论对h=（k 1)成立。假定k+1+22k为B+212k的特征值。由归纳假设可知，我们有+10且h+20 且 0 k+2 入h+4 入h+5.入2 k+2。吕雪征，马梦郁0-2Sh00-2sh-1000000028h-1000-2Sh-10000000000028卷00002t3000t3002t300000000000-282002th00-351282th00000000-2S2002th00-351000000002100000001期再由引理7 可得,(-h+1)(+-2k)=det(Bk+212k)=3(-4)-t.thS1 Sh,(1.+1)+2+3(+4 2+2)=det(B+1+2(+1)=3(-4)*+1 +1$+1,两个行列式的值正负号相反，且除了入+2 和入k+3之外，Bk+1+212(h+1）的其他特征值的乘积与Bk+2I2k的所有特征值的乘积同号，这表明入h+2一定与入+3 有相反的正负性。因此一定有入+2 0,入+3 0，即Bk+1恰有个特征值小于-2，分别是入k+3-2,.,入2 k+2-2。综上，结论得证。根据定理1和引理8，我们可以得到如下关于连通链图的距离特征值的分布结论。定理设G(t1,th;S1,Sh）是一个n 阶连通链图，那么-2 是的重数为n2 h 的距离特征值，而且G的其他2 h个距离特征值恰好有h1个小于-2，恰好有h+1个大于-2。3结语本文主要确定了连通链图的一个特殊距离特征值2 的重数，以及其他距离特征值以2 为标准的分布情况。我们未能确定除一2 以外其他距离特征值的重数，但是根据计算的一些连通链图的距离特征值（(n=5,6,7,8）具体参见表1)，猜想除-2 以外的其他距离特征值都是单根。对于给定阶数的连通链图，我们关心的另外一个问题是：距离谱是否能唯一地确定对应的连通链图。阶数(t1,.,th;s1,.,Sh)5(1;4)5(1,2;1,1)5(2,1;1,1)6(1,1,1;1,1,1)6(2,1;1,2)6(2,2;1,1)6(3;3)7(1,1,1;1,1,2)7(2,1,1;1,1,1)7(2,2;1,2)7(4;3)8(4;4)8(2,2;2,2)链图的距离特征值表1部分n阶连通图的距离特征值距离谱6.61,-0.61,(-2)7.46,-0.51,-1.08,-2,-3.866.54,0,-1.05,-2,-3.489.26,0,-1,-1.09,-3.17,-48.57,0.36,-1,(-2),-3.93)8.90,0,-0.9,(-2),4(7,1,(-2)4)11.77,0,-0.85,-1.07,-2,-3.26,-4.5910.53,0.58,-0.77,-1.03,-2,-3.19,-4.1211.19,0.36,-0.85,(-2)3,-4.698.61,1.39,(-2)10,2,(-2)12.32,0.83,-0.32,(-2)4,-4.83119口参考文献1 Aouchiche M,Hansen P.Distance spectra of graphs:A survey J.Linear Algebra and ItsApplications,2014,458:301-384.1202 Aouchiche M,Hansen P.Distance spectra of graphs:A survey J.Linear Algebra and ItsApplications,2014,458:301-386.3 Lin H,Shu J,Xue J,et al.A survey on distance spectra of graphs J.Advances in Mathematics,2021,50:29-76.4 Andelic M,Andrade E,Cardoso D M,et al.Some new considerations about double nestedgraphs JJ.Linear Algebra and Its Applications,2015,483:323-341.5 Bell F K,Cvetkovic,Rowlinson P,et al.Graphs for which the least eigenvalue is minimal J.Linear Algebra and Its Applications,2008,429:2168-2179.6 Staniczenko P,Kopp J,Allesina S.The ghost of nestedness in ecological networks J.NatureCommunications,2013,4:1391.7 Alazemi A,Andelic M,Simic S K.Eigenvalue location for chain graphs J.Linear Algebraand Its Applications,2016,505:194-210.8 Das K C,Alazemi A,Andelic M.On energy and Laplacian energy of chain graphs J.DiscreteApplied Mathematics,2020,284:391-400.9 Lu L,Huang Q X,Lou Z Z.On the distance spectra of threshold graphs J.Linear Algebraand Its Applications,2018,553:223-237.1o Lou Z,Lin H.Distance eigenvalues of a cograph and their multiplicities J.Linear Algebraand Its Applications,2021,608:1-12.11 Brouwer A E,Haemers W H.Spectra of Graphs M.Heidelberg:Spinger,2012.12 Godsil C D,Royel G.Algebraic Graph Theory M.Berlin:Springer-Verlag,2001.13 Lu L,Huang Q X,Huang X Y.The graphs with exactly two distance eigenvalues differentfrom-1 and-3 J.Journal of Algebraic Combinatorics,2017,45:629-647.14 Bondy J A,Murty U S R.Graph Theory M.New York:Springer,2008.15 Konig M D,Tessone C J,Zenou Y.Nestedness in networks:A theoretical model and someapplications J.Theoretical Economics,2014,9:695-752.16 Lou Z Z,Wang J F,Huang Q X.On the eigenvalues distribution in threshold graphs J.Graphs and Combinatorics,2019,35:867-880.吕雪征，马梦郁28卷