定向图斜谱的若干问题的研究

The spectrum of a graph is one of the most basic concepts of graph-theoretic subjects. The skew spectrum of an oriented graph is a very important concept based on its skew adjacency matrix. The skew adjacency matrices of oriented graphs comes from Tutte’s classical research result about the perfect matching of a graph. Afterwards, many researchers including Haemers and Kirklands have been studying the skew spectra of oriented graphs, which extends the research in this field. Based on the skew spectrum, Adiga et al. introduced the skew energy of an oriented graph, which can be reviewed as the generalization of the graph energy (introduced by mathematician and chemist Gutman). The skew spectra of oriented graphs are attracting more and more attentions, because the skew spectra are related to many important problems, for example, the enumeration of perfect matchings, and have applications in Chemistry.. This project will study the maximum skew spectral radius of a graph and find an effective algorithm of its extremal orientations. The project will study the inner relation between the skew spectral radius of an oriented graph and the matching polynomial of its underlying graph. The project will utilize the graph operations and Cayley graphs to construct integral oriented graphs. The project will study the extremal problems of skew energy by the nonlinear programming and the structural analysis of oriented graphs.

图谱是图论学科中最基本的概念之一。斜谱是基于定向图的斜邻接矩阵提出的一个重要概念。定向图的斜邻接矩阵来源于Tutte关于完美匹配的经典研究结果。此后Haemers, Kirklands等许多著名学者都对定向图斜谱进行了研究，从而拓展了这一领域。基于定向图的斜谱，Adiga等人提出了定向图斜能量的概念。斜能量可以被看作是无向图的能量（数学化学家Gutman引入）在定向图上的推广。定向图斜谱与图论中的一些重要问题如完美匹配计数问题等有紧密联系，同时又有化学应用，因此它得到了越来越多的学者的关注。. 本项目旨在从算法的角度研究一个图的最大斜谱半径及其极值定向，力争找到极值定向的有效算法；研究基图的匹配多项式与定向图的斜谱半径的内在联系；利用图运算和凯莱图来构造整斜谱定向图；结合非线性优化方法和定向图的结构分析，研究定向图斜能量的极值问题。

定向图的斜谱为代数图论中一个重要的研究课题。尤其是最近关于定向图斜谱极值问题的研究，定向图的斜能量的研究，以及定向图的斜谱与组合设计的关系的研究，清晰地表明了定向图的斜谱不仅具有重要的理论意义，而且在化学、组合设计上有重要的应用。本项目以定向图的斜谱为主要研究对象。借助于图谱理论、矩阵分析、随机矩阵, 本项目深入、系统地研究定向图的斜谱及斜特征多项式，挖掘斜特征多项式和匹配多项式之间的关系，从而给出了关于定向图斜谱的一些极值问题的解答，同时研究随机定向图下的斜特征多项式的性质，给出随机定向图的斜邻接矩阵的行列式的各阶矩的图论表示，解决了该方向的一个公开问题。定向图的斜谱和斜能量与基图的匹配多项式和匹配能量有很大联系。基图的匹配多项式和匹配能量是化学图论领域一个重要课题。通过探究图的匹配多项式和图结构之间的关系，图的匹配多项式在去边和去顶点条件的展开式，结合匹配根的性质，本项目完全解决了完全多部图的匹配能量和最大匹配根的极值问题，完全刻画了该图类中具有极大和极小匹配能量的图。此外，在化学图论方面，本项目进一步研究了连通离心指标，通过引进一种新的图积运算，解决了该指标复杂度的一个公开问题。本项目可以进一步丰富定向图的斜谱的研究成果, 也可以推动匹配能量和连通离心指标的进一步发展.