图的积和多项式及相关问题研究

The study of graph polynomials involving characteristic polynomial and Laplacian polynomial etc. and their related problems has a long time. It is an important branch of graph theory. The permanental polynomials of graphs were introduced in mathematics and chemistry almost simultaneously. Some challenging problems have been put forward, and many basic problems need solutions. Since the permaental polynomial is difficult to calculate. Up to now, only a few results involving permantental polynomial have been published, and there lack systemic theory to study permanental polynomial. Recently, studies on the permanental polynomials of graphs has been the focus of a group of scientists. This project studies the permanental polynomials of graphs and some problems closely related with it, mainly including the calculation of permanental polynomials of some important graphs with actual backgrounds， and their distribution and properties of roots. In details, (1) We use Pfaffian orientation theory to compute the permanental polynomials of graphs, and give new calculation method; (2) We discuss the distribution and properties of roots of permanental polynomial of a graph, and the relation between roots and structure parameters.(3) We discuss the problem of Brenner and Brualdi which about module of the maximum root of the permanental polynomial is equal to the spectral radius. (4) We study the skew permanental polynomial of orientation graph and their related problems. Systematical studies of this project can produce some valuable research methods,and solve some important problems and finally push forward the further development of the theory of permanental polynomial and its applications.

图的特征多项式、Laplace多项式等图多项式及其相关问题的研究由来已久，是图论研究中一个重要分支。 图的积和多项式几乎同时在数学和化学中引入，一些挑战性的问题被相继提出，有许多基本问题亟待解决。由于图的积和多项式的计算很困难，到目前为止，得到的结果较少，还缺乏系统的理论，但最近已经受到一批组合学家的重点关注。本项目研究图的积和多项式及与之密切相关问题，主要包括一些有实际背景的重要图类的积和多项式的计算及其根的分布与性质。具体地,（1）用Pfaffian定向等理论计算图的积和多项式，给出新的计算方法;（2）探讨积和多项式的根的分布与性质，及其与结构参数的关系;（3）研究Brenner和Brualdi关于刻画积和多项式的最大根的模等于谱半径的问题;（4）研究定向图的斜积和多项式及其相关问题。通过本项目的研究提出有价值的研究方法, 解决若干重要问题, 推动积和多项式理论和应用进一步发展。

图矩阵积和式的研究是图论研究的一个重要方向。图积和多项式在化学和复杂网络中有着重要的应用背景且是亟待发展的研究领域。本项目主要研究了图的永久和、积和根、基于图匹配的相关参数研究三个部分。中科院郑兰孙院士等合成了富勒烯D_50(D_5h)，清华大学白峰杉教授等发现了D_50(D_5h) 的一种化学现象，为解释这种化学现象，我们提出了永久和的定义。 对永久和进行了系统的研究，发现图的永久和与斐波那契数及Hosoya指标密切相关。证明了永久和的计算是#P-完全的；给出永久和的矩阵表达式；刻画了一些图类的永久和的界及达到该界的极图。这些成果得到了国内外学者的关注，永久和已经成为了一种新的拓扑指标被国内外学者开始研究。积和谱的研究是围绕著名猜想和前人提出的问题而开展的工作，证明了一些图类是积和谱刻画的，给出了一种构造既是积和同谱图又是邻接同谱图的方法。这些成果既有方法上的创新，又有结论上的创新，推动了积和谱理论的研究进展。基于图匹配的参数研究中主要考虑了Hosoya指标、匹配能、匹配排除三个拓扑指标，给出了一些图类Hosoya指标和匹配能的界，刻画清楚了达到该界的极图;研究了超立方及其形变网络的匹配排除问题. 这些成果丰富了超立方网络的研究。