关于树的谱半径与最大度.ppt

关于树的谱半径与最大度,林文水郭晓峰厦门大学数学科学学院linwensh2006-07-18于南开大学,内容提要,图谱理论简介符号说明图的谱半径与最大度的关系树的谱半径与最大度的关系完美匹配树的谱半径与最大度的关系一个问题参考文献,图谱理论简介,图谱理论建立于20世纪五、六十年代，是图论的重要分支。主要结果可参见专著1-3。早期主要研究图的谱与结构之间的关系。图谱理论在量子化学上应用，Hckel分子轨道理论实际上就是分子图的谱理论。,符号说明,表示图,的邻接矩阵,对称，故特征根为实数。,称为,分别表示,的最大特征值，也称为,的谱半径。,阶树的集合和,和,阶具有完,美匹配的树的集合。令,，,图的谱半径与最大度的关系,(见1),Godsil,4若,为树，则,Simietal.,5确定了,具有最大谱,半径的树。,树的谱半径与最大度,林，郭，6在,中，,具有最小的谱半径。,林，郭，6在,中，,具有最大的谱半径，,其中,。,如图所示。,和,树的谱半径与最大度,其中,。,林，郭，6令,为,中的树，则,即当,时，,中的树的谱半径随其最大度,的增大而增大。,树的谱半径与最大度,，,但,。,界,是最好可能的。如当,时，下图中,完美匹配树的谱半径与最大度,林，郭，7在,中，,具有最小的谱半径。,林，郭，7在,中，,具有最大的谱半径，,。,如图所示。,和,完美匹配树在化学上代表无圈Kekulean共轭碳氢化合物分子，,故更具有研究意义。(见8,9),完美匹配树的谱半径与最大度,林，郭，7令,为,中的树，则,其中,即当,中的树的谱半径随其最大度,的增大而增大。,时，,完美匹配树的谱半径与最大度,界,是最好可能的。如当,时，,，,但,，,。,一个问题,令,为具有,个顶点,条边的连通二部图,和,的集合或其子集。令,为,中的两个图，,是否存在常数,（只依赖于,），,或,或,，使得当,时,？,参考文献,1D.Cvetkovi,M.Doob,H.Sachs,SpectraofGraphs-Theoryandapplications(Thirdedition),JohannAmbrosiusBarthVerlag,1995.2D.Cvetkovi,P.Rowlinson,S.Simic,Eigenspacesofgraphs,CambridgeUniversityPress,Cambridge,1997.3A.J.Schwenk,R.J.Wilsion,Ontheeigenvaluesofagraph,in:L.W.Beineke,R.J.Wilson(Eds.),SelectedTopicsinGraphTheory,AcademicPress,NewYork,1978,pp.307-336.4C.D.Godsil,Spectraoftrees,AnnalsofDiscreteMathematics,20(1984)151-159.5S.K.Simi,D.V.Toi,Theindexoftreeswithspecifiedmaximumdegree,MATCHCommun.Math.Comput.Chem.,54(2005)351-362.,参考文献,6W.S.Lin,X.F.Guo,Orderingtreesbytheirlargesteigenvalues,LinearAlgebraAppl.(inpress).7W.S.Lin,X.F.Guo,Onthelargesteigenvaluesoftreeswithperfectmatchings,JournalofMath.Chem.(inpress).8A.Graovac,I.Gutman,N.Trinajsti,Topologicalapprochtothechemistryofconjugatedmolecules,Springer,Berlin,1977.9D.Rouvary,in:A.T.Balaban(E