Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-08T07:29:47.108Z Has data issue: false hasContentIssue false
  • English
  • Français

New dualities from old: generating geometric, Petrie, and Wilson dualities and trialities of ribbon graphs

Part of: Graph theory Low-dimensional topology

Published online by Cambridge University Press:  07 October 2021

Lowell Abrams  and
Joanna A. Ellis-Monaghan
Lowell Abrams*
Affiliation:
University Writing Program and Department of Mathematics, George Washington University, 2115 G Street NW, Washington, DC 20052, USA
Joanna A. Ellis-Monaghan
Affiliation:
Korteweg-de Vries Institute for Mathematics, University of Amsterdam, Science Park 105-107, 1098XG Amsterdam, The Netherlands
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We define a new ribbon group action on ribbon graphs that uses a semidirect product of a permutation group and the original ribbon group of Ellis-Monaghan and Moffatt to take (partial) twists and duals, or twuals, of ribbon graphs. A ribbon graph is a fixed point of this new ribbon group action if and only if it is isomorphic to one of its (partial) twuals. This extends the original ribbon group action, which only used the canonical identification of edges, to the more natural setting of self-twuality up to isomorphism. We then show that every ribbon graph has in its orbit an orientable embedded bouquet and prove that the (partial) twuality properties of these bouquets propagate through their orbits. Thus, we can determine (partial) twualities via these one vertex graphs, for which checking isomorphism reduces simply to checking dihedral group symmetries. Finally, we apply the new ribbon group action to generate all self-trial ribbon graphs on up to seven edges, in contrast with the few, large, very high-genus, self-trial regular maps found by Wilson, and by Jones and Poultin. We also show how the automorphism group of a ribbon graph yields self-dual, -petrial or –trial graphs in its orbit, and produce an infinite family of self-trial graphs that do not arise as covers or parallel connections of regular maps, thus answering a question of Jones and Poulton.

Keywords

Embedded graphribbon graphdualityPetrie dualitytrialitytwualityregular mapWilson grouptwistpartial dual

MSC classification

Primary: 05C10: Planar graphs; geometric and topological aspects of graph theory
Secondary: 05C25: Graphs and abstract algebra (groups, rings, fields, etc.) 57M15: Relations with graph theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 31 , Issue 4 , July 2022 , pp. 574 - 597
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Archdeacon, D. and Richter, R. B. (1992) Construction and classification of self-dual spherical polyhedra. J. Comb. Theory Ser. B 54 37–63.CrossRefGoogle Scholar
Chmutov, S. (2009) Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial. J. Comb. Theory Ser. B 99 617–638.CrossRefGoogle Scholar
Chun, C., Moffatt, I., Noble, S. and Rueckriemen, R. (2019) Matroids, delta-matroids and embedded graphs. J. Comb. Theory Ser. A 167 7–59.CrossRefGoogle Scholar
Chun, C., Moffatt, I., Noble, S. and Rueckriemen, R. (2019) On the interplay between embedded graphs and delta-matroids. Proc. Lond. Math. Soc. 118(3) 675–700.CrossRefGoogle Scholar
Conder, M. D. E. (2009) Regular maps and hypermaps of Euler characteristic $-1$ to $-200$ . J. Comb. Theory Ser. B 99(2) 455–459.CrossRefGoogle Scholar
Ellingham, M. N. and Zha, X. (2017) Partial duality and closed 2-cell embeddings. J. Comb. 8(2) 227–254.Google Scholar
Ellis-Monaghan, J. and Moffatt, I. (2012) Twisted duality and polynomials of embedded graphs. Trans. Amer. Math. Soc. 364 1529–1569.CrossRefGoogle Scholar
Ellis-Monaghan, J. and Moffatt, I. (2013) Graphs on Surfaces: Twisted Duality, Polynomials, and Knots. SpringerBriefs in Mathematics.CrossRefGoogle Scholar
Ellis-Monaghan, J. and Moffatt, I. (2013) A Penrose polynomial for embedded graphs. Eur. J. Comb. 34 424–445.CrossRefGoogle Scholar
Ellis-Monaghan, J. and Moffatt, I. (2015) Valuations of topological Tutte polynomials. Comb. Prob. Comput. 24(3) 556–583.CrossRefGoogle Scholar
Huggett, S. and Moffatt, I. (2013) Bipartite partial duals and circuits in medial graphs. Combinatorica 33(2) 231–252.CrossRefGoogle Scholar
Jones, G. A. and Poulton, A. (2010) Maps admitting trialities but not dualities. Eur. J. Comb. 31 1805–1818.CrossRefGoogle Scholar
Jones, G. A., Streit, M. and Wolfart, J. (2010) Wilsons map operations on regular dessins and cyclotomic fields of definition. Proc. Lond. Math. Soc. (3) 100(2) 510–532.CrossRefGoogle Scholar
Krushkal, V. (2010) Graphs, links, and duality on surfaces. Combin. Probab. Comput. 20 267–287.Google Scholar
Lins, S. (1980) Graphs of Maps, Ph.D. thesis, University of Waterloo.Google Scholar
Lins, S. (1982) Graph-encoded maps. J. Comb. Theory Ser. B 32(2) 171–181.CrossRefGoogle Scholar
Metsidik, M. and Jin, X. (2018) Eulerian partial duals of plane graphs. J. Graph Theory 87(4) 509–515.CrossRefGoogle Scholar
Mohar, B. and Thomassen, C. (2001) Graphs on Surfaces. Johns Hopkins University Press, Baltimore and London.Google Scholar
Moffatt, I. (2016) Ribbon graph minors and low-genus partial duals. Ann. Comb. 20(2) 373–378. CrossRefGoogle Scholar
Nijenhuis, A. and Wilf, H. (1979) The enumeration of connected graphs and linked diagrams. J. Combin. Theory A 27 356–359.CrossRefGoogle Scholar
Orbanić, A., Pellicer, D. and Weiss, A. I. (2010) Map operations and k-orbit maps. J. Comb. Theory Ser. A 117(4) 429.CrossRefGoogle Scholar
Richter, B., Širáň, J. and Wang, Y. (2012) Self-dual and self-Petrie-dual regular maps. J. Graph Theory 69 152–159.CrossRefGoogle Scholar
Robertson, N. (1971) Pentagon-Generated trivalent graphs with girth 5. Canad. J. Math. 23(1) 36–47.CrossRefGoogle Scholar
Servatius, B. and Servatius, H. (1995) The 24 symmetry pairings of self-dual maps on the sphere. Discrete Math. 140(1–3) 167–183.CrossRefGoogle Scholar
Servatius, B. and Servatius, H. (1996) Self-dual graphs. Discrete Math. 149(1–3) 223–232.CrossRefGoogle Scholar
Wilson, S. E. (1979) Operators over regular maps. Pac. J. Math. 81 559–568.CrossRefGoogle Scholar
Tutte, W. T. (1948) The dissection of equilateral triangles into equilateral triangles. Proc. Cambridge Philos. Soc. 44 463–482.Google Scholar
Tutte, W. T. (1975) Duality and trinity. In Infinite and Finite Sets (Colloq., Keszthely, 1973; Dedicated to P. Erdös on his 60th Birthday), Vol. III, pp. 1459–1472. Colloquia Mathematica Societatis JÁnos Bolyai, Vol. 10, North-Holland, Amsterdam.Google Scholar