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 .

Formal definition

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

:$R_G(x,y,z) =\sum_F x^y^z^$,

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

References

*
*

{{DEFAULTSORT:Bollobas-Riordan polynomial
Polynomials