Polynomial invariants of graphs

A polynomial invariant of a graph can be defined by a recursive formula with respect to contraction and deletion of edges. That is what is called the Negami polynomial. many studies on information derived from this polynomial, splitting formula, dual polynomial the extended Negami polynomial and so on have been developed in [Papaer 17, 35, 36, 37�n, and many people seem to be interested in those. In particular, it is extremely dexterious to read the degree sequence of a graph from its extended Negami polynomial.

The Negami polynomial includes potentially other known polynomials as the chromatic polynomial and the flow polynomal, and can be said to be equivalent to the Tutte polynomial which is a matroid invarian in a sense. It might be preferable because of its simple and easy definitoin. Also, the Jones polynomial, which has been studied well in knot theory, can be regarded as a kind of a polynomial invariant of a plane graph and can be said to be related to the Negami polynomial.

�@Ken'ichi Kawagoe, now an assistant in Kanazawa University, redefined the Negami polynomial in his thesis, using a method called a state model. Extending his idea led us to the extended Negami polynomial.