Polynomial invariants of graphs with state models (Q1842661)

The Negami polynomial is a 3-variable polynomial invariant for graphs introduced and named by the first author [Trans. Am. Math. Soc. 299, 601-622 (1987; Zbl 0674.05062)]. It has been shown by the reviewer that this polynomial has a straightforward expression in terms of the well-known Tutte polynomial. This paper shows how the Negami polynomial can also be derived by using a model that assigns states to the vertices of the graph and thereby attaches weights to the edges of the graph. The Negami polynomial is expressible as a summation over all states of the graph of the product of these edge weights. This approach is also used to define an extension of the Negami polynomial which the authors show can be used to distinguish many graphs which the original polynomial could not. For instance, the new polynomial can be used to determine the minimum degree of a loopless connected graph.