View source for Bollobás–Riordan polynomial

The '''Bollobás–Riordan polynomial''' can mean a 3-[[Variable (mathematics)|variable]] [[Invariant polynomial|invariant polynomial]] of graphs on [[Orientability#Orientable surfaces|orientable surfaces]], or a more general 4-variable invariant of [[Ribbon graph|ribbon graph]]s, generalizing the [[Tutte polynomial]].
==History==
These polynomials were discovered by {{harvs |txt |last1=Bollobás |first1=Béla| last2=Riordan |first2=Oliver| year=2001 |year2=2002}}.

==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 [[Glossary of graph theory terms#S|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==
*Graph invariant

==References==
*{{Citation | last1=Bollobás | first1=Béla |  last2=Riordan | first2=Oliver |  title=A polynomial invariant of graphs on orientable surfaces | doi=10.1112/plms/83.3.513 | mr=1851080 | year=2001 | journal=[[Organization:Proceedings of the London Mathematical Society|Proceedings of the London Mathematical Society]] |series=Third Series | issn=0024-6115 | volume=83 | issue=3 | pages=513–531}}
*{{Citation | last1=Bollobás | first1=Béla |  last2=Riordan | first2=Oliver | title=A polynomial of graphs on surfaces | doi=10.1007/s002080100297 | mr=1906909 | year=2002 | journal=[[Mathematische Annalen]] | issn=0025-5831 | volume=323 | issue=1 | pages=81–96}}

{{DEFAULTSORT:Bollobas-Riordan polynomial}}
[[Category:Polynomials]]

{{Sourceattribution|Bollobás–Riordan polynomial}}