Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Twisted duality for embedded graphs
HTML articles powered by AMS MathViewer

by Joanna A. Ellis-Monaghan and Iain Moffatt PDF
Trans. Amer. Math. Soc. 364 (2012), 1529-1569 Request permission

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}^{|E(G)|}$, 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
  • L. M. Aldeman, Molecular computation of solutions to combinatorial problems, Science, 266 no. 5187 (1994), 1021-1024.
  • Martin Aigner, The Penrose polynomial of a plane graph, Math. Ann. 307 (1997), no. 2, 173–189. MR 1428870, DOI 10.1007/s002080050030
  • 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, DOI 10.1112/plms/83.3.513
  • Béla Bollobás and Oliver Riordan, A polynomial of graphs on surfaces, Math. Ann. 323 (2002), no. 1, 81–96. MR 1906909, DOI 10.1007/s002080100297
  • 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, DOI 10.1016/j.jctb.2008.09.007
  • 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, DOI 10.1016/j.jctb.2007.08.003
  • J. A. Ellis-Monaghan and I. Moffatt, A Penrose polynomial for embedded graphs, arXiv:1106.5279.
  • J. A. Ellis-Monaghan and I. Moffatt, Evaluations of topological Tutte polynomials, arXiv:1108.3321.
  • 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
  • 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.
  • H. Fleischner, Eulerian graphs and related topics, Part 1, Volume I, Ann. Discrete Math. 45 (1990).
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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, DOI 10.1007/s00023-011-0087-2
  • T.H. LaBean, H. Li, Constructing novel materials with DNA, Nano Today, 2 no. 2 (2007), 26-35.
  • 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
  • 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
  • I. Moffatt, A characterization of partially dual graphs, J. Graph Theory, 67 (2011) 198–217.
  • I. Moffatt, Partial duals of plane graphs, separability and the graphs of knots, arXiv:1007.4219.
  • Bojan Mohar and Carsten Thomassen, Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001. MR 1844449
  • 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
  • W. T. Tutte, A ring in graph theory, Proc. Cambridge Philos. Soc. 43 (1947), 26–40. MR 18406, DOI 10.1017/s0305004100023173
  • W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80–91. MR 61366, DOI 10.4153/cjm-1954-010-9
  • W. T. Tutte, On dichromatic polynomials. J. Combin. Theory, 2, 301- 320 (1967).
  • Stephen E. Wilson, Operators over regular maps, Pacific J. Math. 81 (1979), no. 2, 559–568. MR 547621
  • 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
  • Email: jellis-monaghan@smcvt.edu
  • Iain Moffatt
  • Affiliation: Department of Mathematics and Statistics, University of South Alabama, Mobile, Alabama 36688
  • Email: imoffatt@jaguar1.usouthal.edu
  • 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
  • © Copyright 2011 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Trans. Amer. Math. Soc. 364 (2012), 1529-1569
  • MSC (2010): Primary 05C10; Secondary 05C31
  • DOI: https://doi.org/10.1090/S0002-9947-2011-05529-7
  • MathSciNet review: 2869185