<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Expansions for the Bollob´as-Riordan Polynomial of Separable Ribbon Graphs
Stephen Huggett1 and Iain Moffatt2
1School of Mathematics and Statistics, University of Plymouth, Drake Circus, Plymouth PL4 8AA, UK
s.huggett@plymouth.ac.uk
2Department of Mathematics and Statistics, University of South Alabama, Mobile, AL 36688, USA
imoffatt@jaguar1.usouthal.edu
Annals of Combinatorics 15 (4) pp.675-706 December, 2011
AMS Subject Classification: 05C31; 05C10, 57M15
Abstract:
We define 2-decompositions of ribbon graphs, which generalize 2-sums and tensor products of graphs. We give formulae for the Bollob´as-Riordan polynomial of such a 2-decomposition, and derive the classical Brylawski formula for the Tutte polynomial of a tensor product as a (very) special case. This study was initially motivated from knot theory, and we include an application of our formulae to mutation in knot diagrams.
Keywords: ribbon graph; embedded graph; 2-sum; tensor product; Tutte polynomial; Bollobás- Riordan polynomial; Ribbon graph polynomial; Jones polynomial

References:

1. Bollobás, B.: Modern Graph Theory. Springer-Verlag, New York (1998)

2. Bollobás, B., Riordan, O.: A polynomial invariant of graphs on orientable surfaces. Proc. London Math. Soc. 83, 513–531 (2001)

3. Bollobás, B., Riordan, O.: A polynomial of graphs on surfaces. Math. Ann. 323(1), 81–96 (2002)

4. Brylawski, T.H.: The Tutte polynomial I: general theory. In: Barlotti, A. (ed.) Matroid Theory and Its Applications, pp. 125–275. Liguori, Naples (1982)

5. Brylawski, T.H., Oxley, J.G.: The Tutte polynomial and its applications. In: White, N. (ed.) Matroid Applications, pp. 123–225. Cambridge Univ. Press, Cambridge (1992)

6. Chmutov, S., Pak, I.: The Kauffman bracket of virtual links and the Bollobás-Riordan polynomial. Mosc. Math. J. 7(3), 409–418 (2007)

7. Chmutov, S., Voltz, J.: Thistlethwaite’s theorem for virtual links. J. Knot Theory Ramifications 17(10), 1189–1198 (2008)

8. Dasbach, O.T., Futer, D., Kalfagianni, E., Lin, X.-S., Stoltzfus, N.W.: The Jones polynomial and graphs on surfaces. J. Combin. Theory Ser. B 98(2), 384–399 (2008)

9. Goldberg, L.A., Jerrum, M.: Inapproximability of the Tutte polynomial. Inform. and Comput. 206(7), 908–929 (2008)

10. Gross, J.L., Tucker, T.W.: Topological Graph Theory. John Wiley & Sons, Inc., New York (1987)

11. Huggett, S.: On tangles and matroids. J. Knot Theory Ramifications 14(7), 919–929 (2005)

12. Jaeger, F.: Tutte polynomials and link polynomials. Proc. Amer. Math. Soc. 103(2), 647–654 (1988)

13. Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108(1), 35–53 (1990)

14. Jerrum, M.: Approximating the Tutte polynomial. In: Grimmett, G.,McDiarmid, C. (eds.) Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh, pp. 144–161. Oxford University Press, Oxford (2007)

15. Kauffman, L.H.: State models and the Jones polynomial. Topology 26(3), 395–407 (1987)

16. Loebl, M., Moffatt, I.: The chromatic polynomial of fatgraphs and its categorification. Adv. Math. 217(4), 1558–1587 (2008)

17. Moffatt, I.: Knot invariants and the Bollobás-Riordan polynomial of embedded graphs. European J. Combin. 29(1), 95–107 (2008)

18. Seymour, P.D.: Decomposition of regular matroids. J. Combin. Theory Ser. B 28(3), 305–359 (1980)

19. Sokal, A.D.: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In: Webb, B.S. (ed.) Surveys in Combinatorics, 2005, pp. 173–226. Cambridge Univ. Press, Cambridge (2005)

20. Thistlethwaite,M.B.: A spanning tree expansion of the Jones polynomial. Topology 26(3), 297–309 (1987)

21. Traldi, L.: A dichromatic polynomial for weighted graphs and link polynomials. Proc. Amer. Math. Soc. 106(1), 279–286 (1989)

22. Woodall, D.R.: Tutte polynomial expansions for 2-separable graphs. Discrete Math. 247(1-3), 201–213 (2002)