A polynomial of graphs on surfaces (Q697371)

A ribbon graph can be thought of, informally, in terms of neighborhoods of graphs imbedded into surfaces: disks (vertices) joined by thin strips (edges) glued to their boundaries. The authors introduce a polynomial invariant of ribbon graphs called the ribbon graph polynomial and denoted by \(R\). The polynomial is of four variables, including \(X\), and is a generalization of the Tutte polynomial. Their main result is that \(R(G)= R(G/e)+ R(G-e)\) for each edge \(e\) which is neither a bridge nor a loop, whereas \(R(G)= XR(G/e)\) if \(e\) is a bridge. They show that \(R\) is the universal ribbon graph invariant satisfying the contraction-deletion results above. They also give the spanning tree expansion of \(R\), and consider the concept of dual ribbon graph, showing that a certain specialization of the ribbon graph polynomial takes the same values on a ribbon graph as on its dual.