we assume that the unit element of the group is not inX

Vol. LXIX, 1(2000), pp. 59–70

COMPARING A CAYLEY DIGRAPH WITH ITS REVERSE

M. ABAS

Abstract. A Cayley digraphG = C(Γ, X) for a group Γ and a generating set X is the digraph with vertex set V(G) = Γ and arcs (g, gx) where g ∈ Γ and x∈X. ThereverseofC(Γ, X) is the Cayley digraphG⁻¹ =C(Γ, X⁻¹) where X⁻¹={x⁻¹;x∈X}. We are interested in sufficient conditions for a Cayley digraph not to be isomorphic to its reverse and focus on Cayley digraphs of metacyclic groups with small generating sets.

1. Introduction

Let Γ be a finite group and let X be a generating set for Γ; we assume that the unit element of the group is not inX. TheCayley digraph G=C(Γ, X) is a digraph with vertex set V(G) = Γ and arc set D(G) ={(g, gx);g ∈Γ, x∈X}. If, in addition, the set X is closed under taking inverses (i.e., if x ∈ X implies x⁻¹ ∈ X) then the two arcs (g, gx) and (gx, g) are usually identified to form a single undirected edge, which turns the digraph into an (undirected) Cayley graph.

Cayley digraphs are automatically vertex-transitive. In fact, for each fixed h∈Γ the mapping θh: V(G)→ V(G) given by θh(g) =hg is an automorphism of the Cayley digraphC(Γ, X). Thus, the (full) automorphism group of a Cayley digraph contains a subgroup acting regularly on its vertex set. The converse is true as well: By the (digraph modification of) Sabidussi’s Theorem [7], if the automorphism group of digraph contains a subgroup acting regularly on its vertex set, then the digraph is necessarily a Cayley digraph.

In both theory and applications, Cayley graphs and digraphs play an increas- ingly important role [4]. Among the variety of research directions here, in the last few years there has been a considerable activity in the study of isomorphism of Cayley (di)graphs. The basic motivation is provided by following simple ob- servation: If C(Γ, X) and C(Γ, Y) are two Cayley digraphs for the same group and if there is an automorphismσ of the group Γ such that σ(X) = Y, then σ naturally extends to an isomorphism of the two Cayley digraphs. The important Cayley-Isomorphismproblem is to characterize the groups Γ for whichevery isomorphism of two Cayley digraphs C(Γ, X) andC(Γ, Y) is induced by a group

Received December 18, 1998.

1980Mathematics Subject Classification(1991Revision). Primary 05C25.

Key words and phrases. Cayley digraph, digraph isomorphism.

automorphism in the above sense. For substantial results in this area we refer to [1], [5], [6].

Cayley digraphs have been successfully used in constructing large digraphs of given (comparatively small) degree and diameter [3]. In a detailed study of these digraphs [2] it was observed that some of the large Cayley digraphsGdescribed in [3] have the following interesting property: The digraph G⁻¹ obtained fromG by reversing the direction of each arc is isomorphic toG. For obvious reasons we call the digraphG⁻¹thereverseofG. In the Cayley digraph setting, the reverse of G = C(Γ, X) is the digraph G⁻¹ = C(Γ, X⁻¹) where X⁻¹ = {x⁻¹;x∈ X}. The interesting question thus is: Which Cayley digraphs are isomorphic to their reverse? Does the isomorphism occur frequently or is it rather rare? In which Cayley digraphs is such an isomorphism induced by a group automorphism of Γ which takesX toX⁻¹?

The answers to the above questions are easy in the case of Cayley digraphs of Abelian groups. Indeed, if Ais an Abelian group then the map φ:A →A such that φ(a) = a⁻¹ for each elementa∈Ais a group automorphism which induces a digraph isomorphismC(A, X)∼=C(A, X⁻¹). In this note we therefore focus on metacyclic groups Γ (which are semidirect products of cyclic groups, thus, in some sense, “simplest” nonabelian groups) and show that there are only few groups for whichG=C(Γ, X) is isomorphic toG⁻¹=C(Γ, X⁻¹) for each generating setX.

2. Metacyclic Groups

Throughout this paper we use the following notation. For an arc (a, b) where b =ax we shall often use the alternative notation a−→^x b to emphasize that one can pass from the vertexato the vertexbalong an arc using the generatorx. We reserve the symbolefor the unit element of a group.

Metacyclic groups are defined as semidirect products of cyclic groups and they have the following standard presentation:

Zno_kZm=ha, b|aⁿ =b^m=e, ba=a^kbi, where gcd(n, k) = 1, 1< k < nandk^m≡1 (modn).

Note that for eachi (modn) andj (modm) we have

(1) b^jaⁱ=a^ikjb^j.

Equivalently, metacyclic groups are split extensions of Z_n by Z_m under the group homomorphism θ:Zm → Aut(Zn) which sends each i ∈ Zm to the au- tomorphism θ_i ∈ Aut(Z_n) where θ_i(s) = kⁱs,s ∈ Z_n. In this setting the group multiplication is given by (r, i)(s, j) = (r+θi(s), i+j).

Letx∈X be a generator of ordertin Γ. In what follows, the cycle (g, gx, . . . , gx^t−1) in the digraphC(Γ, X) will be denoted simply byCx(g); the corresponding cycle (g, gx⁻¹, . . . , gx^1−t) in the reverse digraph will be denoted byC_x⁻₋₁¹(g).

3. Reverses of Cayley digraphs of Valence 2

In this section we focus on comparing Cayley digraphsC(Γ, X) withC(Γ, X⁻¹) such that|X|= 2.

Lemma 1. LetG=C(Γ, X)be a Cayley digraph for the group Γ =Zno_kZm

(n6=m) and the generating setX ={a, b}. If φis an isomorphism φ:G→G⁻¹ such that φ(e) =e, thenφ(aⁱb^j) =a⁻ⁱb^−j.

Proof. We consider only the casen > m; the argument forn < mis similar. An easy inspection shows that for every vertexgof the digraphG(G⁻¹) there is only one cycle of lengthm passing through g, namely C_b(g) (C_b⁻₋₁¹(g)). As φ(e) =e, φmust map the cycleCb(e) onto the cycleC_b⁻₋₁¹(e). Thereforeφ(bⁱ) =b⁻ⁱ. Now, the only possibility for the image of a is φ(a) = a⁻¹. From this it follows that φ(abⁱ) =a⁻¹b⁻ⁱ and the only possibility fora² isφ(a²) =a⁻². Continuing in this manner we eventually obtain thatφ(aⁱb^j) =a⁻ⁱb^−j and the result follows.

Lemma 2. LetG=C(Γ, X)be a Cayley digraph for the group Γ =Z_no_kZ_m (n 6= m) and the generating set X = {a, b}. If m is odd, or if m is even and k²6≡1 (modn), thenGG⁻¹.

Proof. Assume the contrary and let φ: G →G⁻¹ be a digraph isomorphism.

Because every Cayley digraph is vertex-transitive, without loss of generality we may assume that φ(e) = e. According to Lemma 1, this isomorphism must have the form φ(aⁱb^j) =a⁻ⁱb^−j. Then, for an arbitrary vertexaⁱb^j ofG, the two arcs emanating from this vertex are

aⁱb^j−→^a aⁱb^ja=a^i+kjb^j, and

aⁱb^j −→^b aⁱb^jb=aⁱb^j+1.

Similarly, the two arcs ofG⁻¹ emanating from the vertex a⁻ⁱb^−j are a⁻ⁱb^−j −−→^a−1 a⁻ⁱb^−ja⁻¹=a^−i−k−jb^−j,

and

a⁻ⁱb^{−j b}

−1

−−→a⁻ⁱb^−jb⁻¹=a⁻ⁱb^−j−1. Sinceφ(aⁱb^j) =a⁻ⁱb^−j, it follows that

{φ(a^i+kjb^j), φ(aⁱb^j+1)}={a^−i−kjb^−j, a⁻ⁱb^−j−1}.

On the other hand, evaluating φ turns the preceding equality into the following one:

{a^−i−kjb^−j, a⁻ⁱb^−j−1}={a^−i−k−jb^−j, a⁻ⁱb^−j−1}.

Now, the two sets above are equal if and only if a^−i−kjb^−j =a^−i−k−jb^−j. Thus,

−k^j ≡ −k^−j (modn)

for each j. This implies that k^2j ≡ 1 (modn), and for j = 1 we have k² ≡ 1 (modn). If m is even we already have a contradiction with our assumptions. If m= 2r+ 1 then our last congruence implies thatk^m=k^2r+1≡k (mod n). But by our description of the semidirect product we havek^m≡1 (modn); sincek≡1

(modn),we arrive at a contradiction again.

Lemma 3. Let G be a Cayley digraph for the group Γ = Zno_kZn and the generating setX ={a, b}. If nis odd, or if nis even and k² 6≡1 (modn), then GG⁻¹.

Proof. Assume the contrary, again, and let φ:G→G⁻¹ be a digraph isomor- phism; we may assume thatφ(e) =e. In this case, through any vertexg there are only two vertex-disjoint (up to the vertexg) cycles of lengthn, namely

C_a(g) and C_b(g) in the digraphGand

C_a⁻₋₁¹(g) and C_b⁻₋₁¹(g)

in the digraphG⁻¹. It is easy to verify that a possible isomorphismφ(e) =emust satisfy one of the following conditions:

a) φ(aⁱb^j) =a⁻ⁱb^−j or b) φ(aⁱb^j) =b⁻ⁱa^−j.

In the case a) we have a situation similar to the case whenn6=m. In the case b) let us consider the two arcs

aⁱb^j−→^a aⁱb^ja=a^i+kjb^j, and

aⁱb^j −→^b aⁱb^jb=aⁱb^j+1 in the digraphG. ForG⁻¹ it then holds that

φ(aⁱb^j) =b⁻ⁱa^−j−−→^a−1 a^{(−j−1)k−i}b⁻ⁱ, and

φ(aⁱb^j) =b⁻ⁱa^−j −−→^b−1 a^−jk−ib⁻ⁱ⁻¹.

Now, using b) and the relations (1) we obtain φ(a^i+kjb^j) =a^{−jk(−i−kj)}b^−i−kj, and

φ(aⁱb^j+1) =a^{(−j−1)k−i}b⁻ⁱ. Sinceφis assumed to be a digraph isomorphism, we have

{φ(a^i+kjb^j), φ(aⁱb^j+1)}={a^−i−kjb^−j, a⁻ⁱb^−j−1}; therefore (see the proof of Lemma 2)

{a^{(−j−1)k−i}b⁻ⁱ, a^−jk−ib⁻ⁱ⁻¹}={a^{−jk(−i−kj)}b^−i−kj, a^{(−j−1)k−i}b⁻ⁱ}; in particular,

a^−jk−ib⁻ⁱ⁻¹=a^{−jk(−i−kj)}b^−i−kj

for all i, j. This implies that k^j ≡1 (modn) for allj. Settingj = 1 we obtain

k^j =k¹=k≡1 (modn), a contradiction.

Note that in the casek²≡1 (modn) in Lemma 2 and 3, the mappingφ:G→ G⁻¹ such thatφ(aⁱb^j) =a⁻ⁱb^−j is a digraph isomorphism.

4. Reverses of Cayley Digraphs of Valence 4

In the next part of this paper we will consider the case when m is even and k² ≡1 (modn) only. The reason for continuing with the case of four generators will be clear from the conclusion of this section. The following three Lemmas will serve as auxiliary results for proving Lemma 7.

Lemma 4. LetGbe a Cayley digraph for the groupΓ =Z_no_kZ_m(n6=m)with the generating set X = {a, b, baⁱ¹, baⁱ²}, where i1, i2 6= 0, i1 6≡i2 (modn), and letn≥6. Let there exist an isomorphismφ:G→G⁻¹ such that φ(e) =e. Then, fore somep, we have{b⁻¹a^p, b⁻¹a^−i1+p, b⁻¹a^−i2+p}={b⁻¹, b⁻¹a^−i1k, b⁻¹a^−i2k}.

Proof. i) Letn > m. Because the generatorsb, baⁱ¹, baⁱ² all have orderm, each vertexg∈Gis contained in exactly three cycles of lengthm(which is the shortest cycle length inG), namely

Cy_i(g) = (g, gyi, gyi2, . . . , gyim−1, gyim=g),

where y1 =b, y2 =baⁱ¹, y3 = baⁱ². The situation is similar in the digraph G⁻¹, withy_i⁻¹in place ofy_i. Because isomorphism preserves cycle lengths, all arcs of the form (g, gyi) must be mapped byφonto arcs of the form (g⁰, g⁰y⁻_j¹). Sinceφ(e) =e,

the isomorphismφhas to mapaⁱtoa⁻ⁱ, and this implies thatφ(b^jaⁱ) =b^−ja^−i+pj, where 0≤pj ≤n−1.

Except for the vertexa, the neighbourhood of the vertexein the digraphGis the set of vertices{b, baⁱ¹, baⁱ²}, and it is mapped onto the set{b⁻¹a^p, b⁻¹a^−i1+p, b⁻¹a^−i2+p}by the isomorphismφ.

Similarly, except for the vertexa⁻¹, the neighbourhood of the vertexe in the digraphG⁻¹is the set of vertices{b⁻¹,(baⁱ¹)⁻¹=b⁻¹a^−i1k,(baⁱ²)⁻¹=b⁻¹a^−i2k}. ii) Letn < m. By similar arguments as above, the isomorphismφmust satisfy φ(aⁱ) =a⁻ⁱ andφ(b^jaⁱ) =b^−ja^−i+pj. Lemma 5. Let Gbe a Cayley digraph for the groupΓ =Zno_kZn with gener- ating setX ={a, b, baⁱ¹, baⁱ²}, wherei1,i26= 0,i16≡i2 (mod n), and letn≥6.

If φ: G→G⁻¹ is an isomorphism such thatφ(e) =ethen φ(aⁱ) =a⁻ⁱ. Proof. Considering the three cycles C_b(e), C_bai1(e), C_bai2(e), we have eight cases:

1) |Cb(e)∩C_bai1(e)|= 1∧ |Cb(e)∩C_bai2(e)|= 1∧ |C_bai1(e)∩C_bai2(e)|= 1, 2) |Cb(e)∩C_bai1(e)|= 1∧ |Cb(e)∩C_bai2(e)|= 1∧ |C_bai1(e)∩C_bai2(e)|>1, 3) |Cb(e)∩C_bai1(e)|= 1∧ |Cb(e)∩C_bai2(e)|>1∧ |C_bai1(e)∩C_bai2(e)|= 1, 4) |Cb(e)∩C_bai1(e)|>1∧ |Cb(e)∩C_bai2(e)|= 1∧ |C_bai1(e)∩C_bai2(e)|= 1, 5) |C_b(e)∩C_bai1(e)|= 1∧ |C_b(e)∩C_bai2(e)|>1∧ |C_bai1(e)∩C_bai2(e)|>1, 6) |Cb(e)∩C_bai1(e)|>1∧ |Cb(e)∩C_bai2(e)|= 1∧ |C_bai1(e)∩C_bai2(e)|>1, 7) |C_b(e)∩C_bai1(e)|>1∧ |C_b(e)∩C_bai2(e)|>1∧ |C_bai1(e)∩C_bai2(e)|= 1, 8) |Cb(e)∩C_bai1(e)|>1∧ |Cb(e)∩C_bai2(e)|>1∧ |C_bai1(e)∩C_bai2(e)|>1.

The cases 5), 6), 7), 8) are quite easy. For example, in the case 5) the cycleCa(e) is vertex-disjoint (except vertex e) from the cycles Cb(e), C_bai1(e) and C_bai2(e).

The image of the cycle Ca(e) has the same property. But |Cx(e)∩Cy(e)| ≥ 2, wherex, y∈ {b, baⁱ¹, baⁱ²}for some x6=y. Soφ(aⁱ) =a⁻ⁱ.

The remaining cases are 1) and 2). (The cases 3) and 4) are similar to the case 2).) In the case 1), the set{a, b, baⁱ¹, baⁱ²}is equal to the set{a, b⁰, b⁰aⁱ⁰¹, b⁰aⁱ⁰²} for b⁰ = baⁱ¹ and some i⁰; without loss of generality we may assume the con- trary and let φ(aⁱ) = b⁻ⁱ. There are three arcs emanating from e and termi- nating in the cycle C_a⁻₋₁¹(b⁻¹) = (b⁻¹, b⁻¹a⁻¹, b⁻¹a⁻², . . . , b⁻¹a) in the digraph G⁻¹. Similarly there are three arcs emanating from e and terminating in the cycle Cy(a) = (a, ay, ay², . . . , ay⁻¹), where y ∈ {b, baⁱ¹, baⁱ²} in the digraph φ(G). These three arcs must terminate in the verticesa, baⁱ¹, baⁱ². But the cycle (a, ay, ay², . . . , ay⁻¹) has the form (a, ba^r1, b²a^r2, . . . , bⁿ⁻¹a^rn−1, a) and hence it is impossible to find there two elements of the formb¹a^rj.

As regards the case 2), the considerations are similar to the case 1).

Lemma 6. Let G be the Cayley digraph for the group Γ = Zno_k Zn with generating set X = {a, b, baⁱ¹, baⁱ²}, where i1, i2 6= 0, i1 6≡ i2 (mod n), and let

n≥6. Ifφ:G→G⁻¹ is an isomorphism such thatφ(aⁱ) =a⁻ⁱ then, for somep, (2) {b⁻¹a^p, b⁻¹a^−i1+p, b⁻¹a^−i2+p}={b⁻¹, b⁻¹a^−i1k, b⁻¹a^−i2k}.

Proof. There are just three arcs emanating from the vertex eand terminating in the cycle of the form (b, ba, ba², . . . , b) in the digraphG. Similarly, there are just three arcs emanating from the vertex eand terminating in the cycle of the form (b⁻¹, b⁻¹a⁻¹, b⁻¹a⁻², . . . , b⁻¹) in the digraphG⁻¹. Becauseφ(e) =eit holds that φ({bhai}) = {b⁻¹hai}, i.e.: the cycle (b, ba, ba², . . . , b) is mapped onto the cycle (b⁻¹, b⁻¹a⁻¹, b⁻¹a⁻², . . . , b⁻¹) by the isomorphismφ. In the cycle (b, ba, ba², . . . , b) the distance from the vertexbaⁱ to the vertexba^j is d(baⁱ, ba^j)≡j−i (mod n).

Applying the isomorphism φ, we have d(φ(baⁱ), φ(ba^j))≡ j−i (mod n), for all i,j. This is true if and only ifφ(baⁱ) =b⁻¹a^−i+p for somep∈[0, n−1].

Now, there are three arcs emanating from the vertex e and terminating in the set of vertices {b⁻¹,(baⁱ¹)⁻¹,(baⁱ²)⁻¹} = {b⁻¹, b⁻¹a^−i1k, b⁻¹a^−i2k} and one arc terminating in the vertex a⁻¹, in the digraph G⁻¹. Similarly, there are three arcs emanating from the vertex e and terminating in the set of vertices {b⁻¹, b⁻¹a^−i1+p, b⁻¹a^−i2+p} and one arc terminating in the vertex a⁻¹, in the digraphφ(G). Comparing the above two sets we obtain (2).

Summing up the preceding three Lemmas we have:

Lemma 7. Let G be a Cayley digraph for the group Γ = Zno_kZm with the generating set X = {a, b, baⁱ¹, baⁱ²}, where i1, i2 6= 0, i1 6≡ i2 (mod n), and let n≥6. Let there exist an isomorphismφ: G→G⁻¹such thatφ(e) =e. Then, for somep,we have {b⁻¹a^p, b⁻¹a^−i1+p, b⁻¹a^−i2+p}={b⁻¹, b⁻¹a^−i1k, b⁻¹a^−i2k}.

Lemma 8. Let Gbe a Cayley digraph for the groupΓ =Z_no_kZ_m,n≥6 and k² ≡ 1 (modn), k 6= 1, with the generating set X = {a, b, baⁱ¹, baⁱ²} such that i₁, i₂6= 0, i₁6≡i₂ (modn). Then there existi₁,i₂ such that GG⁻¹.

Proof. Letφbe an isomorphism such thatφ(e) =e.

i) Ifi₁= 1, i₂= 3, then

{b⁻¹a^p, b⁻¹a^−1+p, b⁻¹a^−3+p}={b⁻¹, b⁻¹a^−k, b⁻¹a^−3k}, by Lemma 7. We can see that the above is equivalent with

{a^p, a^−1+p, a^−3+p}={e, a^−k, a^−3k}.

I) Leta^p=e,thenp= 0 and we have the following two possibilities:

Ifa^−1+p=a^−k,thek≡1 (modn) and this implies thatk= 1; a contradiction.

Ifa^−1+p=a^−3k then 3k≡1 (modn) and at the same timea^−3+p =a^−k; hence k ≡3 (modn) and this implies that k= 3. Thus 9 ≡1 (modn) which implies thatn= 8.

The remaining case to be investigated isZ8o₃Zm,ba=a³b.

II) Leta^−1+p=e,thenp= 1 and the possibilities to be considered area^p=a^−k anda^p=a^−3k.

Let a^p = a^−k. Then k ≡ −1 (modn) that is, k = n−1. Together with a^−3+p =a^−3k we obtain 3k≡2 (modn). Hence 3(n−1) = 3n−3≡2 (modn) and now 5≡0 (modn) which implies thatn= 5. Butn≥6; a contradiction.

Ifa^p=a^−3k then 3k≡ −1 (modn). Soa^−3+p =a^−k and it follows thatk≡2 (modn), thus k = 2. Consequently 6 ≡ −1 (modn) which implies that n = 7.

Butk²= 2²= 46≡1 (mod 7); a contradiction.

III) Leta^−3+p=e. Thenp= 3 and we have the following two cases:

Ifa^p=a^−k, thenk≡ −3 (modn). Thereforek=n−3 and soa^−1+p =a^−3k ⇒ 3k≡ −2 (modn). From this it follows that 3(n−3) = 3n−9≡ −2 (modn) and accordingly 7≡0 (modn); so nown= 7. Butk=n−3 = 4,k² = 4²= 166≡1 (mod 7); a contradiction.

If a^p = a^−3k, then 3k ≡ 3 (modn) and at the same time a^−1+p = a^−k. This implies that k ≡ −2 (modn) and consequently k = n−2. Thus, 3(n−2) = 3n−6 ≡3 (modn) and hence 9 ≡0 (modn). From this it follows that n= 3 or n = 9. Since n ≥ 6, the only possibility is n = 9. But k = n−2 = 7, k²= 7²= 496≡1 (mod 9); a contradiction.

ii) Leti1 = 1,i2= 4. We consider this possibility only for the caseZ8o₃Zm, ba=a³b,n= 8,k= 3. By part i),

{a^p, a^−1+p, a^−4+p}={e, a^−k, a^−4k}, thus

{a^p, a^7+p, a^4+p}={e, a⁵, a⁴}.

I) Leta^p=e. Thenp= 0 and it follows thata^7+p =a⁷.Buta⁷6=e, a⁷6=a⁵and a⁷6=a⁴.

II) Let a^7+p = e. Then we have p = 1 which implies that a^p =a. But a 6=e, a6=a⁵and a6=a⁴.

III) Leta^4+p=e. Thenp= 4 and consequentlya^7+p=a³. As in the above cases,

a³6=e,a³6=a⁵ anda³6=a⁴.

5. Groups of TypeZ_no_kZ_2m for n≤5 and Special m

In order to complete our investigation, the remaining cases to be considered are Γ₁=Z₃o₂Z_2m, ba=a²b,

Γ₂=Z₄o₃Z_2m, ba=a³b, Γ₃=Z₅o₄Z_2m, ba=a⁴b.

Lemma 9. Let Γ1=Z3o₂Z2m,ba=a²b, and let 2m= 2^r3^sq; where r≥1, s≥0,q >1,gcd(q,2) = gcd(q,3) = 1, soq >4. Let2^r3^s=p. Then

Γ1∼=Z3qo₂Zp.

Proof. We take the group generated by elementsaandb₁, namelyH₁=ha, b₁i, where b1 =b^p. Then b1a = b^pa = a^2pb^p =ab^p =ab1, because p is even. Now since |hb₁i| = q and 3 - q we have ha, b₁i ∼= Z₃ ×Z_q ∼= Z_3q. We can see that (aⁱb^j)aⁱ¹b1j₁

(aⁱb^j)⁻¹ =aⁱ²b1j₂

, and soha, b1iCΓ1. Let b2 =b^q, and hb2i=H2. ThenH₁∩H₂={e},andH₁∪H₂= Γ₁.

Accordingly

Γ₁=Z₃o₂Z_pq∼=Z_3qo_kZ_p. Remark 1. The groupZ3qo_kZp has a presentationZ3qo_kZp=hc, d|c^3q = b^p =e, dc=c^kdi where k^p ≡1 (mod 3q) and at the same time k≡ 2 (mod 3).

The isomorphismφ:Z3o₂Zpq→Z3qo_kZphas the formφ(a) =c^q andφ(b) =cd.

Remark 2. By similar arguments,

Γ2=Z4o₃Zpq∼=Z4qo_kZp,

where p = 2^r; r ≥ 1, gcd(q,2) = 1; q > 1. Here the group Z4q o_k Zp has a presentation Z_4q o_kZ_p =hc, d |c^4q =b^p =e, dc=c^kdiwhere k^p ≡1 (mod 4q) and k ≡ 3 (mod 4). The isomorphism φ:Z4o₃ Zpq → Z4q o_k Zp is given by φ(a) =c^q andφ(b) =cd.

Similarly

Γ3=Z5o₄Zpq∼=Z5qo₄Zp,

and p = 2^r5^s; r ≥ 1, s ≥ 0, gcd(q,2) = 1, gcd(q,5) = 1, q > 1. The group Z_5q o_k Z_p has a presentation Z_5qo_kZ_p =hc, d| c^5q =b^p =e, dc =c^kdiwhere k^p≡1 (mod 5q) andk≡4 (mod 5). The isomorphismφ:Z5o₄Zpq→Z5qo_kZp

has the formφ(a) =c^q andφ(b) =cd.

Lemma 10. Let

Γ₁=Z₃o₂Z_pq,

wherep= 2^r3^s;r≥1,s≥0,gcd(q,2) = 1,gcd(q,3) = 1,q >1;

Γ2=Z4o₃Zpq, wherep= 2^r;r≥1,gcd(q,2) = 1,q >1;

Γ3=Z5o₄Zpq,

wherep= 2^r5^s;r≥1,s≥0,gcd(q,2) = 1,gcd(q,5) = 1,q >1.

Then there are generating sets Xi,i= 1,2,3, such that for Gi =C(Γi, Xi) it holds that GiGi−1

.

Proof. By Lemma 9 and Remark 1, the groups Γi have the form Zn o_k Zm, wheren≥6,cⁿ =d^m=e,dc=c^kd,k^m≡1 (modn),k6= 1.

i) Ifk²6≡1 (modn),the result follows from Lemmas 2 and 3.

ii) Ifk²≡1 (modn), the result follows from Lemma 8.

6. Reverses of Cayley Digraphs of Valence 3

Lemma 11. Let Γ = Z3o₂Z2^r3^s, ba=a²b,r ≥1, s≥1,2^r =r1, 3^s=s1, 2^r3^s=m and letX ={a, b, ab^s1}. Let G=C(Γ, X). If an isomorphism φ:G→ G⁻¹ is such that φ(e) =ethen φ(aⁱb^j) =a⁻ⁱb^−j.

Proof. It is obvious that for eachg∈Gthere exists exactly one cycle throughg of the length 3 inG(G⁻¹), namelyCa(g)(C_a⁻₋₁¹(g)). SimilarlyCab^s1(g)(C_(ab⁻¹_s1)−1(g)) is the unique cycle of length r1, through g, and Cb(g)(C_b⁻₋₁¹(g)) is the unique cycle of length m, throughg in G(G⁻¹), respectively. In particular, from this it follows that the arcs of the form (g, gab^s1) must be mapped by an isomorphism to the arcs of the form (g⁰, g⁰(ab^s1)⁻¹). Hence an isomorphism (if any) must be the same as in the case with the generating set{a, b}. Now by Lemma 1 we have

φ(aⁱb^j) =a⁻ⁱb^−j.

Lemma 12. Let Γ = Z₃o₂Z₂r3^s, ba=a²b,r ≥1, s≥1,2^r =r₁, 3^s=s₁, 2^r3^s=mand letX ={a, b, ab^s1}. ThenC(Γ, X)C(Γ, X⁻¹).

Proof. Letφ(e) =e. By Lemma 11,φ(aⁱb^j) =a⁻ⁱb^−j. Hence in the digraphG we havee ^ab

s1

−−−→ab^s1and for the digraphφ(G) it holds thatφ(e) ^(ab

s1)⁻¹

−−−−−→(ab^s1)⁻¹. Therefore (ab^s1)⁻¹=a⁻¹b^−s1 and this implies thata^−2−s1b^−s1 =a⁻¹b^−s1. Con- sequently −2^−s1 ≡ −1 (mod 3) and thus 2^m−s1 ≡ 1 (mod 3), where m−s₁ is odd. But 2^2h+1≡2 (mod 3) for all positive integers; a contradiction.

Lemma 13. Let Γ = Z₅o₄Z₂r5^s, ba=a⁴b,r ≥1, s≥1,2^r =r₁, 5^s=s₁, 2^r5^s=m and let X ={a, b, ab^s1}. If an isomorphismφ: G→ G⁻¹ is such that φ(e) =e thenφ(aⁱb^j) =a⁻ⁱb^−j.

Proof. The proof is similar to the proof of Lemma 11.

Lemma 14. Let Γ = Z5o₄Z2^r5^s, ba=a⁴b,r ≥1, s≥1,2^r =r1, 5^s=s1, 2^r3^s=mand letX ={a, b, ab^s1}. ThenC(Γ, X)C(Γ, X⁻¹).

Proof. Letφ(e) =e. By Lemma 13,φ(aⁱb^j) =a⁻ⁱb^−j. Hence in the digraphG it holds that e ^ab

s1

−−−→ab^s1 and for digraph φ(G) we have φ(e) ^(ab

s1)⁻¹

−−−−−→(ab^s1)⁻¹.

Therefore (ab^s1)⁻¹=a⁻¹b^−s1 and this implies thata^−4−s1b^−s1 =a⁻¹b^−s1. Con- sequently −4^−s1 ≡ −1 (mod 5) and thus 4^m−s1 ≡ 1 (mod 5), where m−s1 is odd. But 4^2h+1≡4 (mod 5) for all positive integers; a contradiction.

Lemma 15. Let Γ =Di,i∈ {3,4,5}, be the dihedral group of the formDi = Zio_i−1Z2,ba=aⁱ⁻¹b. ThenC(Γ, X)∼=C(Γ, X⁻¹)for all X⊂Γ.

Proof. It is easy to see thatφ(aⁱb^j) =a^−i+pjb^−jdefines an isomorphismφ:G→ G⁻¹ for a suitable choice of pj. (The numbers pj depend on the generating

setX.)

7. Summary

In order to facilitate the formulation we set

Γ⁰_i=Zio_i−1Z2^r, r≥2, ba=aⁱ⁻¹b, i∈ {3,4,5} and

Di =Zio_i−1Z2, ba=aⁱ⁻¹b, i∈ {3,4,5}.

The above results about comparing Cayley digraphs of metacyclic groups with their reverses (disregarding the vertex valence) may now be summed up as follows.

Theorem 1. Let Γbe an abelian or metacyclic group.

If Γis abelian or D_i thenC(Γ, X)∼=C(Γ, X⁻¹)for every generating setX. If Γ is any metacyclic group such that Γ 6= Γ⁰_i and Γ 6= D_i then there exist generating sets X forΓsuch that C(Γ, X)C(Γ, X⁻¹).

The comparison of the Cayley digraphsC(Γ, X) andC(Γ, X⁻¹) for the groups Γ = Γi0 remains open.

Acknowledgement. I would like to thank J. ˇSir´aˇn for helpful discussion on the topic of this paper.

References

1.Alspach B.,Isomorphism and Cayley graphs on Abelian groups, Graph Symmetry (G. Hahn and G. Sabidussi, eds.), Kluwer, 1997, pp. 1–22.

2.Baskoro E. T., Brankovi´c L., Miller M., Plesn´ık J., Ryan J., ˇSir´aˇn J.,Large digraphs with small diameter: A Voltage Assignment Approach, JCMCC24(1997), 161–176.

3.Hafner P. R.,Large Cayley graphs and digraphs with small degree and diameter, Computa- tional Algebra and Number Theory (W. Bosma and van der Poorten, eds.), Kluwer, Amster- dam, 1995, pp. 291–302.

4.Heydemann M. C.,Cayley graphs and interconnections networks, Graph Symmetry (G. Hahn and G. Sabidussi, eds.), Kluwer, 1997, pp. 167–224.

5.Cai Heng Li,Isomorphism of Connected Cayley Digraphs, Graphs and Combinatorics (1997).

6. ,Isomorphism of Cayley Digraphs of Abelian Groups, to appear in Bulletin of Aus- tralian Mathematical Society.

7.Sabidussi G.,On a class of fixed-point-free graphs, Proc. Amer. Math. Soc.9(1958), 800–804.

M. Abas, Slovak Technical University, Department of Mathematics, Slovak Technical University, 917 24 Trnava, Slovakia;e-mail: [email protected]