The Bollobás–Riordan polynomial can mean a 3- variable

invariant polynomial In mathematics, an invariant polynomial is a polynomial P that is invariant under a group \Gamma acting on a vector space V. Therefore, P is a \Gamma-invariant polynomial if :P(\gamma x) = P(x) for all \gamma \in \Gamma and x \in V. Cases of p ...

of graphs on orientable surfaces, or a more general 4-variable invariant of

ribbon graph In topological graph theory, a ribbon graph is a way to represent graph embeddings, equivalent in power to signed rotation systems or graph-encoded maps. It is convenient for visualizations of embeddings, because it can represent unoriented surfa ...

s, generalizing the

Tutte polynomial The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contain ...

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

References

* * {{DEFAULTSORT:Bollobas-Riordan polynomial Polynomials

History

Formal definition

See also

References