Bollobás–Riordan polynomial

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 Template:Harvs.

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$.

See also

• Graph invariant