Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 


Twisted duality for embedded graphs

Authors: Joanna A. Ellis-Monaghan and Iain Moffatt
Journal: Trans. Amer. Math. Soc. 364 (2012), 1529-1569
MSC (2010): Primary 05C10; Secondary 05C31
Published electronically: October 24, 2011
MathSciNet review: 2869185
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider two operations on an edge of an embedded graph (or equivalently a ribbon graph): giving a half-twist to the edge, and taking the partial dual with respect to the edge. These two operations give rise to an action of $ {S_3}^{\vert E(G)\vert}$, the ribbon group, on $ G$. The action of the ribbon group on embedded graphs extends the concepts of duality, partial duality, and Petrie duality. We show that this ribbon group action gives a complete characterization of duality in that if $ G$ is any cellularly embedded graph with medial graph $ G_m$, then the orbit of $ G$ under the group action is precisely the set of all graphs with medial graphs isomorphic (as abstract graphs) to $ G_m$. We provide characterizations of special sets of twisted duals (such as the partial duals) of embedded graphs in terms of medial graphs, and we show how different kinds of graph isomorphism give rise to these various notions of duality. The ribbon group action then leads to a deeper understanding of the properties of, and relationships among, various graph polynomials via the generalized transition polynomial which interacts naturally with the ribbon group action.

References [Enhancements On Off] (What's this?)

  • 1. L. M. Aldeman, Molecular computation of solutions to combinatorial problems, Science, 266 no. 5187 (1994), 1021-1024.
  • 2. M. Aigner, The Penrose polynomial of a plane graph, Math. Ann. 307 (1997), no. 2, 173-189. MR 1428870 (98b:05040)
  • 3. B. Bollobás and O. Riordan, A polynomial for graphs on orientable surfaces, Proc. London Math. Soc. 83 (2001), 513-531. MR 1851080 (2002f:05056)
  • 4. B. Bollobás and O. Riordan, A polynomial of graphs on surfaces, Math. Ann. 323 (2002), 81-96. MR 1906909 (2003b:05052)
  • 5. S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobas-Riordan polynomial, J. Combin. Theory Ser. B, 99 (2009), 617-638. MR 2507944 (2010f:05046)
  • 6. O. T. Dasbach, D. Futer, E. Kalfagianni, X.-S. Lin, N. W. Stoltzfus, Alternating sum formulae for the determinant and other link invariants, J. Combin. Theory Ser. B, 98 (2) (2008), 384-399. MR 2389605 (2009d:57020)
  • 7. J. A. Ellis-Monaghan and I. Moffatt, A Penrose polynomial for embedded graphs, arXiv:1106.5279.
  • 8. J. A. Ellis-Monaghan and I. Moffatt, Evaluations of topological Tutte polynomials, arXiv:1108.3321.
  • 9. J. A. Ellis-Monaghan, I. Sarmiento, Generalized transition polynomials, Congr. Numer. 155 (2002) 57-69. MR 1980048 (2004f:05106)
  • 10. J. A. Ellis-Monaghan and I. Sarmiento, A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan, European J. Combin. 32 (2011) 782-794.
  • 11. H. Fleischner, Eulerian graphs and related topics, Part 1, Volume I, Ann. Discrete Math. 45 (1990).
  • 12. H. Fleischner, Eulerian graphs and related topics, Part 1, Volume 2, Ann. Discrete Math. 50 (1990). MR 1113484 (92f:05066)
  • 13. J. L. Gross, T. W. Tucker, Topological graph theory, Wiley-Interscience Publication, 1987. MR 898434 (88h:05034)
  • 14. F. Jaeger, On transition polynomials of $ 4$-regular graphs, In: Cycles and rays (Montreal, PQ, 1987), 123-150, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 301, Kluwer Acad. Publ., Dordrecht, 1990. MR 1096990 (92c:05059)
  • 15. F. Jaeger, On transition polynomials of $ 4$-regular graphs, In: Cycles and Rays (Hahn et al, eds.) Kluwer, (1990), 123-150. MR 1096990 (92c:05059)
  • 16. A. Kotzig, Eulerian lines in finite $ 4$-valent graphs and their transformations. 1968 Theory of Graphs (Proc. Colloq., Tihany, 1966) pp. 219-230 Academic Press, New York. MR 0248043 (40:1298)
  • 17. T. Krajewski, V. Rivasseau, A. Tanasa, Zhituo Wang, Topological Graph Polynomials and Quantum Field Theory, Part II: Mehler Kernel Theories, Ann. Henri Poincaré 12 (2011) 1-63. MR 2785137
  • 18. T.H. LaBean, H. Li, Constructing novel materials with DNA, Nano Today, 2 no. 2 (2007), 26-35.
  • 19. M. Las Vergnas, Eulerian circuits of $ 4$-valent graphs imbedded in surfaces. Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 451-477, Colloq. Math. Soc. Jonos Bolyai, 25, North-Holland, Amsterdam-New York, 1981. MR 642057 (83a:05087)
  • 20. M. Las Vergnas, Le polynôme de Martin d'un Graphe Eulerien, Ann. Discrete Math. 17 (1983) 397-411. MR 841322 (87i:05137)
  • 21. I. Moffatt, A characterization of partially dual graphs, J. Graph Theory, 67 (2011) 198-217.
  • 22. I. Moffatt, Partial duals of plane graphs, separability and the graphs of knots, arXiv:1007.4219.
  • 23. B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins University Press, 2001. MR 1844449 (2002e:05050)
  • 24. R. Penrose, Applications of negative dimensional tensors. 1971 Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) pp. 221-244 Academic Press, London. MR 0281657 (43:7372)
  • 25. W. T. Tutte, A ring in graph theory. Proc. Cambridge Phil. Soc., 43, 26-40 (1947). MR 0018406 (8:284k)
  • 26. W. T. Tutte, A contribution to the theory of chromatic polynomials. Can. J. Math., 6, 80-91 (1954). MR 0061366 (15:814c)
  • 27. W. T. Tutte, On dichromatic polynomials. J. Combin. Theory, 2, 301- 320 (1967).
  • 28. S. E. Wilson, Operators over regular maps. Pacific J. Math. 81 no. 2, 559568 (1979). MR 547621 (81a:57004)
  • 29. H. Yan, S. H. Park, G. Finkelstein, J. Reif, T. LaBean, DNA-templated self-assembly of protein arrays and highly conductive nanowires, Science, 301 (2003), 1882-1884.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C10, 05C31

Retrieve articles in all journals with MSC (2010): 05C10, 05C31

Additional Information

Joanna A. Ellis-Monaghan
Affiliation: Department of Mathematics, Saint Michael’s College, 1 Winooski Park, Colchester, Vermont 05439

Iain Moffatt
Affiliation: Department of Mathematics and Statistics, University of South Alabama, Mobile, Alabama 36688

Received by editor(s): April 21, 2010
Received by editor(s) in revised form: October 12, 2010, and December 17, 2010
Published electronically: October 24, 2011
Additional Notes: The work of the first author was supported by the National Science Foundation (NSF) under grant number DMS-1001408, by the Vermont Space Grant Consortium through the National Aeronautics and Space Administration (NASA), and by the Vermont Genetics Network through Grant Number P20 RR16462 from the INBRE Program of the National Center for Research Resources (NCRR), a component of the National Institutes of Health (NIH). This paper’s contents are solely the responsibility of the authors and do not necessarily represent the official views of the NSF, NASA, NCRR, or NIH
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.