关于图的谱刻画问题的研究

The theory of graph spectra mainly studies combinatorial properties of a graph through spectral characterization (the multiset of eigenvalues) of some matrices associated with the graph..The content of graph spectra theory is quite broad, and mainly includes two aspects. One is the spectral characterization of graphs, it involves estimating the eigenvalues, determining the distribution of the spectra, studying the relation between the spectra and the invariants (e.g. diameter, chromatic number, girth, connectivity, etc) of graphs; the other one is the problem of characterizing graphs through their spectra, where which graphs are determined by their spectra (DS problem for short) is one of the famous and difficult problems in this field. Gunthard and Primas first raised the question “which graphs are DS?” then van Dam and Haemers had published two survey papers which include many cospectral mates and give some necessary conditions about cospectral graphs. But the question is far from resolved. In this project, we will study the spectral characterizations of certain properties of graphs and certain structures of graphs, this project aims at enriching the database of DS graphs, and also aims at accumulating theoretical insight for the problem.

图谱理论主要是利用矩阵理论中的方法和技巧, 来研究与图相关的矩阵的谱（特征值及其重数）的性质进而用这些性质来反映图的一些组合性质. .图谱理论研究的内容相当广泛,主要包括两个方面, 一个方面是图的谱特征, 主要涉及确定图的谱及其分布,确定谱的性质, 谱与图的各种参数之间的关系等; 另一个方面是谱的图特征,主要是根据谱的性质刻画图等, 其中图的谱唯一性（又称图的谱确定）问题是其研究的重点. 图的谱唯一问题最早由Gunthard和Primas提出, 接着van Dam和Haemers发表了两篇综述文章对此问题进行了概括总结, 并给出了很多谱唯一确定的图及图同谱的必要条件. 但是“哪些图是由它的谱所唯一确定的”这个问题还远远没有解决. 本项目拟对具有一定特性及一定结构的图来研究这个问题, 本项目旨在进一步扩大及丰富谱唯一确定图的图类, 并为回答上述问题提供一些理论积累.