×

Classification of regular embeddings of \(n\)-dimensional cubes. (English) Zbl 1222.05032

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 S. F. Du, J. Ho and R. Nedela [Eur. J. Comb. 26, No. 3–4, 505–519 (2005; Zbl 1057.05026)], and in 2007 by J. Xu [Sci. China, Ser. A 50, No. 12, 1673–1679 (2007; Zbl 1133.05023)] proved that for \(n=2m\) where \(m\) is odd, they are precisely the embeddings constructed by Y. S. Kwon [J. Graph Theory 46, No. 4, 297–312 (2004; Zbl 1046.05022)]. Here, we give a classification of orientably-regular embeddings of \(Q_{n}\) for all \(n\). In particular, we show that for all even \(n (=2m)\), 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:\mathbb Z_{m}\rightarrow \mathbb 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\).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C65 Hypergraphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Software:

Magma; GAP
Full Text: DOI

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) · Zbl 0898.68039 · doi:10.1006/jsco.1996.0125
[3] Catalano, D.A., Nedela, R.: A characterization of regular embeddings of n-dimensional cubes. Discrete Math. (2010, to appear). doi:10.1016/j.disc.2010.05.010 · Zbl 1255.05054
[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 http://www.math.auckland.ac.nz/ conder/hypermaps.html · Zbl 1205.05106 · doi:10.1016/j.jctb.2008.09.003
[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) · Zbl 1028.05045 · doi:10.1006/jctb.2000.2008
[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) · Zbl 1123.05029 · doi:10.1016/j.ejc.2006.08.012
[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). doi:10.1016/j.ejc.2010.01.009 · Zbl 1221.05079
[8] Du, S.F., Kwak, J.H., Nedela, R.: Regular maps with pq vertices. J. Algebraic Comb. 19, 123-141 (2004) · Zbl 1042.05027 · doi:10.1023/B:JACO.0000023003.69690.18
[9] Du, S.F., Kwak, J.H., Nedela, R.: Classification of regular embeddings of hypercubes of odd dimension. Discrete Math. 307, 119-124 (2007) · Zbl 1112.05027 · doi:10.1016/j.disc.2006.05.035
[10] Du, S.F., Kwak, J.H., Nedela, R.: Regular embeddings of complete multipartite graphs. Eur. J. Comb. 26, 505-519 (2005) · Zbl 1057.05026 · doi:10.1016/j.ejc.2004.02.010
[11] The GAP Group: GAP—Groups Algorithms and Programming, Version 4.3 (2002). http://www.gap-system.org
[12] Gardiner, A., Nedela, R., Širáň, J., Škoviera, M.: Characterization of graphs which underlie regular maps on closed surfaces. J. Lond. Math. Soc. 59, 100-108 (1999) · Zbl 0940.05037 · doi:10.1112/S0024610798006851
[13] Heffter, L.: Über metacyclic Gruppen und Nachbarconfigurationen. Math. Ann. 50, 261-268 (1898) · JFM 29.0117.01 · doi:10.1007/BF01448067
[14] James, L.D., Jones, G.A.: Regular orientable imbeddings of complete graphs. J. Comb. Theory Ser. B 39, 353-367 (1985) · Zbl 0584.05028 · doi:10.1016/0095-8956(85)90060-7
[15] Jones, G.A.: Regular embeddings of complete bipartite graphs: classification and enumeration. Proc. Lond. Math. Soc. (to appear). doi:10.1112/plms/pdp061 · Zbl 1202.05028
[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) · Zbl 1125.05033
[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) · Zbl 1136.05014 · doi:10.1016/j.jctb.2006.07.004
[18] Jones, G.A., Singerman, D.: Belyi functions, hypermaps, and Galois groups. Bull. Lond. Math. Soc. 28, 561-590 (1996) · Zbl 0853.14017 · doi:10.1112/blms/28.6.561
[19] Kwak, J.H., Kwon, Y.S.: Regular orientable embeddings of complete bipartite graphs. J. Graph Theory 50, 105-122 (2005) · Zbl 1077.05032 · doi:10.1002/jgt.20097
[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) · Zbl 1141.05029 · doi:10.1016/j.disc.2007.04.062
[21] Kwon, Y.S.: New regular embeddings of n-cubes Qn. J. Graph Theory 46, 297-312 (2004) · Zbl 1046.05022 · doi:10.1002/jgt.20010
[22] Kwon, Y.S., Nedela, R.: Non-existence of nonorientable regular embeddings of n-dimensional cubes. Discrete Math. 307, 511-516 (2007) · Zbl 1109.05034 · doi:10.1016/j.disc.2005.09.041
[23] Nedela, R., Škoviera, M.: Regular maps of canonical double coverings of graphs. J. Comb. Theory Ser. B 67, 249-277 (1996) · Zbl 0856.05029 · doi:10.1006/jctb.1996.0044
[24] Nedela, R., Škoviera, M.: Regular maps from voltage assignments and exponent groups. Eur. J. Comb. 18, 807-823 (1997) · Zbl 0908.05036 · doi:10.1006/eujc.1996.0138
[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) · Zbl 1008.05037
[26] Nedela, R., Škoviera, M., Zlatoš, A.: Regular embeddings of complete bipartite graphs. Discrete Math. 258, 379-381 (2002) · Zbl 1009.05049 · doi:10.1016/S0012-365X(02)00539-3
[27] Wilson, S.E.: Operators over regular maps. Pac. J. Math. 81, 559-568 (1979) · Zbl 0433.05021
[28] Xu, J.: A classification of regular embeddings of hypercubes Q2m with m odd. Sci. China Ser. A, Math. 50, 1673-1679 (2007) · Zbl 1133.05023 · doi:10.1007/s11425-007-0150-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.