谱与图的对称性及相关问题研究

Highly symmetric graphs possess highly symmetrical structures and algebraic properties of small number of eigenvalues and large multiplicities of eigenvalues. Cayley graphs are a class of important highly symmetric graphs. The spectral characterization of highly symmetric graphs, which is closely related with Algebra and Combinational Design Theory, is a branch of the study of spectral characterization. A lot of important advances have been made on the spectral characterization of graphs with 3 or 4 distinct eigenvalues. However, there are still many vital problems on the spectral characterization of highly symmetric graphs and Cayley graphs to solve.. In this project, by threading the spectral characterization of highly symmetric graphs as a main clue, using Spectral Theory, Algebra and Combinational Design Theory as tools, we mainly investigate the internal relations between the plentiful structures and algebraic properties of highly symmetric graphs. In particular, we investigate the explicit representations of the spectra of Cayley graphs, which further stimulate the research of integrality, DS-property and isomorphism classification of Cayley graphs. Besides, we also analyse the other extremity, that is, the spectral characterization of anti-symmetric graphs, and make efforts to get some research findings with high quality.

高度对称图具有高度对称的组合结构以及特征值数目较少、重数较高的代数特征；Cayley图是一类重要的高度对称图。高度对称图的谱刻画是图谱刻画研究的一个分支，同时与代数和组合设计理论有密切的关系。对3、4个特征值的图谱刻画已取得许多重要的进展，然而，高度对称图、Cayley图的谱刻画中还有许多重要问题尚未解决。. 本项目以图谱理论、代数理论和组合设计理论为工具，以研究高度对称图的谱刻画为主线，重点研究高度对称图丰富的组合结构和代数特征的内在联系，特别研究解决Cayley图的谱的显式表达，进一步研究Cayley图的整谱性、谱确定性及同构分类问题。此外，我们还要研究高度对称图的另一个极端，反对称图的谱刻画问题，努力取得较高质量的研究成果。

代数图论主要运用代数方法来解决图论问题，是图论学科的重要研究领域之一。其中图与线性代数，图与群论是代数图论的两个主要分支，图与线性代数的研究核心是图的谱理论，图与群论的研究核心是具有特定对称性的图。这两个分支之间也有着紧密的联系，例如，凯莱图的邻接谱可以由群的不可约表示的特征标表示出来；一些高度对称图往往具有较少数目的不同特征值。. 本项目中主要运用图谱理论、代数和组合方法研究高度对称图的组合特征及不同特征值数目较少、重数较高的代数特征。另外，几乎所有的图都是非对称的，这说明大部分图具有不同的特征值。因此，我们也研究了高度对称图的另一个极端——反对称图。具体包括以下几个方面：一是确定了二面体群上凯莱图的同构分类及计数，对称群、交错群上凯莱图的自同构群；二是确定了特殊群上凯莱图的谱间隙、整谱性、第二大特征值、哈密顿性，并得到了6类强正则轨道凯莱图；三是刻画了不同邻接特征值、距离特征值、距离拉普拉斯特征值、无符号距离拉普拉斯谱、正规拉普拉斯特征值数目较少的图，同时也刻画了恰有一个或两个正特征值的图；四是刻画了邻接特征值、无符号拉普拉斯特征值互不相同的图，构造了控制图（特征值互不相同且都是主特征值的图）的无穷类并且完全刻画了所有邻接特征值及距离特征值互不相同的门槛图；五是确定了给定图类的特征值及其分布。此外，我们确定了给定直径的树中Steiner Wiener指标的一个下界并得到了相应的极图, 得到了零度的一个上界等等。