Английская Википедия: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 Шаблон:Harvs.
Formal definition
The 3-variable Bollobás–Riordan polynomial of a graph <math>G</math> is given by
- <math>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>F</math> and
- <math>v(G)</math> is the number of vertices of <math>G</math>;
- <math>e(G)</math> is the number of its edges of <math>G</math>;
- <math>k(G)</math> is the number of components of <math>G</math>;
- <math>r(G)</math> is the rank of <math>G</math>, such that <math>r(G) = v(G)- k(G)</math>;
- <math>n(G)</math> is the nullity of <math>G</math>, such that <math>n(G) = e(G)-r(G)</math>;
- <math>bc(G)</math> is the number of connected components of the boundary of <math>G</math>.
See also
References
