图谱及相关问题的研究

Spectral graph theory is the study of the eigenvalues of matrices associated with graphs. By finding the relation between eigenvalues and topological structure of graphs, we can analyze the structural properties of graphs by means of spectral method. .Based on the previous work and my research basis for many years, the project intends to study the relations between the spectra of graphs and various invariants of graphs, especially the relation between the extremal eigenvalue and the structure of graphs. Because there is a natural 1-1 correspondence between 2-lifts of graphs and signings of graphs, we study the properties of spectra of signed graphs, including the relation between the spectral radius of signed graphs and the signing function and how to apply switching operation to solve the eigenvalues of signed graphs. We are focused on the spectral radius of signing of some underlying graph and see how small it can be and its relation with the structure of the underlying graph. We study the spectral properties of hypergraphs, such as how to analyze the expansion of hypergraphs in terms of the second eigenvalue of regular hypergraphs. We study the relation between the eigenvalues of hypergraph and those of its covering hypergraph, especially the relation between the second eigenvalue of regular hypergraph and the spectral radius of its universal cover. Mainly we are interested in the relation between the spectra of hypergraph and the structural properties of hypergraph. We shall investigate the extremal problem of matching energy in some classes of graphs and explore the bound on the gap between matching energy and energy of graphs.

谱图理论主要研究图关联的矩阵的谱，建立图的拓扑结构与图的特征值之间的联系，应用谱方法来研究图的拓扑结构性质。.基于前人的工作和本人多年的研究基础，本项目拟研究图的特征值与图的各种不变量之间的联系，重点关注图的极特征值与图的结构之间的关系。由于图的2-lift与图的带号图的一一对应关系，拟研究带号图的谱半径的性质，包括带号图的谱半径与标号函数之间的关系，分析如何对带号图实施变换以便于谱半径的求解，给定基础图的所有带号图的谱半径所能达到的最小值与基础图的结构的关系。拟研究超图的谱性质，包括如何利用正则超图的第二特征值来分析超图的扩容性，研究超图与其覆盖超图的特征值之间的关系，特别是正则超图的第二特征值与超图的一致覆盖的谱半径之间的关系。研究超图的特征值特别是谱半径与超图的结构间的关系。研究某些图类中匹配能量的极值问题，探究图的匹配能量与能量间隙的上下界。

本项目主要研究谱图理论中的几个重要问题，包括极值超图谱理论、图的匹配多项式和图的极特征值性质。我们引入了超图上的“移边”变换，通过研究超图的邻接张量、无号拉普拉斯张量和关联Q-张量的谱半径在这些变换下的谱扰动，刻画了这三种谱半径在超树中达到的前两大的值以及取到极值的极图。同时考虑了这三种谱半径相应的极小值问题。我们这些方法被众多学者用来成功地解决了很多超图类中谱半径的极值问题。我们给出了一致（有限或无限的）超图的谱半径的一个下界，将著名的Alon-Boppana定理推广到超图上来，即给出了超图的第二特征值的一个下界，这些结论有望将图上扩容性的结论推广到超图上来。我们在超图上引入了匹配多项式的概念，得到了该匹配多项式一些基本结论，特别是超图的匹配多项式的递推关系式，以及超树的谱半径与它们的匹配多项式决定的拟序关系间的联系。利用超图的匹配多项式，建立了超树上关于谱半径的三个嫁接定理，作为推论解决了超树中前两大谱半径和前两小谱半径的极图刻画问题。重要的是，综合利用匹配多项式的方法和嫁接定理和我们的“移边”变换方法，以及加权关联矩阵方法，我们给出了在具有给定直径d的超树中取到前d/2大谱半径的极值超树。同时，在具有给定匹配的超树中我们给出了具有最大谱半径的超树。 在给出了一系列相关的超树的拟序关系后，综合利用多种方法，我们在具有给定匹配的超树中刻画了具有第二大谱半径的超树。这些结论为进一步研究极值超图谱理论提供了方法、思想和工具。我们研究了图的补图的匹配多项式和匹配数的表达式，建立了图的运算或变换后的图的补图与原来的图的补图的关于匹配数的拟序关系，基于此我们确定了具有给定点数的补图为单圈图的图类中关于拟序关系的最大和最小的极图，以及具有给定点数和围长的补图为单圈图的图类中关于拟序关系的最大和最小的极图。我们研究了具有给定点数和围长的补图为双圈图的图类中关于拟序关系的最大和最小的极图。这些结论可以用来比较图的匹配能量。