图的多项式研究及应用

项目名称： 图的多项式研究及应用

项目编号： No.10861009

项目类型： 地区科学基金项目

立项/批准年度： 2009

项目学科： 无线电电子学、电信技术

项目作者： 马海成

作者单位： 青海民族大学

项目金额： 20万元

中文摘要： 本项目研究了图的特征、匹配、色、伴随等多项式及其应用。主要研究内容是：研究了这些多项式的基本性质，根的分布规律，系数及根的图论意义等；研究了图多项式对图的组合结构的刻画，刻画了某项参数达到极值的图类，刻画了根在某个范围的图类，刻画了多项式相等即某个图的多项式等价图类，刻画了多项式所唯一确定的图类等；研究了多项式与多项式之间的相互联系，特殊图类的多项式计算等。主要结果是：完全刻画了一类图的谱等价类，刻画了许多谱唯一图类，给出了构造谱等价图的若干新方法，给出了谱半径的若干新界，对图的零度、行列式、积和式及6闭途径数等方面作出了研究；刻画了许多匹配唯一的图类，刻画了匹配最大根大于2的一个小范围的图类，作为应用计算了满足某些不等式条件的置换的个数；完全刻画了森林、单圈图、双圈图的色等价图类，给出了构造色等价图的若干新方法；计算了若干网络图的毁裂度、离散度和完整度，在网络的抗毁性方面进行了研究；对超图的着色也进行了研究，得到了若干结论。共发表论文41篇。

中文关键词： 图;多项式;矩阵;组合结构.

英文摘要： This academic research project studies characteristic polynomials, matching polynomials, chromatic polynomials, adjoint polynomials of graphs and their application. The central contents of the project are as follows: it studies cardinal properties of these polynomials, the ditributions of roots, significance of coefficients and roots in graph theory and so on; it also studies the combinatorial structure of graph portrayed by polynomails of graphs in which it characterizes the graph class that has extremal for some parameter of graph, and portrays the graph of roots in a definite areas, characterizes polynomials equevalence, namely, polynonials equivalent classes of some graphs, and also characterizes the graphs uniquely determined by polynomials. It studies the relation among polynomials and calculations of poylnomials of some special graphs as well. The project has drawn the following conclusions: Firstly, it completely characterizes spectrum equivalent classes of a class graphs and a number of unique graphs determined by its adjacency spectrum. It shows new methods for constructing spectrum-equivalence graphs and new bounds on the spectral radius. It studies the nullity, the determinant, the permanent and the number of closed 6-walks of graphs. Secondly, it characterizes many graphs determined by its matching polynomial, and portrays a small-scaled graph class where the largest matching roots are less than two. It, as an application, calculates the number of permutation to satisfy some inequality conditions. Thirdly, it completely characterizes the chromatically equivalent graphs of a forest, a mono-cycle graph and a bi-cycle graph and shows several new methods for constructing chromatically-equivalence graphs. Fourthly, it calculates the rupture degree, the scattering number and integrity of several network graphs and conducts a study on the vulnerability of networks. Finally, it also studies hypergraphs colorable and draws some conclusions. A total of 41 academic articles related to the project have been published.

英文关键词： Graph;polynomial;Matrix;Combinatorial structure