Многочлен Боллобаша — Риордана (Bukikclyu >kllkQgog — Jnkj;gug)

Многочлен Боллобаша — Риордана — это инвариантный многочлен графов на ориентируемых поверхностях от трех переменных или инвариант ленточных графов от четырех переменных, обобщающий многочлен Татта.

История

Эти многочлены открыли Бела Боллобаш и Оливер Риордан в 2001 году.

Определение

Многочлен Боллобаша — Риордана от трех переменных задаётся следующей формулой:

$R_{G}(x,y,z)=\sum _{F}x^{r(G)-r(F)}y^{n(F)}z^{k(F)-bc(F)+n(F)}$

где

• v(G) — это число вершин графа G;
• e(G) — это число ребер графа G;
• k(G) — это число компонент связности графа G;
• r(G) — это ранг графа G, r(G) = v(G) − k(G);
• n(G) — это контурный ранг графа, n(G) = e(G) − r(G);
• bc(G) — это число связанных компонентов грани графа G.

См. также

• Инвариант графа

Литература

• 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