基于图的不变量与子图结构的谱极值问题研究

项目名称： 基于图的不变量与子图结构的谱极值问题研究

项目编号： No.11201432

项目类型： 青年科学基金项目

立项/批准年度： 2013

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

项目作者： 刘瑞芳

作者单位： 郑州大学

项目金额： 22万元

中文摘要： 图谱理论主要通过研究图的相关矩阵的谱性质来反映图的结构性质，是当前代数图论和组合矩阵论共同关注的一个重要课题。本项目拟对图的谱极值问题开展两方面的深入研究。第一，基于图的不变量的谱极值问题：即刻画图的不变量固定的图类中谱参数的极值或极图，研究图的特征值与各种不变量(如团数、色数、独立数、直径等)之间的联系。图的特征值具有好算法，而图的某些不变量如独立数及团数的计算是NP-困难的，因此这方面的研究是很有必要的。第二，基于子图结构的谱极值问题：即确定包含或者禁用某种子图(如完全子图、完全二部子图、给定长的路和圈、Hamilton圈和路等)的图类中谱参数的极值，如谱形式的Turá和Zarankiewicz型问题，研究图的特征值与某种子图存在性之间的关系。本项目将综合运用图论和矩阵论方法，采用理论推导和计算机验证相结合的研究方案，挖掘和丰富谱图论研究的工具，以期推动上述问题的顺利解决。

中文关键词： 图矩阵；特征值；特征向量；不变量；子图结构

英文摘要： Spectral graph theory mainly studies structure properties of graphs using the spectrum of related matrices, and now it is an important subject concerned commonly by algebraic graph theory and combinatorial matrix theory. The program will develop two field of intensive study on spectral extremal value problem. One is spectral extremal value problem based on the invariants of graphs, i.e., characterizing extremal value or extremal graph of spectral parameter in a given set of graphs with some fixed invariant of graph, and investigating the connection between eigenvalues of graphs and all kinds of invariants of graphs (e.g. clique number, chromatic number, independence number and diameter). The eigenvalues of graphs have good algorithm, however the computation complexity of some invariants of graphs (e.g. independence number and clique number) is NP-hard, and hence it is very necessary to develop the research.The other is spectral extremal value problem based on subgraph structure, that is to say, determining extremal value of spectral parameter in a given set of graphs including or forbidding some subgraph (e.g. complete subgraph, complete bipartite subgraph, path and cycle with given length, Hamilton cycle and path, and so on), for example, spectral forms of Turáand Zarankiewicz type problems, and studying the

英文关键词： graph matrix；eigenvalue；eigenvector；invariant；subgraph structure