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
[edit]These polynomials were discovered by Béla Bollobás and Oliver Riordan (2001, 2002).
Formal definition
[edit]The 3-variable Bollobás–Riordan polynomial of a graph is given by
- ,
where the sum runs over all the spanning subgraphs and
- is the number of vertices of ;
- is the number of its edges of ;
- is the number of components of ;
- is the rank of , such that ;
- is the nullity of , such that ;
- is the number of connected components of the boundary of .
See also
[edit]References
[edit]- 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, MR 1851080
- 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, MR 1906909