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)



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. Martin Aigner, The Penrose polynomial of a plane graph, Math. Ann. 307 (1997), no. 2, 173–189. MR 1428870,
  • 3. Béla Bollobás and Oliver Riordan, A polynomial invariant of graphs on orientable surfaces, Proc. London Math. Soc. (3) 83 (2001), no. 3, 513–531. MR 1851080,
  • 4. Béla Bollobás and Oliver Riordan, A polynomial of graphs on surfaces, Math. Ann. 323 (2002), no. 1, 81–96. MR 1906909,
  • 5. Sergei Chmutov, Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial, J. Combin. Theory Ser. B 99 (2009), no. 3, 617–638. MR 2507944,
  • 6. Oliver T. Dasbach, David Futer, Efstratia Kalfagianni, Xiao-Song Lin, and Neal W. Stoltzfus, The Jones polynomial and graphs on surfaces, J. Combin. Theory Ser. B 98 (2008), no. 2, 384–399. MR 2389605,
  • 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. Joanna A. Ellis-Monaghan and Irasema Sarmiento, Generalized transition polynomials, Proceedings of the Thirty-third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002), 2002, pp. 57–69. MR 1980048
  • 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. Herbert Fleischner, Eulerian graphs and related topics. Part 1. Vol. 2, Annals of Discrete Mathematics, vol. 50, North-Holland Publishing Co., Amsterdam, 1991. MR 1113484
  • 13. Jonathan L. Gross and Thomas W. Tucker, Topological graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1987. A Wiley-Interscience Publication. MR 898434
  • 14. F. Jaeger, On transition polynomials of 4-regular graphs, Cycles and rays (Montreal, PQ, 1987) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 301, Kluwer Acad. Publ., Dordrecht, 1990, pp. 123–150. MR 1096990
  • 15. F. Jaeger, On transition polynomials of 4-regular graphs, Cycles and rays (Montreal, PQ, 1987) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 301, Kluwer Acad. Publ., Dordrecht, 1990, pp. 123–150. MR 1096990
  • 16. A. Kotzig, Eulerian lines in finite 4-valent graphs and their transformations., Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 219–230. MR 0248043
  • 17. Thomas Krajewski, Vincent Rivasseau, and Fabien Vignes-Tourneret, Topological graph polynomial and quantum field theory Part II: Mehler kernel theories, Ann. Henri Poincaré 12 (2011), no. 3, 483–545. 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) Colloq. Math. Soc. János Bolyai, vol. 25, North-Holland, Amsterdam-New York, 1981, pp. 451–477. MR 642057
  • 20. Michel Las Vergnas, Le polynôme de Martin d’un graphe eulérien, Combinatorial mathematics (Marseille-Luminy, 1981) North-Holland Math. Stud., vol. 75, North-Holland, Amsterdam, 1983, pp. 397–411 (French, with English summary). MR 841322
  • 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. Bojan Mohar and Carsten Thomassen, Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001. MR 1844449
  • 24. Roger Penrose, Applications of negative dimensional tensors, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press, London, 1971, pp. 221–244. MR 0281657
  • 25. W. T. Tutte, A ring in graph theory, Proc. Cambridge Philos. Soc. 43 (1947), 26–40. MR 0018406
  • 26. W. T. Tutte, A contribution to the theory of chromatic polynomials, Canadian J. Math. 6 (1954), 80–91. MR 0061366
  • 27. W. T. Tutte, On dichromatic polynomials. J. Combin. Theory, 2, 301- 320 (1967).
  • 28. Stephen E. Wilson, Operators over regular maps, Pacific J. Math. 81 (1979), no. 2, 559–568. MR 547621
  • 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.

American Mathematical Society