图积和多项式理论中的图结构与极值问题

In recent years, the permanental polynomials of graphs are more and more widely investigated in the areas of Mathematics and Chemistry. Arising with Pólya problem and Borowiecki problem, the conversions of permanental polynomials and characteristic polynomials and the relation between the permanental roots and permanental coefficients and the structures of graphs are important research subjects. Following these problems, this project will focus on three aspects: the relation between the conversions of permanental polynomials and characteristic polynomials and the structures of graphs, the relation between the properties on real and imaginary permanental roots and the structures of graphs, as well as the extremal problem on the sum of coefficients of permanental polynomial. The explicit research approaches are as follows: 1)deepen the existing research and establish new ideas. By introducing the linear combination of the skew-characteristic polynomials of orientation graphs, we will first study the conversions of such linear combinations and the permanental polynomials, and then determine the structures the those graphs with this convertible properties in terms of ear decomposition. 2) by breaking through the existing method, we plan to improve the existed results of Borowiecki problem. By combining the combinatorial analysis and the theory on the roots of polynomials in the complex domain, we will determine the existence of new graphs whose permanental roots are pure imaginary numbers, and characterize such graphs. 3) with the help of graph structures and matching numbers, we will first study the sums of permanental coefficients of hexagonal system and extended graphs, and then establish the bounds of this sums and characterize the structures of extremal graphs. The research of above problems is expected to not only provide a new idea to the study of permanental polynomials of graphs, but also enrich and improve the theory of permanental polynomials of graphs.

近年来图积和多项式在数学、化学领域的研究日益广泛：围绕Pólya问题、Borowiecki问题产生的积和多项式和特征多项式的转化问题、积和多项式的根和系数与图结构关系问题是当前研究的重要方面。针对其突出问题，本项目深入研究三方面内容：积和多项式和特征多项式的转化与图结构关系、积和多项式根的实虚性与图结构关系、积和多项式系数和的极值问题。具体思路为：1）深化并创新已有研究，引入定向图斜特征多项式的线性组合，研究其与积和多项式的转化，利用耳朵分解，刻画可转化图类结构；2）突破已有方法，运用组合分析与复数域多项式根理论相结合的方法，研究积和多项式的根均为纯虚数新图类的存在性及结构，以促进Borowiecki问题研究；3）借助图结构及匹配计数，建立Cata-型六角系统及其推广图类积和多项式系数和的界值，并刻画极值图。上述问题的研究，将为图积和多项式研究提供新思路，丰富发展图积和多项式理论体系。

由于特征多项式不是图结构的不变量，Tuner 提出利用图的积和多项式研究图结构，自此有关积和多项式与图结构关系的研究逐渐受到关注。近年来，积和多项式与特征多项式的转化问题、积和多项式系数和等问题的研究日渐活跃。本项目主要围绕以下四方面内容展开：（一）研究了积和多项式和特征多项式的转化与图结构关系，得到可转化图类的禁止子图条件，并借助平面耳朵分解，分别刻画了二部等值图和非二部等值图的结构，该研究提供了研究具有给定代数性质图类结构的新方法，丰富了结构图论的研究内容；（二）研究了定向图积和多项式与原图积和多项式的转化与图结构关系，首先构建了定向方案使得定向图斜积和多项式常数项的绝对值等于原图完美匹配数平方，在此基础上确立了满足定向二部图斜积和多项式和原图积和多项式的对应项系数在绝对值意义下相等的定向图条件，最后建立了定向图的斜积和多项式与原图的特征多项式的转化关系，刻画了可转化图类的结构及定向图特征。本研究提供了计算定向图斜积和多项式的新方法，深化了多项式的内在联系，用图论方法解决了多项式间的转化问题；（三）研究了具有对称积和多项式的图结构，得到了根积图和连根图的积和多项式与子图的积和多项式的生成关系，建立了判定对称积和多项式的充要条件，基于根积图刻画了具有对称积和多项式的图结构，该结果提供了研究图结构的新思路；（四）研究了积和多项式系数和的极值问题，利用拼接变换，确立了极值六角链的结构，并得到极值六角链直链积和多项式系数和为0，进一步的推广得到了平面及柱面上四边形直链的积和多项式系数和。上述四方面内容的研究为图积和多项式研究提供了新思路，丰富发展了图积和多项式理论体系，为挖掘积和多项式的应用提供了理论依据。