Bollobás–Riordan polynomial - Alchetron, the free social encyclopedia

The Bollobás–Riordan polynomial can mean a 3-variable invariant polynomial of graphs on orientable surfaces, or a more general 4-variable invariant of ribbon graphs, generalizing the Tutte polynomial.

History

These polynomials were discovered by Bollobás and Riordan (2001, 2002).

Formal definition

The 3-variable Bollobás–Riordan polynomial is given by

R G ( x , y , z ) = ∑ F x r ( G ) − r ( F ) y n ( F ) z k ( F ) − b c ( F ) + n ( F )

where

v(G) is the number of vertices of G;

e(G) is the number of its edges of G;

k(G) is the number of components of G;

r(G) is the rank of G such that r(G) = v(G) − k(G);

n(G) is the nullity of such that n(G) = e(G) − r(G);

bc(G) is the number of connected components of the boundary of G.

References

Bollobás–Riordan polynomial Wikipedia

(Text) CC BY-SA

Contents

History

Formal definition

References