Bollobás–Riordan polynomial
From HandWiki
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 Béla Bollobás and Oliver Riordan (2001, 2002).
Formal definition
The 3-variable Bollobás–Riordan polynomial of a graph [math]\displaystyle{ G }[/math] is given by
- [math]\displaystyle{ 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]\displaystyle{ F }[/math] and
- [math]\displaystyle{ v(G) }[/math] is the number of vertices of [math]\displaystyle{ G }[/math];
- [math]\displaystyle{ e(G) }[/math] is the number of its edges of [math]\displaystyle{ G }[/math];
- [math]\displaystyle{ k(G) }[/math] is the number of components of [math]\displaystyle{ G }[/math];
- [math]\displaystyle{ r(G) }[/math] is the rank of [math]\displaystyle{ G }[/math], such that [math]\displaystyle{ r(G) = v(G)- k(G) }[/math];
- [math]\displaystyle{ n(G) }[/math] is the nullity of [math]\displaystyle{ G }[/math], such that [math]\displaystyle{ n(G) = e(G)-r(G) }[/math];
- [math]\displaystyle{ bc(G) }[/math] is the number of connected components of the boundary of [math]\displaystyle{ G }[/math].
See also
- Graph invariant
References
- Bollobás, Béla; Riordan, Oliver (2001), "A polynomial invariant of graphs on orientable surfaces", Proceedings of the London Mathematical Society, Third Series 83 (3): 513–531, doi:10.1112/plms/83.3.513, ISSN 0024-6115
- Bollobás, Béla; Riordan, Oliver (2002), "A polynomial of graphs on surfaces", Mathematische Annalen 323 (1): 81–96, doi:10.1007/s002080100297, ISSN 0025-5831
 |  |
