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 is given by
,
where the sum runs over all the spanning subgraphs and is the number of vertices of ; is the number of its edges of ; is the number of components of ; is the rank of , such that ; is the nullity of , such that ; is the number of connected components of the boundary of .
See also Graph invariant
References