Bollobás–Riordan polynomial

From HandWiki

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 Béla Bollobás and Oliver Riordan (2001, 2002).

Formal definition

The 3-variable Bollobás–Riordan polynomial of a graph [math]\displaystyle{ G }[/math] is given by

[math]\displaystyle{ R_G(x,y,z) =\sum_F x^{r(G)-r(F)}y^{n(F)}z^{k(F)-bc(F)+n(F)} }[/math],

where the sum runs over all the spanning subgraphs [math]\displaystyle{ F }[/math] and

  • [math]\displaystyle{ v(G) }[/math] is the number of vertices of [math]\displaystyle{ G }[/math];
  • [math]\displaystyle{ e(G) }[/math] is the number of its edges of [math]\displaystyle{ G }[/math];
  • [math]\displaystyle{ k(G) }[/math] is the number of components of [math]\displaystyle{ G }[/math];
  • [math]\displaystyle{ r(G) }[/math] is the rank of [math]\displaystyle{ G }[/math], such that [math]\displaystyle{ r(G) = v(G)- k(G) }[/math];
  • [math]\displaystyle{ n(G) }[/math] is the nullity of [math]\displaystyle{ G }[/math], such that [math]\displaystyle{ n(G) = e(G)-r(G) }[/math];
  • [math]\displaystyle{ bc(G) }[/math] is the number of connected components of the boundary of [math]\displaystyle{ G }[/math].

See also

  • Graph invariant

References