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 Béla Bollobás and Oliver Riordan (2001, 2002).

Formal definition

The 3-variable Bollobás–Riordan polynomial is given by

where

  • 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 such that n(G) = e(G) − r(G);
  • bc(G) is the number of connected components of the boundary of G.
gollark: Unfortunately the "comparing features" bit is probably extremely hard.
gollark: The annoying thing is that I'm pretty sure I've got duplicates, but I can't *check* because memes tend to get randomly recompressed and cropped and downscaled and whatnot, so `fdupes` doesn't work on them.
gollark: Apparently I've now got 2021 memes saved for easy access, including that one.
gollark: I'm a climate denier. I don't believe the *lies* about "temperature" and "weather". They're just made up to sell more clothes.
gollark: It's nice to hope so, but people believe *so* many weird stupid things...

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, 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.