距离正则图的谱理论

项目名称： 距离正则图的谱理论

项目编号： No.11471009

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 库伦

作者单位： 中国科学技术大学

项目金额： 70万元

中文摘要： 本项目主要研究距离正则图的分类相关问题,具体包括两个部分：距离正则图和交叉数之间的关系，以及最小特征值为固定值的图的性质。目前所有已知的直径至少为 8 的本原距离正则图都是 Q-多项式的。 著名组合图论专家Bannai于1984年提出对大直径的 Q-多项式距离正则图进行分类。但是 VanDam 和 Koolen 发现的与特定Grassmann 图包含同样交叉数的反常 Grassmann 图表明了 Bannai 提出的分类问题比想象的困难的多。我们计划通过图谱理论来探索已知的距离正则图是否被它们的交叉数完全确定。在第二部分中，我们将会在Camara 等对最小特征值至少为-2 的图完全分类的基础上，对最小特征值为-3 的例外强正则图进行分类，并推广 Hoffman 理论。本项目的研究将不仅为距离正则图的分类问题提供强大的理论基础和依据，而且会大大丰富图分类研究领域的科研成果。

中文关键词： 代数图论；结合方案；组合矩阵

英文摘要： All known examples of primitive distance-regular graphs with diameter at least 8 are Q-polynomial. It is not yet understood why this is the case. Bannai asked to classify the Q-polynomial distance-regular graphs with large diameter. But the discovery of the twisted Grassmann graphs by Van Dam and Koolen, an infinite family of unbounded, non-vertex-transitive distance-regular graphs with the same intersection numbers as certain Grassmann graphs, showed that the above classification problem of Bannai is much harder then previously thought. This also leads us to the question whether all the known families of distance-regular graphs are determined by their intersection numbers.The first part of this project is to look at the this problem whether the known distance-regular graphs like the Grassmann graphs and the bilinear forms graphs are determined by their intersection numbers. We propose to attack this problem using spectral graph theory.In the second part of this project we will look at graphs with a fixed smallest eigenvalue, mainly -3.In 1976, Cameron et al.showed that any connected graph that has smallest eigenvalue at least -2 is either a generalized line graph (a line graph with cocktail party graphs attached to some cliques in the line graph) or the number of vertices is bounded by 36.In this part of project, we will classify the exceptional strongly regular graphs with smallest eigenvalue -3 and extend the theory as developed by Hoffman.

英文关键词： Algebraic graph theory;Association scheme;Combinatorial matrix