Bollobás–Riordan polynomial

History

These polynomials were discovered by .

Formal definition

The 3-variable Bollobás–Riordan polynomial of a graph G is given by

:R_G(x,y,z) =\sum_F x^{r(G)-r(F)}y^{n(F)}z^{k(F)-bc(F)+n(F)},

where the sum runs over all the spanning subgraphs F and

• 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 G, such that n(G) = e(G)-r(G);
• bc(G) is the number of connected components of the boundary of G.

References

References

1. Bollobás, Béla. (November 2001). "A Polynomial Invariant of Graphs On Orientable Surfaces". Proceedings of the London Mathematical Society.
2. Bollobás, Béla. (May 2002). "[No title found]". Mathematische Annalen.