ELibM Journals • ELibM Home • EMIS Home • EMIS Mirrors

  EMIS Electronic Library of Mathematics (ELibM)
The Open Access Repository of Mathematics
  EMIS ELibM Electronic Journals

JOURNAL OF
ALGEBRAIC
COMBINATORICS
  Editors-in-chief: C. A. Athanasiadis, T. Lam, A. Munemasa, H. Van Maldeghem
ISSN 0925-9899 (print) • ISSN 1572-9192 (electronic)
 

Classification of regular embeddings of n-dimensional cubes

Domenico A. Catalano , Marston D.E. Conder , Shao Fei Du , Young Soo Kwon , Roman Nedela and Steve Wilson

DOI: 10.1007/s10801-010-0242-8

Abstract

An orientably-regular map is a 2-cell embedding of a connected graph or multigraph into an orientable surface, such that the group of all orientation-preserving automorphisms of the embedding has a single orbit on the set of all arcs (incident vertex-edge pairs). Such embeddings of the n-dimensional cubes Q n were classified for all odd n by Du, Kwak and Nedela in 2005, and in 2007, Jing Xu proved that for n=2 m where m is odd, they are precisely the embeddings constructed by Kwon in 2004. Here, we give a classification of orientably-regular embeddings of Q n for all n. In particular, we show that for all even n (=2 m), these embeddings are in one-to-one correspondence with elements σ  of order 1 or 2 in the symmetric group S n such that σ  fixes n, preserves the set of all pairs B i ={ i, i+ m} for 1\leq  i\leq  m, and induces the same permutation on this set as the permutation B i \rightarrowtail  B f( i) for some additive bijection f:\Bbb Z m \rightarrow \Bbb Z m . We also give formulae for the numbers of embeddings that are reflexible and chiral, respectively, showing that the ratio of reflexible to chiral embeddings tends to zero for large even n.

Pages: 215–238

Keywords: keywords hypercubes; cubes; regular maps; regular embeddings; chiral

Full Text: PDF

References

1. Biggs, N.L.: Classification of complete maps on orientable surfaces. Rend. Mat. 4(6), 132-138 (1971)
2. Bosma, W., Cannon, J., Playoust, C.: The MAGMA algebra system I: the user language. J. Symb. Comput. 24, 235-265 (1997)
3. Catalano, D.A., Nedela, R.: A characterization of regular embeddings of n-dimensional cubes. Discrete Math. (2010, to appear).
4. Conder, M.D.E.: Regular maps and hypermaps of Euler characteristic - 1 to -
200. J. Comb. Theory Ser. B 99, 455-459 (2009). With associated lists of computational data available at the website J Algebr Comb (2011) 33: 215-238
5. Conder, M.D.E., Dobcsányi, P.: Determination of all regular maps of small genus. J. Comb. Theory Ser. B 81, 224-242 (2001)
6. Du, S.F., Jones, G.A., Kwak, J.H., Nedela, R., Škoviera, M.: Regular embeddings of Kn,n where n is a power of
2. I: Metacyclic case. Eur. J. Comb. 28, 1595-1609 (2007)
7. Du, S.F., Jones, G.A., Kwak, J.H., Nedela, R., Škoviera, M.: Regular embeddings of Kn,n where n is a power of
2. II: Non-metacyclic case. Eur. J. Comb. (2010, to appear).
8. Du, S.F., Kwak, J.H., Nedela, R.: Regular maps with pq vertices. J. Algebraic Comb. 19, 123-141 (2004)
9. Du, S.F., Kwak, J.H., Nedela, R.: Classification of regular embeddings of hypercubes of odd dimension. Discrete Math. 307, 119-124 (2007)
10. Du, S.F., Kwak, J.H., Nedela, R.: Regular embeddings of complete multipartite graphs. Eur. J. Comb. 26, 505-519 (2005)
11. The GAP Group: GAP-Groups Algorithms and Programming, Version 4.3 (2002).
12. Gardiner, A., Nedela, R., Širá\check n, J., Škoviera, M.: Characterization of graphs which underlie regular maps on closed surfaces. J. Lond. Math. Soc. 59, 100-108 (1999)
13. Heffter, L.: Über metacyclic Gruppen und Nachbarconfigurationen. Math. Ann. 50, 261-268 (1898)
14. James, L.D., Jones, G.A.: Regular orientable imbeddings of complete graphs. J. Comb. Theory Ser. B 39, 353-367 (1985)
15. Jones, G.A.: Regular embeddings of complete bipartite graphs: classification and enumeration. Proc. Lond. Math. Soc. (to appear).
16. Jones, G.A., Nedela, R., Škoviera, M.: Regular embeddings of Kn,n where n is an odd prime power. Eur. J. Comb. 28, 1863-1875 (2007)
17. Jones, G.A., Nedela, R., Škoviera, M.: Complete bipartite graphs with a unique regular embedding. J. Comb. Theory Ser. B 98, 241-248 (2008)
18. Jones, G.A., Singerman, D.: Belyi functions, hypermaps, and Galois groups. Bull. Lond. Math. Soc. 28, 561-590 (1996)
19. Kwak, J.H., Kwon, Y.S.: Regular orientable embeddings of complete bipartite graphs. J. Graph Theory 50, 105-122 (2005)
20. Kwak, J.H., Kwon, Y.S.: Classification of reflexible regular embeddings and self-Petrie dual regular embeddings of complete bipartite graphs. Discrete Math. 308, 2156-2166 (2008)
21. Kwon, Y.S.: New regular embeddings of n-cubes Qn. J. Graph Theory 46, 297-312 (2004)
22. Kwon, Y.S., Nedela, R.: Non-existence of nonorientable regular embeddings of n-dimensional cubes. Discrete Math. 307, 511-516 (2007)
23. Nedela, R., Škoviera, M.: Regular maps of canonical double coverings of graphs. J. Comb. Theory Ser. B 67, 249-277 (1996)
24. Nedela, R., Škoviera, M.: Regular maps from voltage assignments and exponent groups. Eur. J. Comb. 18, 807-823 (1997)
25. Nedela, R., Škoviera, M., Zlatoš, A.: Bipartite maps, Petrie duality and exponent groups. Atti Semin. Mat. Fis. Univ. Modena 49 (Suppl.), 109-133 (2001). Dedicated to the memory of Professor M. Pezzana (in Italian)
26. Nedela, R., Škoviera, M., Zlatoš, A.: Regular embeddings of complete bipartite graphs. Discrete Math.



© 1992–2009 Journal of Algebraic Combinatorics
© 2012 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition