# zbMATH — the first resource for mathematics

A polynomial of graphs on surfaces. (English) Zbl 1004.05021
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.

##### MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory
ribbon graph
Full Text: