The Calculation And Property Research Of Kirchhoff Polynomial Of Graphs

In recent years,as an important branch of combinatorial mathematics,graph theory has continuously increasing relationship with quantum field theory,combinatorial optimization,operational research,physical communication,computer science,statistical physics,and other fields.The research on spanning tree has attracted people's attention,and the counting problem of spanning trees is also an important direction.Although there are a lot of algorithms to calculate spanning trees,most of these algorithms are based on analysis method,such as Greedy algorithm,Fleury algorithm.On the other hand,the matrix tree theorem is based on algebraic matrix method to calculate the numbers of spanning trees.In this paper,we further study certain properties of the general matrix tree theorem.In the research of spanning tree,we assign all edges of a spanning tree with different variables,and form a monomial in these variables.Then the sum of all the monomials corresponding to all spanning trees is called spanning tree polynomial of the graph.When each variable is assigned value one,we can get the matrix tree theorem,which is about the number of spanning trees.The Kirchhoff polynomial has been an important subject of spanning tree in graph theory.Its structure is based on the spanning tree of graph by definition.For different types of graphs,we can get a lot of different kinds of polynomials.If the variables in the spanning tree polynomial take values in a finite field,then the problem of finding the number of zeros of the polynomial is famous conjecture of Kontsevich.The dual Kirchhoff polynomials are related to some invariants of the Feyman integral in special cases.In this paper,we calculate the Kirchhoff polynomials of some special graphs,and obtain some properties on the Kirchhoff polynomials,including the relationship between dual Kirchhoff polynomial of planar graph and Kirchhoff polynomial of its dual graph.An necessary and sufficient condition for Kirchhoff polynomials of graph to be reducible is given,and an necessary and sufficient condition for the Kirchhoff polynomials of two graphs with common factor is then obtained.It is proved that the Kirchhoff polynomials of two sub-graphs of Aztec diamond graph do not have the factor relation.The operation of Kirchhoff polynomial under some graph operation is given.The number of zeros of the Kirchhoff polynomials of some special graphs in finite field is calculated.Lastly,the generation function of some graphs is computed under probability conditions.