Classification of regular embeddings of hypercubes of odd dimension

Abstract

By a regular embedding of a graph into a closed surface we mean a 2-cell embedding with the automorphism group acting regularly on flags. Recently, Kwon and Nedela [Non-existence of nonorientable regular embeddings of n-dimensional cubes, Discrete Math., to appear] showed that no regular embeddings of the n-dimensional cubes Q, into nonorientable surfaces exist for any positive integer n > 2. In 1997, Nedela and Skoviera [Regular maps from voltage assignments and exponent groups, European J. Combin. 18 (1997) 807-823] presented a construction giving for each solution of the congrumce e(2) equivalent to 1 (mod n) a regular embedding M-e of the hypercube Q(n) into an orientable surface. It was conjectured that all regular embeddings of Q(n) into orientable surfaces can be constructed in this way. This paper gives a classification of regular embeddings of hypercubes Q(n) into orientable surfaces for n odd, proving affirmatively the conjecture of Nedela and koviera for every odd n. (c) 2006 Elsevier B.V. All rights reserved.