Regular Cayley maps for cyclic groups
HTML articles powered by AMS MathViewer
- by Marston D.E. Conder and Thomas W. Tucker PDF
- Trans. Amer. Math. Soc. 366 (2014), 3585-3609 Request permission
Abstract:
An orientably-regular map $M$ is a 2-cell embedding of a connected graph in a closed, orientable surface, with the property that the group $\mathrm {Aut}^\textrm {o}M$ of all orientation-preserving automorphisms acts transitively on the arcs of $M$. If $\mathrm {Aut}^\textrm {o}M$ contains a subgroup $A$ that acts regularly on the vertex set, then $M$ is called a regular Cayley map for $A$. In this paper, we answer a question of recent interest by providing a complete classification of the regular Cayley maps for the cyclic group $C_n$, for every possible order $n$. This is the first such classification for any infinite family of groups. The approach used is entirely algebraic and does not involve skew morphisms (but leads to a classification of all skew morphisms which have an orbit that is closed under inverses and generates the group). A key step is the use of a generalisation by Conder and Isaacs (2004) of Ito’s theorem on group factorisations, to help determine the isomorphism type of $\mathrm {Aut}^\textrm {o}M$. This group is shown to be a cyclic extension of a cyclic or dihedral group, dependent on $n$ and a single parameter $r$, which is a unit modulo $n$ that satisfies technical number-theoretic conditions. For each $n$, we enumerate all such $r$, and then in terms of $r$, we find the valence and covalence of the map, and determine whether or not the map is reflexible, and whether it has a representation as a balanced, anti-balanced or $t$-balanced regular Cayley map.References
- Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
- Domenico A. Catalano, Marston D. E. Conder, Shao Fei Du, Young Soo Kwon, Roman Nedela, and Steve Wilson, Classification of regular embeddings of $n$-dimensional cubes, J. Algebraic Combin. 33 (2011), no. 2, 215–238. MR 2765323, DOI 10.1007/s10801-010-0242-8
- Marston D. E. Conder, Regular maps and hypermaps of Euler characteristic $-1$ to $-200$, J. Combin. Theory Ser. B 99 (2009), no. 2, 455–459. MR 2482963, DOI 10.1016/j.jctb.2008.09.003
- Marston Conder and Peter Dobcsányi, Determination of all regular maps of small genus, J. Combin. Theory Ser. B 81 (2001), no. 2, 224–242. MR 1814906, DOI 10.1006/jctb.2000.2008
- M. D. E. Conder and I. M. Isaacs, Derived subgroups of products of an abelian and a cyclic subgroup, J. London Math. Soc. (2) 69 (2004), no. 2, 333–348. MR 2040608, DOI 10.1112/S0024610703005027
- Marston Conder, Robert Jajcay, and Thomas Tucker, Regular Cayley maps for finite abelian groups, J. Algebraic Combin. 25 (2007), no. 3, 259–283. MR 2317333, DOI 10.1007/s10801-006-0037-0
- Marston Conder, Robert Jajcay, and Tom Tucker, Regular $t$-balanced Cayley maps, J. Combin. Theory Ser. B 97 (2007), no. 3, 453–473. MR 2305898, DOI 10.1016/j.jctb.2006.07.008
- Marston D. E. Conder, Young Soo Kwon, and Jozef Širáň, Reflexibility of regular Cayley maps for abelian groups, J. Combin. Theory Ser. B 99 (2009), no. 1, 254–260. MR 2467830, DOI 10.1016/j.jctb.2008.07.002
- Marston Conder, Primož Potočnik, and Jozef Širáň, Regular hypermaps over projective linear groups, J. Aust. Math. Soc. 85 (2008), no. 2, 155–175. MR 2470535, DOI 10.1017/S1446788708000827
- Marston D. E. Conder, Jozef Širáň, and Thomas W. Tucker, The genera, reflexibility and simplicity of regular maps, J. Eur. Math. Soc. (JEMS) 12 (2010), no. 2, 343–364. MR 2608943, DOI 10.4171/JEMS/200
- Jonathan L. Gross and Thomas W. Tucker, Topological graph theory, Dover Publications, Inc., Mineola, NY, 2001. Reprint of the 1987 original [Wiley, New York; MR0898434 (88h:05034)] with a new preface and supplementary bibliography. MR 1855951
- Noboru Itô, Über das Produkt von zwei abelschen Gruppen, Math. Z. 62 (1955), 400–401 (German). MR 71426, DOI 10.1007/BF01180647
- Robert Jajcay, Characterization and construction of Cayley graphs admitting regular Cayley maps, Discrete Math. 158 (1996), no. 1-3, 151–160. MR 1411114, DOI 10.1016/0012-365X(95)00076-9
- Robert Jajcay and Jozef Širáň, Skew-morphisms of regular Cayley maps, Discrete Math. 244 (2002), no. 1-3, 167–179. Algebraic and topological methods in graph theory (Lake Bled, 1999). MR 1844030, DOI 10.1016/S0012-365X(01)00081-4
- Lynne D. James and Gareth A. Jones, Regular orientable imbeddings of complete graphs, J. Combin. Theory Ser. B 39 (1985), no. 3, 353–367. MR 815402, DOI 10.1016/0095-8956(85)90060-7
- Gareth A. Jones, Regular embeddings of complete bipartite graphs: classification and enumeration, Proc. Lond. Math. Soc. (3) 101 (2010), no. 2, 427–453. MR 2679697, DOI 10.1112/plms/pdp061
- István Kovács, Classifying arc-transitive circulants, J. Algebraic Combin. 20 (2004), no. 3, 353–358. MR 2106966, DOI 10.1023/B:JACO.0000048519.27295.3b
- I. Kovács, D. Marušič and M. Muzychuk, Regular Cayley maps for dihedral groups of twice odd order, preprint.
- Jin Ho Kwak, Young Soo Kwon, and Rongquan Feng, A classification of regular $t$-balanced Cayley maps on dihedral groups, European J. Combin. 27 (2006), no. 3, 382–393. MR 2206474, DOI 10.1016/j.ejc.2004.12.002
- Jin Ho Kwak and Ju-Mok Oh, A classification of regular $t$-balanced Cayley maps on dicyclic groups, European J. Combin. 29 (2008), no. 5, 1151–1159. MR 2419219, DOI 10.1016/j.ejc.2007.06.023
- Young Soo Kwon, A classification of regular $t$-balanced Cayley maps for cyclic groups, Discrete Math. 313 (2013), no. 5, 656–664. MR 3009432, DOI 10.1016/j.disc.2012.12.012
- Cai Heng Li, Permutation groups with a cyclic regular subgroup and arc transitive circulants, J. Algebraic Combin. 21 (2005), no. 2, 131–136. MR 2142403, DOI 10.1007/s10801-005-6903-3
- Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An introduction to the theory of numbers, 5th ed., John Wiley & Sons, Inc., New York, 1991. MR 1083765
- Ju-Mok Oh, Regular $t$-balanced Cayley maps on semi-dihedral groups, J. Combin. Theory Ser. B 99 (2009), no. 2, 480–493. MR 2482966, DOI 10.1016/j.jctb.2008.09.006
- Jozef Širáň and Thomas W. Tucker, Symmetric maps, Topics in topological graph theory, Encyclopedia Math. Appl., vol. 128, Cambridge Univ. Press, Cambridge, 2009, pp. 199–224. MR 2581547
- Yan Wang and Rong Quan Feng, Regular balanced Cayley maps for cyclic, dihedral and generalized quaternion groups, Acta Math. Sin. (Engl. Ser.) 21 (2005), no. 4, 773–778. MR 2156952, DOI 10.1007/s10114-004-0455-7
Additional Information
- Marston D.E. Conder
- Affiliation: Department of Mathematics, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand
- MR Author ID: 50940
- ORCID: 0000-0002-0256-6978
- Thomas W. Tucker
- Affiliation: Department of Mathematics, Colgate University, Hamilton, New York 13346
- MR Author ID: 175090
- ORCID: 0000-0002-7868-6925
- Received by editor(s): March 2, 2011
- Received by editor(s) in revised form: August 9, 2012
- Published electronically: March 3, 2014
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 366 (2014), 3585-3609
- MSC (2010): Primary 05E18; Secondary 05C10, 20B25, 57M15
- DOI: https://doi.org/10.1090/S0002-9947-2014-05933-3
- MathSciNet review: 3192608