Reflexibility of regular Cayley maps for abelian groups

Marston D.E. Conder^{∗}

Department of Mathematics, University of Auckland,

Private Bag 92019, Auckland, New Zealand m.conder@auckland.ac.nz

Young Soo Kwon^{†}

Department of Mathematics, Yeungnam University,

Kyongsan 712-749, Republic of Korea ysookwon@ynu.ac.kr

Jozef Širáň^{‡}

Department of Mathematics, University of Auckland,

Private Bag 92019, Auckland, New Zealand siran@math.auckland.ac.nz

Abstract

In this paper, properties of reflexible Cayley maps for abelian groups are investigated, and as a result, it is shown that a regular Cayley map of valency greater than 2 for a cyclic group is reflexible if and only if it is anti-balanced.

Keywords: Cayley map, regular embedding, anti-balanced 2000 Mathematics subject classification: 05C10, 05C25, 57M15

1 Introduction

Let G be a finite group and let X be a symmetric and unit-free generating set of G, by which we mean that X contains the inverse of each of its elements, but does not contain the identity element of G. The Cayley graph C(G, X) for the pair (G, X) has vertex set G, with any two vertices g, h ∈ G joined by an edge whenever g^{−1}h ∈ X, or, equivalently, h^{−1}g ∈ X. It follows that the Cayley graphs considered in this article are finite, connected, undirected, and simple (with no loops or multiple edges).

∗Research supported in part by the N.Z. Marsden Fund, Grant UOA 316 †This research was supported by Yeungnam University research grants in 2006 ‡Research supported in part by the N.Z. Marsden Fund, Grant UOA 316

We will be interested in particular embeddings of Cayley graphs on surfaces. In general, it is well known that to cellularly embed a connected simple graph on a compact orientable surface, one just needs to specify, at every vertex, a cyclic ordering of edges emanating from the vertex. The resulting embedding is often simply called a map. A graph automorphism that also preserves 2-cells (faces) of the embedding and the orientation of the surface is a map automorphism. If the group of orientation-preserving automorphisms of an embedding acts transitively on incident vertex-edge pairs, then this action must be regular and, accordingly, the embedding (map) is called regular (or sometimes rotary). In addition, the map is said to be reflexible if it admits an automorphism that reverses the orientation of the surface.

In the case of a Cayley graph C(G, X), all edges incident to a vertex g ∈ G have the form {g, gx} where x ∈ X. Hence to describe an embedding of a Cayley graph in an orientable surface, it is sufficient to specify a cyclic order of the generators at each vertex. If this cyclic order is the same at each vertex, given by a cyclic permutation p of the set X, then the embedding is called a Cayley map, and is denoted by CM(G, X, p). Since left multiplication by any fixed element of G induces an orientation-preserving automorphism of CM(G, X, p), Cayley maps are automatically vertex-transitive, with the group G acting regularly on vertices. Such a map may, of course, admit additional automorphisms.

The study of maps that are both Cayley and regular has been very fruitful from both combinatorial as well as group-theoretic perspectives. A substantial survey paper about Cayley maps and their role in the study of embeddings with a ‘high level of symmetry’ can be found in [9].

Properties of the permutation p which (from the point of view of the entire map) may be considered ‘local’, can often induce important ‘global’ properties of the Cayley map. For example, regularity of a Cayley map is equivalent to p satisfying a certain system of identities [4], subsequently re-stated in terms of so-called skew morphisms [5] (which we will introduce later). Such characterizations simplify greatly under additional and quite natural assumptions on p. As an important example of such a situation, we have the family of Cayley maps CM(G, X, p) that are balanced [10], meaning that p satisfies p(x^{−1}) = (p(x))^{−1} for all x ∈ X. By the main result of [10], a regular Cayley map CM(G, X, p) is balanced if and only if some automorphism of G coincides with p when restricted to the set X, which is equivalent to the condition that G is a normal subgroup of the map automorphism group of the Cayley map. A result of a similar type was proved in [11] for Cayley maps satisfying p(x^{−1}) = (p^{−1}(x))^{−1} for all x ∈ X, and these maps are called anti-balanced.

Historically, the first important class of regular Cayley maps was obtained in the course of construction and classification of regular embeddings of complete graphs; see [1] and references therein. By later findings [6] we know that, in fact, all regular embeddings of complete graphs are balanced Cayley maps (for additive groups of finite fields). Investigation of balanced Cayley maps for abelian groups was later taken quite far in [2], and led to a complete characterization of their existence (in terms of ‘balanced automorphisms’) in [7]. Further extensions of the theory to not necessarily balanced Cayley maps on abelian groups can be found in [8]. Based on the evidence from these three papers, we would like to emphasise that, even for cyclic groups, questions about existence of regular Cayley maps with specified properties are far from trivial.

In this paper we investigate in detail properties of reflexible Cayley maps for abelian groups. As the main (and rather surprising) result, we prove that a regular Cayley map of valency at least three on a cyclic group is reflexible if and only if it is anti-balanced.

2 Preliminaries

Let G be a finite group. Consider a permutation φ of G of order d (in the full symmetric group Sym(G)) and a function π from G to the cyclic group ℤ_{d}. The function φ is said to be a skew-morphism of G, with associated power function π, if φ fixes the unit element of G and

φ(ab) = φ(a)φ^{π(a)}(b) for all a, b ∈ G.

Here φ^{j} stands for the composition φ ∘ ⋯ ∘ φ consisting of j terms. Skew-morphisms and power functions were introduced in [5], where it was also proved that a Cayley map CM(G, X, p) is regular if and only if there exists a skew-morphism φ of G such that φ(x) = p(x) for each x ∈ X.

From now on, all Cayley graphs will be assumed to have valency greater than 2, since Cayley graphs of valency 2 are just simple cycles, and the corresponding Cayley maps are of genus 0 and reflexible. For a given finite group G with a symmetric, unitfree generating set X, and for a regular Cayley map M = CM(G, X, p), we will always use φ and π to denote respectively the skew-morphism of M with the property that the restriction of φ to X is p, and the associated power function. We will use d to denote the valency of M, and identify the integers 0, 1, …, d − 1 with their residue classes modulo d when the context permits. In particular, it follows from [5] that we may view the power function π as a function from G to ℤ_{d}. Also, if p = (x_{0}, x_{1}, …, x_{d−1}), then we will let c(k) ∈ ℤ_{d} be the subscript of x_{k}^{−1}, so that x_{k}^{−1} = x_{c(k)} for any k ∈ ℤ_{d}. Then for all k ∈ ℤ_{d} we have 1_{G} = φ(1_{G}) = φ(x_{k}x_{k}^{−1}) = φ(x_{k})φ^{π(x_{k})}(x_{k}^{−1}) = x_{k+1}φ^{π(x_{k})}(x_{c(k)}), which implies φ^{π(x_{k})}(x_{c(k)}) = x_{k+1}^{−1} = x_{c(k+1)}; and thus π(x_{k}) = c(k + 1) − c(k) for all k ∈ ℤ_{d}.

By an arc of a Cayley graph C(G, X) we will mean any pair of the form (g, gx) for g ∈ G and x ∈ X, which represents just an ‘edge with a direction’. The following observation will be useful later on.

Lemma 2.1 Let M = CM(G, X, p), with p = (x_{0}, x_{1}, …, x_{d−1}), be a d-valent reflexible Cayley map for the finite group G, and let ψ be an orientation-reversing automorphism of M. If ψ takes the arc (g, gx_{i}) to the arc (h, hx_{j}), then ψ takes gx_{i}x_{k} to hx_{j}x_{c(j)+c(i)−k} for all k ∈ ℤ_{d}.

Proof: This is easily seen from the following diagram, using the fact that the rotation p = (x_{0}, x_{1}, …, x_{d−1}) of edge-labels is the same at each vertex:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .^{.............................................................................................................................................................................................................}  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .^{.............................................................................................................................................................................................................} •  • •  • • • gx_{i}  g gx_{i}x_{k}  hx_{j} hhx_{j}x_{c(j)+c(i)−k} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .^{..................} . . . . . . . . . . . . . . . . . .  ^{..................} . . . . . . . . . . . . . . . . . . ψ

Note that the (k −c(i))th power of the rotation at vertex gx_{i} takes g = gx_{i}x_{c(i)} to gx_{i}x_{k}, while the (c(i)−k)th power of the rotation at vertex hx_{j} takes h = hx_{j}x_{c(j)} to hx_{j}x_{c(j)+c(i)−k}, which must therefore be the image of gx_{i}x_{k} under ψ.

It follows from [5] that all values of a power function π are non-zero. Although the power function need not be a group homomorphism, we will still use the notation ker π, but here for the set of all g ∈ G such that π(g) = 1. Note that by another result from [5], ker π is always a subgroup of G.

Power functions also lead to an important generalization of the concepts of balanced and anti-balanced Cayley maps. We say [2] that a Cayley map CM(G, X, p) is tbalanced if the associated power function π satisfies π(x) = t for all x ∈ X. Balanced and anti-balanced Cayley maps turn out to be special cases of this definition for t = 1 and t = −1, respectively.

We continue with the following observation, which can be obtained from the proof of [3, Theorem 5.4]:

Proposition 2.2 Let M = CM(A, X, p) be a regular Cayley map for the finite abelian group A, with associated skew-morphism φ. If the power function π takes ℓ distinct values on the generating set X, then ℓ divides |X|, and for any x ∈ X the ℓ elements x, φ(x), φ^{2}(x), …, φ^{ℓ−1}(x) belong to mutually distinct cosets of ker π, while φ^{i}(x) and φ^{i+ℓ}(x) belong to the same coset of ker π for all i; in particular, if p = (x_{0}, x_{1}, …, x_{d−1}) then the values π(x_{0}), π(x_{1}), …, π(x_{d−1}) repeat with period ℓ.

Note that in the special case where ℓ = 1 (so that π is constant on X), either M is balanced, or M is t-balanced for some t ≠ 1 (with π(x) = t for all x ∈ X).

In the next Section, we will investigate the properties of certain orientation-reversing automorphisms (reflections) of a reflexible Cayley map M = CM(A, X, p) for a finite abelian group A, and then in the subsequent Section, we will prove that if A is cyclic then ℓ = 1 and π(x) = d − 1 for all x ∈ X, so that M is anti-balanced.

3 Reflexible Cayley maps for abelian groups

In this Section we make the following critical observation:

Proposition 3.1 Let M = CM(A, X, p) be a regular Cayley map for the abelian group A, and suppose M is reflexible. Let ψ : A → A be any orientation-reversing automorphism of the map M that fixes the identity vertex 1_{A}, and takes x to x^{−1} for some x ∈ X. Then ψ induces a group automorphism of the vertex-regular subgroup A of Aut(M).

Proof: First let p = (x_{0}, x_{1}, …, x_{d−1}), and without loss of generality, let x = x_{0}. Also let u = c(0), so that x_{u} = x_{0}^{−1} = x^{−1}, and then from the choice of ψ it follows that ψ(x_{k}) = x_{u−k} for all k ∈ ℤ_{d}. Moreover, inspection of the rotations at vertices x_{0} and x_{u} (using Lemma 2.1) shows that ψ takes x_{0}x_{k} to x_{u}x_{u−k}, and then inspection of the rotations at those two vertices shows that

ψ(x_{0}x_{k}x_{u}) = ψ(x_{0}x_{k}x_{c(k)+(u−c(k))}) = x_{u}x_{u−k}x_{c(u−k)−(u−c(k))} = x_{u}x_{u−k}x_{c(u−k)−u+c(k)}.

But x_{0}x_{k}x_{u} = x_{0}x_{k}x_{0}^{−1} = x_{k} (since A is abelian), so this implies that

x_{u−k} = ψ(x_{k}) = ψ(x_{0}x_{k}x_{u}) = x_{u}x_{u−k}x_{c(u−k)−u+c(k)},

and hence x_{0} = x_{u}^{−1} = x_{c(u−k)−u+c(k)}, which gives c(u − k) = u − c(k), for all k ∈ ℤ_{d}. In particular, ψ(x_{k}^{−1}) = ψ(x_{c(k)}) = x_{u−c(k)} = x_{c(u−k)} = x_{u−k}^{−1} = ψ(x_{k})^{−1} for all k ∈ ℤ_{d}. But further, by Lemma 2.1 with g = h = 1_{A} we find that

ψ(x_{i}x_{k}) = x_{u−i}x_{c(u−i)+c(i)−k} = x_{u−i}x_{u−c(i)+c(i)−k} = x_{u−i}x_{u−k} = ψ(x_{i})ψ(x_{k})

for all i, k ∈ ℤ_{d}, and it follows by induction (and Lemma 2.1) that ψ(ax_{k}) = ψ(a)ψ(x_{k}) for all a ∈ A and all k ∈ ℤ_{d}, and hence that ψ induces an automorphism of A.

Note that in the above proof, x = x_{0} can be chosen as any of the elements of the generating set X. In particular, if x is an involution, then c(0) = 0, and the ‘axis’ of the reflection ψ contains the arc (1_{A}, x). Hence if A is an elementary abelian 2-group of order 2^{d}, then the Cayley map M has many such reflections. On the other hand, if A is cyclic, then the number of possible reflections (that take an element x ∈ X to its inverse) is limited, as we will see at the beginning of the next Section.

It is also easy to prove the following:

Theorem 3.2 If M = CM(A, X, p) is an anti-balanced regular Cayley map for the finite abelian group A, then M is reflexible.

Proof: If p = (x_{0}, x_{1}, …, x_{d−1}) then since M is anti-balanced, we may suppose that x_{i} = x_{d−1−i}^{−1} for all i ∈ ℤ_{d}. It follows that the automorphism of A taking x to x^{−1} for all x ∈ A gives an automorphism of the underlying graph of M compatible with p, and hence an orientation-reversing automorphism of M.

4 Reflexible Cayley maps for cyclic groups

We begin by establishing a property of every regular Cayley map for a finite cyclic group A, that needs only the fact that Aut(A) is abelian. (Recall that if A is cyclic of order n, generated by a element w, then every automorphism of A is given by the assignment w ↦ w^{α} for some unit α ∈ ℤ_{n}, and any two such automorphisms commute.)

Proposition 4.1 Let M = CM(A, X, p = (x_{0}, x_{1}, …, x_{d−1})) be a reflexible d-valent regular Cayley map for a cyclic group A. Also let ψ be an orientation-reversing automorphism of M that fixes the identity vertex 1_{A}, and takes x_{i} to x_{u−i} for all i ∈ ℤ_{d}, where x_{u} = x_{0}^{−1} (as in the proof of Proposition 3.1). Then if τ is any orientationreversing automorphism of M that takes some x_{s} to its inverse x_{s}^{−1} = x_{c(s)}, then 2(s + c(s)) ≡ 2u mod d, so either s + c(s) ≡ u mod d, or d is even and s + c(s) ≡ u + \frac{d}{2} mod d; in particular, either τ = ψ, or d is even and τ takes x_{i} to x_{\frac{d}{2} +u−i} for all i ∈ ℤ_{d}.

Proof: First since τ is an orientation-reversing automorphism fixing 1_{A} and taking x_{s} to x_{c(s)}, we see that τ(x_{i}) = x_{s+c(s)−i} for all i ∈ ℤ_{d}. Next, since Aut(A) is abelian, ψ and τ commute, so x_{u−(s+c(s)−k)} = ψ(τ(x_{k})) = τ(ψ(x_{k})) = x_{s+c(s)−(u−k)} for all k ∈ ℤ_{d}, and it follows that 2(s + c(s)) ≡ 2u mod d. The rest follows easily.

Corollary 4.2 Let M = CM(A, X, p) be a reflexible d-valent regular Cayley map for the cyclic group A. Then either M is anti-balanced, or d is even and M is (\frac{d}{2} −1)- balanced, or d is even and the power function of the skew-morphism φ of A associated with M takes just two values −1 and \frac{d}{2}−1 on the generating set X, and these alternate for π(x_{i}) as i runs through ℤ_{d} in the natural order 0, 1, 2, …, d−1. In particular, every reflexible regular Cayley map of odd valency for a cyclic group A is anti-balanced.

Proof: Let p, u and ψ be as given in Proposition 4.1, and let π be the associated power function of φ. Then we know that for any s ∈ ℤ_{d}, either c(s) = u − s or \frac{d}{2} + u − s (where d has to be even in the latter case). If c(s) = u − s for all s then π(x_{k}) = c(k + 1) − c(k) = (u − (k + 1)) − (u − k) = −1 for all k ∈ ℤ_{d}, and so M is anti-balanced. If not, then d is even, and π(x_{k}) = c(k +1) − c(k) can differ from (u − (k + 1)) − (u − k) = −1 by \frac{d}{2}. If π(x_{k}) = \frac{d}{2} − 1 for all k ∈ ℤ_{d} (which would occur for example when c(s) = u − s for all even s and c(s) = \frac{d}{2} + u − s for all odd s), then M is (\frac{d}{2} −1)-balanced. Otherwise π takes both values −1 and \frac{d}{2} −1 on X, and by Proposition 2.2, the values π(x_{0}), π(x_{1}), …, π(x_{d−1}) repeat with period 2.

Geometrically, when π takes values −1 and \frac{d}{2} −1 on X, there are two reflections of interest, viz. ψ: x_{i} ↦ x_{u−i} and τ: x_{i} ↦ x_{\frac{d}{2} +u−i}, and these have orthogonal axes.

We will show that every reflexible regular Cayley map M = CM(C_{n}, X, p) of valency greater than 2 for a cyclic group C_{n} (of order n) admits only one such reflection, and is therefore anti-balanced. In doing this, we will use p = (x_{0}, x_{1}, …, x_{d−1}) and other notation as given in the previous Section. Also we will suppose that d is even, and define two sets U and V as follows:

U = \{ x_{k} ∈ X | k + c(k) ≡ u mod d \} and V = \{ x_{k} ∈ X | k + c(k) ≡ \frac{d}{2} +u mod d \}.

We are assuming that U is non-empty, and by Proposition 4.1, we know that X is a disjoint union of U and V. Moreover, for each i ∈ ℤ_{d}, either x_{i} and x_{i}^{−1} = x_{c(i)} both lie in U, or both lie in V. On the other hand, since d is even, and C_{n} contains at most one element of order 2, we may suppose that x_{i}^{−1} ≠ x_{i} (and so c(i) ≠ i) for all i ∈ ℤ_{d}.

Also if U = X then M is anti-balanced, so we will assume that V is non-empty. Then by Corollary 4.2, we know that either M is (\frac{d}{2} −1)-balanced (with π(x_{i}) = \frac{d}{2} −1 for all i ∈ ℤ_{d}), or the values π(x_{0}), π(x_{1}), …, π(x_{d−1}) alternate between −1 and \frac{d}{2} −1. We are going to rule out each of these two possibilities.

Corresponding to U is a reflection ψ taking x_{i} to x_{u−i} for all i ∈ ℤ_{d}, with the property that ψ(x_{k}) = x_{u−k} = x_{c(k)} = x_{k}^{−1} whenever x_{k} ∈ U. By Proposition 3.1, this reflection ψ induces an automorphism of C_{n} = ⟨w⟩, and so there exists some unit α ∈ ℤ_{n} such that ψ(w^{i}) = w^{iα} for all i ∈ ℤ_{n}. In particular, x_{k}^{α} = ψ(x_{k}) = x_{k}^{−1} whenever x_{k} ∈ U. Also U cannot generate C_{n}, for otherwise ψ would invert every element of X, and then we would find that x_{u−k} = ψ(x_{k}) = x_{k}^{−1} = x_{c(k)} for all x_{k} ∈ X, giving U = X.

Similarly, corresponding to V is a reflection τ taking x_{i} to x_{\frac{d}{2} +u−i} for all i ∈ ℤ_{d}, and there is a unit β ∈ ℤ_{n} such that ψ(w^{i}) = w^{iβ} for all i ∈ ℤ_{n}, with x_{k}^{β} = τ(x_{k}) = x_{k}^{−1} whenever x_{k} ∈ V, and it follows that V cannot generate C_{n}.

On the other hand, X = U ∪ V generates C_{n}, so at least one of ⟨U⟩ and ⟨V ⟩ has odd index in C_{n}, and without loss of generality we may suppose this is true for ⟨V ⟩. In particular, if x is any element of C_{n} for which x^{2} ∈ ⟨V ⟩, then also x ∈ ⟨V ⟩.

We are now ready to consider the two cases we wish to eliminate:

Case (1) π(x_{i}) = \frac{d}{2} −1 for all i ∈ ℤ_{d}

Here we know that x_{i} ∈ U (and c(i) = u − i) whenever i is even, while x_{j} ∈ V (and c(j) = \frac{d}{2} + u − j) whenever j is odd, in order for π to have constant value \frac{d}{2} −1 on the generating set X. In particular, the skew morphism φ associated with M interchanges elements of U with elements of V.

If u is odd, then one of x_{\frac{u−1}{2}} and x_{\frac{u−1}{2} +1} = x_{\frac{u+1}{2}} lies in U, but then since \frac{u−1}{2} + \frac{u+1}{2} = u, also the other one lies in U, which is impossible. Hence u is even.

Similarly, as X contains no involutions, we find that x\frac{u}{2} = x_{u− \frac{u}{2}} cannot lie in U, so x\frac{u}{2} lies in V and c(\frac{u}{2}) = \frac{d}{2} + u − \frac{u}{2}.

Next, since M is (\frac{d}{2} −1)-balanced, we know that (\frac{d}{2} − 1)^{2} ≡ 1 mod d, and then since d is even, it follows that \frac{d}{2} must be even, so d ≡ 0 mod 4. Now consider c(\frac{d}{4} + \frac{u}{2}). Either c(\frac{d}{4} + \frac{u}{2}) ≡ u−(\frac{d}{4}+\frac{u}{2}) ≡ \frac{u}{2} − \frac{d}{4} mod d, or c(\frac{d}{4} + \frac{u}{2}) ≡ \frac{d}{2} +u−(\frac{d}{4}+\frac{u}{2}) ≡ \frac{d}{4} + \frac{u}{2} mod d, depending on whether x_{\frac{d}{4} + \frac{u}{2}} lies in U or V. The latter is impossible since c(i) ≠ i for all i ∈ ℤ_{d}, so c(\frac{d}{4} + \frac{u}{2}) ≡ \frac{u}{2} − \frac{d}{4} mod d, and in particular, x_{\frac{d}{4} + \frac{u}{2}} must lie in U. As x\frac{u}{2} lies in V, it follows that \frac{d}{4} is odd, so d ≡ 4 mod 8. In particular, \frac{d}{4}(\frac{d}{2} − 1) ≡ \frac{d}{4} mod d.

Accordingly, because π(x) = \frac{d}{2} − 1 for all x ∈ X, we find that

φ^{\frac{d}{4}} (x_{i}x_{j}) = φ^{\frac{d}{4}} (x_{i})φ^{\frac{d}{4} ( \frac{d}{2} −1)}(x_{j}) = φ^{\frac{d}{4}} (x_{i})φ^{\frac{d}{4}} (x_{j}) for all x_{i}, x_{j} ∈ X,

and hence by induction that φ^{\frac{d}{4}} is a group automorphism of C_{n}.

But \frac{d}{4} is odd, so φ^{\frac{d}{4}} (like φ) interchanges elements of U with elements of V, and hence U and V must generate the same proper cyclic subgroup of C_{n}; that, however, is impossible since X = U ∪ V generates C_{n}. Hence this case can be eliminated.

Case (2) The values π(x_{0}), π(x_{1}), …, π(x_{d−1}) alternate between −1 and \frac{d}{2} −1

Here, since we have assumed that x_{0} lies in U, we may suppose without loss of generality that x_{i} ∈ U (and c(i) = u − i) whenever i ≡ 0 or 1 mod 4, while x_{j} ∈ V (and c(j) = \frac{d}{2} + u − j) whenever j ≡ 2 or 3 mod 4. In particular, d is divisible by 4. Moreover, x_{u} = x_{c(0)} and x_{u−1} = x_{c(1)} both lie in U (since x_{0} and x_{1} lie in U), so we find that u − 1 ≡ 0 mod 4, and u ≡ 1 mod 4.

Now consider x_{i} for any i ≡ 1 mod 4, so that x_{i−1} and x_{i} lie in U while x_{i−2}, x_{i+1} and x_{i+2} all lie in V. Then π(x_{i−1}) ≡ c(i) − c(i−1) ≡ (u−i) − (u−(i−1)) ≡ −1 mod d, and similarly π(x_{i+1}) ≡ c(i+2) − c(i+1) ≡ (\frac{d}{2}+u−(i+2)) − (\frac{d}{2}+u−(i+1)) ≡ −1 mod d, so

x_{i}^{2} = φ(x_{i−1})φ^{−1}(x_{i+1}) = φ(x_{i−1}x_{i+1}) = φ(x_{i+1}x_{i−1}) = φ(x_{i+1})φ^{−1}(x_{i−1}) = x_{i+2}x_{i−2}.

Thus x_{i}^{2} = x_{i+2}x_{i−2} ∈ ⟨V ⟩, and as ⟨V ⟩ has odd index in C_{n}, it follows that x_{i} ∈ ⟨V ⟩. On the other hand, x_{u−i} = x_{c(i)} and x_{u−i+1} = x_{c(i−1)} both lie in U (since x_{i−1} and x_{i} lie in U), so u − i ≡ 0 mod 4 and u − i + 1 ≡ 1 mod 4, so by the above argument ⟨V ⟩ contains x_{u−i+1} = x_{c(i−1)} = x_{i−1}^{−1}. Thus ⟨V ⟩ contains both x_{i−1} and x_{i} whenever i ≡ 1 mod 4, so ⟨V ⟩ contains all elements of U, which is another contradiction, and eliminates this case.

Hence we have proved the following:

Theorem 4.3 If M = CM(C_{n}, X, p) is a reflexible regular Cayley map of valency greater than 2 for the cyclic group C_{n}, then M is anti-balanced.

Putting this together with Theorem 3.2, we have the following:

Theorem 4.4 A regular Cayley map of valency greater than 2 for a finite cyclic group is reflexible if and only if it is anti-balanced.

5 Concluding remarks

An obvious question is how far these results extend to other groups, or at least to other abelian groups. The answer appears to be “a very limited extent”. There exist reflexible balanced regular Cayley maps for non-cyclic abelian groups, including elementary abelian p-groups and other abelian groups of non-prime-power order (such as 18, 20, 24, 28, 36, 40, 44, 45, 48 and 50), and also there exist reflexible regular Cayley maps for non-cyclic abelian groups that are t-balanced for some t ≠ ±1, and others that are not t-balanced for any t (such as unbalanced but reflexible regular Cayley maps for abelian groups of order 32 and 64). On the other hand, there exist anti-balanced regular Cayley maps for non-abelian groups that are chiral (irreflexible), such as nonabelian groups of order 36, 40, 42, 60, 64, 72, 80 and 96. Hence it is difficult to see how the above theorems can be taken further.

References

[1] N. Biggs, Cayley maps and symmetrical maps, Proc. Cambridge Philos. Soc. 72 (1972), 381-386.

[2] M. Conder, R. Jajcay and T. Tucker, Regular Cayley maps for finite abelian groups, J. Algebraic Combinatorics 25 (2007), 259-283.

[3] M. Conder, R. Jajcay and T. Tucker, Regular t-balanced Cayley maps, J. Combin. Theory Ser. B, 97 (2007), 453-473.

[4] R. Jajcay, Automorphism groups of Cayley maps, J. Combin. Theory Ser. B 59 (1993), 297-310.

[5] R. Jajcay and J. Širáň, Skew-morphisms of regular Cayley maps, Discrete Mathematics 244 (2002), 167-179.

[6] L. James and G. Jones, Regular orientable imbeddings of complete graphs, J. Combinat. Theory Ser. B 39 (1985), 353-367.

[7] M. Muzychuk, On balanced automorphisms of abelian groups, preprint, 2005.

[8] M. Muzychuk, On unbalanced regular Cayley maps over abelian groups, preprint, 2005.

[9] B. Richter, J. Širáň, R. Jajcay, T. Tucker, M. Watkins, Cayley maps, J. Combin. Theory Ser. B 95 (2005) No. 2, 189-245.

[10] M. Škoviera and J. Širāň, Regular maps from Cayley graphs, Part I: Balanced Cayley maps, Discrete Math. 109 (1992), 265-276.

[11] M. Škoviera and J. Širāň, Regular maps from Cayley graphs, Part II: Antibalanced Cayley maps, Discrete Math. 124 (1994), 179-191.