Bollobás–Riordan polynomial

These polynomials were discovered by {{harvs |txt |author1-link=Béla Bollobás |last1=Bollobás |first1=Béla| author2-link=Oliver Riordan |last2=Riordan |first2=Oliver| year=2001 |year2=2002}}.

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

:$R\_G(x,y,z)\; =\backslash sum\_F\; x^\{r(G)-r(F)\}y^\{n(F)\}z^\{k(F)-bc(F)+n(F)\}$,

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$.

• Graph invariant

• {{Citation | last1=Bollobás | first1=Béla | author1-link=Béla Bollobás | last2=Riordan | first2=Oliver | author2-link=Oliver Riordan| title=A polynomial invariant of graphs on orientable surfaces | doi=10.1112/plms/83.3.513 | mr=1851080 | year=2001 | journal=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 | author1-link=Béla Bollobás | last2=Riordan | first2=Oliver | author2-link=Oliver Riordan |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}}

Category:Polynomials

Category:Graph invariants