关于树的谱半径与最大度林文水 郭晓峰 厦门大学数学科学学院linwenshsina.com2006-07-18于南开大学内容提要n图谱理论简介n符号说明n图的谱半径与最大度的关系n树的谱半径与最大度的关系n完美匹配树的谱半径与最大度的关系n一个问题n参考文献图谱理论简介n图谱理论建立于20世纪五、六十年代，是图论的重要分支。主要结果可参见专著1-3。n早期主要研究图的谱与结构之间的关系。n图谱理论在量子化学上应用，Hckel 分子轨道理论实际上就是分子图的谱理论。符号说明 表示图的邻接矩阵对称，故特征根为实数。称为分别表示的最大特征值，也称为的谱半径。阶树的集合和和阶具有完美匹配的树的集合。令，图的谱半径与最大度的关系(见1)Godsil, 4 若为树，则 Simi et al., 5 确定了具有最大谱半径的树。树的谱半径与最大度林，郭，6 在中，具有最小的谱半径。 林，郭，6 在中，具有最大的谱半径， 其中 。 如图所示。 和 树的谱半径与最大度其中。林，郭，6 令为中的树，则即当时， 中的树的谱半径随其最大度的增大而增大。树的谱半径与最大度，但。界是最好可能的。如当时，下图中完美匹配树的谱半径与最大度林，郭，7 在中，具有最小的谱半径。 林，郭，7 在中，具有最大的谱半径， 。 如图所示。 和 完美匹配树在化学上代表无圈Kekulean共轭碳氢化合物分子，故更具有研究意义。(见8,9)完美匹配树的谱半径与最大度林，郭，7 令为中的树，则其中即当中的树的谱半径随其最大度的增大而增大。时，完美匹配树的谱半径与最大度界是最好可能的。如当时，但，。一个问题令为具有个顶点条边的连通二部图和的集合或其子集。令为 中的两个图， 是否存在常数 （只依赖于），或或，使得当时？参考文献n1 D. Cvetkovi, M. Doob, H. Sachs, Spectra of Graphs-Theory and applications (Third edition), Johann Ambrosius Barth Verlag, 1995. n2 D. Cvetkovi, P. Rowlinson, S. Simic, Eigenspaces of graphs, Cambridge University Press, Cambridge, 1997. n3 A. J. Schwenk, R. J. Wilsion, On the eigenvalues of a graph, in: L. W. Beineke, R. J. Wilson (Eds.), Selected Topics in Graph Theory, Academic Press, New York, 1978, pp. 307-336. n4 C. D. Godsil, Spectra of trees, Annals of Discrete Mathematics, 20 (1984) 151-159. n5 S. K. Simi, D. V. Toi, The index of trees with specified maximum degree, MATCH Commun. Math. Comput. Chem., 54 (2005) 351-362. 参考文献n6 W. S. Lin, X. F. Guo, Ordering trees by their largest eigenvalues, Linear Algebra Appl. (in press). n7 W. S. Lin, X. F. Guo, On the largest eigenvalues of trees with perfect matchings, Journal of Math. Chem. (in press).n8 A. Graovac, I. Gutman, N. Trinajsti, Topological approch to the chemistry of conjugated molecules, Springer, Berlin, 1977.n9 D. Rouvary, in: A.T. Balaban (Ed.), Chemical Applications of Graph Theory, Academic Press, New York, 1976 (Chapter 7). Thank you!