图多项式与匹配理论研究

图多项式含其基础图的许多有用的组合信息，图参数（Numeric graph invariant）是图的组合信息的数值表示形式。分子图的拓扑不变量（图指标）常能反映该化合物的物理化学性质。本项目主要研究匹配多项式及其相关图多项式的代数性质；用图多项式刻画图参数（图指标）、图结构；讨论图多项式的根、系数的分布规律及与图的关系；通过研究各种匹配变换图及相关的图参数来研究一般图的匹配问题，期望找到有完美匹配图与无完美匹配图之间匹配结构的本质区别与联系。这些问题具有重要的理论价值和明确的实际背景，且涉及到组合数学与图论的重要部分。本研究将丰富匹配理论内容，发展代数图论、组合计数的基本理论和方法。

本项目研究了匹配多项式及其相关图多项式的代数性质；用图多项式刻画图参数与图结构；讨论图多项式的根、系数的分布规律及与图的关系；利用匹配理论中一般图的Gallai-Edmonds分解定理、基本二部图与因子临界图的耳朵分解、有完美匹配图的块分解等结果研究一般图的匹配计数问题；通过研究与匹配有关的图参数和各种匹配变换图来研究一般图的匹配问题，主要研究结果：（1）研究了一些典型图类的匹配多项式、特征多项式、Wiener多项式、 Laplacian特征多项式、点独立集多项式，利用图变换及各图多项式的性质及关系, 刻画了给定图类的全匹配数、全独立数、Wiener数、谱半径、Eccentric connectivity指数、Winer-type指数及Schults 指数，并得到对应极值图的结构；给出了一种计算六角链的边-Szeged指数的新方法-割法，并计算了一些六角链的边-Szeged指数；研究了图的极大Balaban指数，分别刻画了单圈图、双圈图中具有极大Balaban指数的图类。（2）利用图变换研究了树的Laplacian系数，给出了具有次大、次小、第三大、第三小Laplacian系数的树结构；研究了图的前k个Laplacian特征值的和的问题，证实了Brouwer等的猜想在一些图的情形下是正确的，并关于特定的树给出了一个更好的上界。（3）研究了具有完美匹配及直径d的树的Laplacian能量，证明了d=4,5时，这类图的Laplacian能量不小于路的Laplacian能量，部分解决了Radenkovic和Gutman的猜想。（4）研究了随机六角格子系统的Dimer构型、Monomer-Dimer构型中的计数问题；给出了Dimer常数、三个不同方向Dimer系统配分函数、Monomer-Dimer常数及Monomer-Dimer系统配分函数的计算公式，讨论了其渐进性。（5）根据给定的线图的完美匹配数，刻画了原图的性质及结构。（6） 根据给定的围长和边数，刻画了导出匹配可扩图的性质和结构。（7） 定义了第二类最大匹配图，研究了这类变换图的结构，并研究了第二类最大匹配图是完全图、树与圈时原图的结构。（8） 研究了一个图是分数k-因子。（9）研究了一类图的匹配计数与完美匹配计数问题，得到了三圈图的匹配数的上界和极图，解决一类因子临界图的最大匹配计数问题。