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 
 
 

 

Regular Cayley maps for cyclic groups


Authors: Marston D.E. Conder and Thomas W. Tucker
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
Published electronically: March 3, 2014
MathSciNet review: 3192608
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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}^{\rm o}M$ of all orientation-preserving automorphisms acts transitively on the arcs of $ M$. If $ \mathrm {Aut}^{\rm 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}^{\rm 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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1006/jsco.1996.0125
  • [2] 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 (2012b:57005), https://doi.org/10.1007/s10801-010-0242-8
  • [3] 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 (2010b:05084), https://doi.org/10.1016/j.jctb.2008.09.003
  • [4] 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 (2002f:05088), https://doi.org/10.1006/jctb.2000.2008
  • [5] 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 (2005e:20030), https://doi.org/10.1112/S0024610703005027
  • [6] 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 (2008d:05069), https://doi.org/10.1007/s10801-006-0037-0
  • [7] 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 (2007k:05086), https://doi.org/10.1016/j.jctb.2006.07.008
  • [8] 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 (2009k:05192), https://doi.org/10.1016/j.jctb.2008.07.002
  • [9] 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 (2010f:57005), https://doi.org/10.1017/S1446788708000827
  • [10] 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 (2011i:05092), https://doi.org/10.4171/JEMS/200
  • [11] 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
  • [12] Noboru Itô, Über das Produkt von zwei abelschen Gruppen, Math. Z. 62 (1955), 400-401 (German). MR 0071426 (17,125b)
  • [13] Robert Jajcay, Characterization and construction of Cayley graphs admitting regular Cayley maps, Discrete Math. 158 (1996), no. 1-3, 151-160. MR 1411114 (97d:05141), https://doi.org/10.1016/0012-365X(95)00076-9
  • [14] 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 (2003b:05079), https://doi.org/10.1016/S0012-365X(01)00081-4
  • [15] 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 (87a:05060), https://doi.org/10.1016/0095-8956(85)90060-7
  • [16] 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 (2011g:05072), https://doi.org/10.1112/plms/pdp061
  • [17] István Kovács, Classifying arc-transitive circulants, J. Algebraic Combin. 20 (2004), no. 3, 353-358. MR 2106966 (2005g:05068), https://doi.org/10.1023/B:JACO.0000048519.27295.3b
  • [18] I. Kovács, D.  Marušič and M. Muzychuk, Regular Cayley maps for dihedral groups of twice odd order, preprint.
  • [19] 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 (2007a:05058), https://doi.org/10.1016/j.ejc.2004.12.002
  • [20] 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 (2009f:05122), https://doi.org/10.1016/j.ejc.2007.06.023
  • [21] Young Soo Kwon, A classification of regular $ t$-balanced Cayley maps for cyclic groups, Discrete Math. 313 (2013), no. 5, 656-664. MR 3009432, https://doi.org/10.1016/j.disc.2012.12.012
  • [22] 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 (2006b:20002), https://doi.org/10.1007/s10801-005-6903-3
  • [23] 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 (91i:11001)
  • [24] 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 (2010d:05074), https://doi.org/10.1016/j.jctb.2008.09.006
  • [25] 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
  • [26] 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 (2006c:05075), https://doi.org/10.1007/s10114-004-0455-7

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05E18, 05C10, 20B25, 57M15

Retrieve articles in all journals with MSC (2010): 05E18, 05C10, 20B25, 57M15


Additional Information

Marston D.E. Conder
Affiliation: Department of Mathematics, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand

Thomas W. Tucker
Affiliation: Department of Mathematics, Colgate University, Hamilton, New York 13346

DOI: https://doi.org/10.1090/S0002-9947-2014-05933-3
Received by editor(s): March 2, 2011
Received by editor(s) in revised form: August 9, 2012
Published electronically: March 3, 2014
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society