Classification of regular embeddings of $n$-dimensional cubes

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

Journal of Algebraic Combinatorics, Tome 33 (2011) no. 2, pp. 215-238.

Résumé

Summary: 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 $\sigma $ of order 1 or 2 in the symmetric group $S _{ n }$ such that $\sigma $ 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$.

Détail

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