图的谱及相关拓扑指数的极图刻画

Graph spectra and topological indices are attractive invariants in graph theory, which found wide applications in many fields, such as physics, chemistry, biological science, information science. The study of these invariants has become a hot topic in recent decades. For their theoretic and practical applications, one elementary problem is to extract their properties and characterize the extremal graphs. With the present project, aided by mass computer search we plan to (1) study the properties and the problem of characterization of extremal graphs with respect to spectra and some relational topological indices, including adjacent spectra, (signless) Laplacian spectra, distance spectra, Harary spectra, (Laplacian) energy, Laplacian-energy-like invariants, ABC index, Kirchhoff index, Wiener number, Zagreb index, Estrada index, and so on, (2) find some unified approaches to studying their properties and characterizing the extremal graphs, (3) develop efficient and fairly universalizable software for extremal graph search, and (4) publish 8+ SCI indexed papers. The expected achievements will have significant theoretic and practical values.

图的谱和拓扑指数是图论中备受关注的不变量，且在物理、化学、生命科学、信息科学等领域有着广泛的应用，是近几十年来的研究热点。性质研究和极图刻画是这些不变量的理论和应用研究的重要问题。本项目拟结合大规模计算机搜索，（1）研究图的谱及相关拓扑指数的性质和极图刻画，包括邻接谱、（无符号）拉普拉斯谱、距离谱、Harary谱，以及能量、（类）拉普拉斯能量、ABC指数、Kirchhoff指数、Wiener指数、Zagreb指数、Estrada指数等，（2）发现不变量性质研究和极图刻画的通用方法，（3）开发高效且具有一定通用性的极图搜索软件，（4）完成相关SCI学术论文8篇以上。预期成果将具有重要的理论意义和应用价值。

项目的研究内容包括：1.研究图的谱及相关拓扑指数的性质和极图刻画；2.发现不变量性质研究和极图刻画的通用方法；3.开发高效且具有一定通用性的极图搜索软件；4.互联网络的容错性研究。.主要的研究成果有：1.开发了一套极图搜索软件，实现了对若干不变量极图迄今最高效的搜索。 2.（部分）刻画了若干不变量极图，包括：极小ABC指数树、ISI指数极大树、给定匹配数的Harary谱半径极大图等的部分刻画；AZI极大树、ISI极大化学树的完全刻画，给出具有较大ABC谱半径的前5个树。3.确定了Möbius和柱状八角链的Kirchhoff指数。4.定义了图的一种新的交运算，给出某些特殊交图的谱性质，构造了无穷多的关于邻接谱或（无符号）拉普拉斯谱的同谱图对。5.针对（折叠）立方体网络，给出一个统一的容错性研究方法。项目已发表学术论文23篇，其中SCI索引18篇，解决了两个公开问题。.项目的研究成果丰富了图谱理论和极值图论，证实：重复“搜索－猜想－证明”过程的研究路线可行、有效。此外，我们建立了ABC谱研究的基础工具，并初步搜索了ABC谱确定图。前期研究成果表明，ABC谱对图可能具有更强的识别能力，这为图谱确定问题的进一步研究指明了新的方向。