Generalized Transition Polynomials

摘要

We construct a one variable graph polynomial, q(G, W; x) on the space of Eulerian graphs G with weight system W. This polynomial generalizes the transition polynomial of Jaeger from 4-regular Eulerian graphs to all Eulerian graphs. Furthermore, we provide a Hopf algebraic structure for the space of weighted Eulerian graphs and show that q(G, W; x) is a Hopf algebra map. Many polynomials, such as the Tutte, Penrose, and Martin polynomials, as well as the Kaufman bracket of knot theory and Bollobas and Riordan's Tutte polynomial for coloured graphs, can be formulated, at least partially, as evaluations of q(G, W; x) Thus, the comultiplication and antipode of the Hopf algebra give new tools for analyzing these polynomials as well.