ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 7 (2014) 215-235 Isomorphic tetravalent cyclic Haar graphs Hiroki Koike University of Primorska, UP IAM, Muzejski trg 2, SI6000 Koper, Slovenia Istvan Kovacs * University of Primorska, UP IAM and UP FAMNIT Muzejski trg 2, SI6000 Koper, Slovenia Received 31 January 2012, accepted 20 April 2013, published online 26 April 2013 Abstract Let S be a subset of the cyclic group Zn. The cyclic Haar graph H(Zn, S) is the bipartite graph with color classes Z+ and Z-, and edges {x+, y-}, where x, y G Zn and y - x G S .In this paper we give sufficient and necessary conditions for the isomorphism of two connected cyclic Haar graphs of valency 4. Keywords: Graph isomorphism, cyclic Haar graph, 4-BCI-group. Math. Subj. Class.: 20B25, 05C25, 05C60 1 Introduction Let S be a subset of a finite group G. The Haar graph H ( G, S) is the bipartite graph with color classes identified with G and written as G+ and G-, and the edges are {x+, y-}, where x, y G G and yx-1 G S. Haar graphs were introduced for abelian groups by Hladnik, Marusic and Pisanski [6], and were redefined under the name bi-Cayley graphs in [17]. A Haar graph H (G, S ) is called cyclic if G is a cyclic group. In this paper we consider the problem of giving sufficient and necessary conditions for the isomorphism of two cyclic Haar graphs. This is a natural continuation of the isomorphism problem of circulant digraphs which has been solved by Muzychuk [12]. It appears in the context of circulant matrices under the name bipartite Adam problem [16], and also in the context of cyclic configurations [2, 6]. The symbol Zn denotes the additive group of the ring Z/nZ of residue classes modulo n, and Z*n denotes the multiplicative group of units in Z/nZ. Two Haar graphs H(Zn, S) and H(Zn,T) are called affinely equivalent, written as H(Zn,S) =aff H(Zn, T), if S * Corresponding author. E-mail addresses: hiroki.koike@upr.si (Hiroki Koike), istvan.kovacs@upr.si (Istvan Kovacs) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 216 Ars Math. Contemp. 7 (2014) 201-213 can be mapped to T by an affine transformation, i.e., aS + b = T for some a e Z*n and b e Zn. It is an easy exercise to show that two affinely equivalent cyclic Haar graphs are isomorphic as usual graphs. The converse implication is not true in general, and this makes the following definition interesting (see [17]): we say that a subset S C Zn is a BCI-subset if for each T C G, H(Zn, S) = H(Z„,T) if and only if H(Zn, S) =aff H(Z„,T). Wiedemann and Zieve proved in [16, Theorem 1.1] that any subset S of Zn is a BCI-subset if |S| < 3 (a special case was proved earlier in [3]). However, this is not true if |S| > 4 (see [6, 16]), hence the first nontrivial case of the isomorphism problem occurs when |S| =4. In this paper we settle this case by proving the following theorem: Theorem 1.1. Two connected Haar graphs H(Zn, S) and H(Zn, T) with |S| = |T| =4 are isomorphic if and only if there exist ai, a2 e Zn and bi, b2 e Zn such that (1) aiS + bi = T; or (2) aiS + bi = {0, u, v, v + m} and a2T + b2 = {0, u + m, v, v + m}, where n = 2m, Zn = (u, v), 2 | u, 2u | m and u/2 ^ v + m/(2u)(mod m/u). Remark 1.2. A group G is called an m-BCI-group if every subset S of G with |S| < m is a BCI-subset (see [7, 17]). In this context [16, Theorem 1.1] can be rephrased as Zn is a 3-BCI-group for any number n; and Theorem 1.1 says that Zn is not a 4-BCI-group if and only if n is divisible by 8. This refines [16, Theorem 7.2] in which it is proved that, if Zn contains a non-BCI-subset of size k, k e {4, 5}, then n has a prime divisor less or equal to 2k(k - 1). Our approach towards Theorem 1.1 is group theoretical, we adopt the ideas of [1, 11]. In short terms the initial problem is transformed to a problem about the automorphism group of the graphs in question. Theorem 1.1 is proven in two steps: first it is settled for graphs H(Zn, S) with S satisfying additional conditions (see Theorem 3.1); then it is shown that, if S is not a BCI-subset, then it is affinely equivalent to a set satisfying the conditions of Theorem 3.1 (see Theorem 4.1). We conclude the introduction with the following modification of Theorem 1.1: Theorem 1.3. Two connected Haar graphs H(Zn, S) and H(Zn, T) with |S| = |T| =4 are isomorphic if and only if there exist ai, a2 e Zn and bi, b2 e Zn such that (1) aiS + bi = T; or (2) aiS + bi = {0, u, v, v + m} and a2T + b2 = {0, u + m, v, v + m}, where n = 2m, Zn = (u, v), 2 | u, 2u | m. Proof. In view of Theorem 1.1 it is sufficient to prove that H(Zn, S) = H(Zn, T) if aiS + bi = {0, u, v, v + m} and a2T + b2 = {0, u + m, v, v + m}, where n = 2m, Zn = (u, v), 2 | u, 2u | m and u/2 = v + m/(2u)(mod m/u). In fact, we are going to show below that there exist a e Zn and b e Zn such that a • {0, u, v, v + m} + b = {0, u + m, v, v + m}. Then (a-iaai) • S + a-i(abi + b - b2) = T, and so H(Zn, S) = H(Zn,T). H. Koike and I. Kovacs: Isomorphic tetravalent cyclic Haar graphs 217 Let us consider the following system of congruences: ux = — u + m(mod n) and vx = — u + v(mod n). (1.1) By the first congruence, using also that 2u | m, x may be written in the form x = (n/u)y — 1 + m/u. Plugging this in the second one, we obtain (vn/u)y = 2v — u — vm/u(mod n), which has an integer solution in y exactly when gcd(vn/u, n) | (2v — u — vm/u). Then gcd(vn/u, n) = n/ugcd(u,v), and since Zn = (u, v), n/u and gcd(u,v) are coprime. Since gcd(u, v) is clearly a divisor of 2v — u — vm/u, a solution in y exists if and only if n/u | (2v — u — vm/u), i.e., u = 2v — vm/u(mod 2m/u) (recall that n = 2m). On the other hand, one of the initial assumptions is u/2 = v + m/(2u)(mod m/u), and so u = 2v + m/u(mod 2m/u). We conclude that (1.1) has an integer solution if —vm/u = m/u(mod 2m/u). Now, the latter congruence holds because of the conditions 2 | u, 2 | n, and Zn = (u, v). Let a be a solution of (1.1). It follows from the above argument that gcd(a, m/u) = 1. Notice that, since 2u | m, 2 { a. Let d = gcd(a, u). By (1.1), av = —u + v(mod n), implying that d | v, and so d =1. We see that gcd(a, 2m) = 1, i.e., a G Zn. Choosing b = u + m, we finally get by (1.1), a • 0 + b = u + m, au + b = 0, av + b = v + m, and a(v + m) + b = v, as required. □ Theorem 1.3 becomes especially interesting when we compare it with the solution of the isomorphism problem of trivalent circulant digraphs. In fact, the same conditions can be derived from Muzychuk's general algorithm presented in [12]: two connected Cayley digraphs Cay(Zn, S) and Cay(Zn, T) with |S| = |T| =3 are isomorphic if and only if there exist ai, a2 G Z*n such that • a1S = T; or • aiS = {u, v, v + m} and a2T = {u + m, v, v + m}, where n = 2m, Zn = (u, v), 2 | u, and 2u | m. The natural question arises whether this phenomenon holds also for graphs of larger valencies. 2 A Babai type theorem In this paper every group, graph and digraph is finite. For a (di)graph r, the symbols V(r), E(r) and Aut(r) denote the set of its vertices, (directed) edges and the full group of its automorphisms, respectively. Regarding terminology and notation in permutation group theory we follow [5]. Let S be a subset of a group G. The Cayley digraph Cay(G, S) is the digraph with vertex set G, and its directed edges are (x, y), where x, y G G and yx-1 G S. Two digraphs Cay(G, S) and Cay(G, T) are called Cayley isomorphic, written as Cay(G, S) =cay Cay(G, T), if T = Sv for some group automorphism ^ G Aut(G). It is clear that such an automorphism induces an isomorphism between Cay(G, S) and Cay(G, T), and thus Cayley isomorphic digraphs are isomorphic as usual digraphs. It is also well-known that the converse implication is not true, and this makes sense for the following definition (see [1]): a subset S C G is a Cl-subset if for each T C G, Cay(G, S) = Cay(G, T) if and only if Cay(G, S) =cay Cay(G, T). The following equivalence was proved by Babai [1, 3.1 Lemma]. Theorem 2.1. The following are equivalent for every Cayley digraph Cay(G, S). 218 Ars Math. Contemp. 7 (2014) 201-213 (1) S is a Cl-subset. (2) Every two regular subgroups of Aut(Cay(G, S)) isomorphic to G are conjugate in Aut(Cay(G, S)). Theorem 2.1 essentially says that the CI-property of a given subset S depends entirely on the automorphism group Aut(Cay(G, S)). In this section we prove analogous results for cyclic Haar graphs. Let V = V(H(Z„, S)) be the vertex set of the Haar Graph H(Z„, S). Throughout this paper c and d denote the permutations of V defined by c : xe ^ (x +1)e and d : xe ^J (n - x)+ if £ =+, (2.1) I (n — x)+ if £ = —, where x G Zn and £ G {+, —}. It follows immediately that both c and d are automorphisms of any Haar graph H(Zn, S). Denote by C the group generated by c, and by D the group generated by c and d. The group D acts regularly on V, and D is isomorphic to D2n. Thus H(Zn, S) is isomorphic to a Cayley graph over D, and so Theorem 2.1 can be applied. The following corollary is obtained. Corollary 2.2. The implication (1) ^ (2) holds for every Haar graph H (Zn, S). (1) S is a BCI-subset. (2) Every two regular subgroups of Aut(H(Zn, S)) isomorphic to D are conjugate in Aut( H(Zn,S)). However, we do not have equivalence in Corollary 2.2 as it is shown in the following example. Example 2.3. Let r = H(Z10, {0,1,3,4}). Using the computer package Magma [4] we compute that r is edge-transitive and its automorphism group Aut(r) = D20 x Z4. Furthermore, Aut(r) contains a regular subgroup X which is isomorphic to D20 but X = D20, hence (2) in Corollary 2.2 does not hold. On the other hand, we find that for every subset T C Zi0 with 0 G T and |T| = 4, the corresponding Haar graph H(Z10,T) = r exactly when H(Z10,T) =aff r. Thus {0,1,3,4} is a BCI-subset, so (1) in Corollary 2.2 holds. □ Example 2.3 shows that the isomorphism problem of cyclic Haar graphs is not a particular case of the isomorphism problem of Cayley graphs over dihedral groups. We remark that the latter problem is still unsolved, for partial solutions, see [1, 13, 14]. Nonetheless, the idea of Babai works well if instead of the regular subgroup D we consider its index 2 cyclic subgroup C. We say that a permutation group G < Sym(Z+ U Z-) is bicyclic if G is a cyclic group which has two orbits: Z+ and Z-. By a bicyclic group of a Haar graph r = H(Zn, S) we simply mean a bicyclic subgroup X < Aut(r). Obviously, C is a bicyclic group of any cyclic Haar graph, and being so it will be referred to as the canonical bicyclic group. Let Iso(r) denote the set of all isomorphisms from r to any other Haar graph H(Zn, T), i.e., Iso(r) = {/ G Sym(V) : rf = H(Zn,T) for some T C Z„}. H. Koike and I. Kovacs: Isomorphic tetravalent cyclic Haar graphs 219 And let Ciso(r) denote the isomorphism class of cyclic Haar graphs which contains r, i.e., CiSo(r) = {rf: f e iso(r)}. Lemma 2.4. Let r = H(Zn, S) be a connected Haar graph and f be in Sym(V). Then f e iso(r) if and only if fCf-1 is a bicyclic group of r. Proof. Let f e iso(r). Then fCf-1 < Aut(r). Clearly, fCf-1 is a cyclic group. Since the sets Z+ and Z- are the color classes of the connected bipartite graph r, f preserves these color classes, implying that Orb(fCf-1, V) = {Z+, Z-}. The group fCf-1 is a bicyclic group of r. Conversely, suppose that fCf-1 is abicyclic group of r. Then C = f-1(f Cf-1)f < Aut(rf). Because that Orb(fCf-1, V) = {Z+, Z-}, the graph rf is connected and bipartite with color classes Z+ and Z-. We conclude that rf = H(Zn,T) for some T C Zn, so f e iso(r). The lemma is proved. □ Lemma 2.4 shows that the normalizer NSym(V)(C) C Iso(H(Zn,S)). The group NSym(V) (C) is known to consist of the following permutations: where r e Z^ and s,t e Zn. Note that, two Haar graphs H(Zn, S) and H(Zn,T) are from the same orbit under NSym(V)(C) exactly when H(Zn,S) =aff H(Zn,T). Let Caff (r) denote the affine equivalence class of cyclic Haar graphs which contains the graph r = H(Zn, S), i.e., Caff (r) = {rv : ^ e NSym(V)(C)}. It is clear that the isomorphism class Ciso(r) splits into affine equivalence classes: Our next goal is to describe the above decomposition with the aid of bicyclic groups. Let X be a bicyclic group of a connected graph r = H(Zn, S). Then g-1Xg is also a bicyclic group for every g e Aut(r), hence the full set of bicyclic groups of r is the union of Aut(r)-conjugacy classes. We say that a subset S C Iso(r) is a bicyclic base of r if the subgroups £C£-1, £ e S, form a complete set of representatives of the corresponding conjugacy classes. Thus every bicyclic group X can be expressed as Remark 2.5. Our definition of a bicyclic base copies in a sense the definition of a cyclic base introduced by Muzychuk [11, Definition, page 591]. Theorem 2.6. Let r = H(Zn, S) be a connected Haar graph with a bicyclic base S. Then (rx + s) if £ = +, (rx + t)+ if £ = —, (2.2) CiSo(r) = Caff(ri)ü ••• üCaff(rfc)*. X = g£C(g£) 1 for a unique £ G S and g G Aut(r). CiSo(r) = U 5eHCaff (r«). Proof. It follows immediately that, CiSo(r) d U Caff (r«). (2.3) 1Here we mean that CiSo(r) = Caff (ri) U • • • U Caff (rfc) and Caff n Caff (r) = 0 for every i, j € {1,..., k}, i = j. 220 Ars Math. Contemp. 7 (2014) 201-213 We prove that equality holds in (2.3). Pick S G Cisc,(T). Then S = rf for some f G Iso(r). By Lemma 2.4, f Cf-1 is a bicyclic group of r, hence fcf-1 = gee(ge)-1, e g s, g g Aut(r). Thus f-1ge = h, where h G NSym(V)(C). Then s = rf = rs«h-1 = (r« f-1. This shows that S G Caff (r« ), and so CiSo(r) ç U Caff (r«). «es In view of (2.3) the two sides are equal. Moreover, if Caff (r«1 ) n Caff (r«2 ) = 0 for e1 ,e2 G s, then r«1 = r«2h for some h G NSym(V)(C). Hence e2he-1 = g for some g G Aut(r), and so e1ce-1 = g-1 e2hch-1e2-1g = g-1 foCe-^g. The bicyclic subgroups e1Ce-1 and e2Ce-1 are conjugate in Aut(r), hence e1 = e2 follows from the definition of the bicyclic base s. We obtain that Caff (r«1 ) n Caff (r«2 ) = 0 whenever e1, e2 G s, e1 = e2, and so Cisc(r) = U«eSCaff (r«). The theorem is proved. " □ As a direct consequence of Theorem 2.6 we obtain the following corollary, analog of Theorem 2.1. Corollary 2.7. The following are equivalent for every connected Haar graph H (Zn, S ). (1) S is a BCI-subset. (2) Any two bicyclic groups of H (Zn, S) are conjugate in Aut(H (Zn, S )). In our last proposition we connect the BCI-property with the CI-property. For ae G V, in what follows Aut(H(Zn, S))ae denotes the vertex stabilizer of ae in Aut(H(Zn, S)). Proposition 2.8. Suppose that r = H(Zn, S) is a connected Haar graph such that for some a G Zn, Aut(r)0+ = Aut(r)a-. Then the following are equivalent. (1) S is a BCI-subset. (2) S — a = {s — a : s G S} is a CI-subset. Proof. For sake of simplicity we put A = Aut(r) and G = Aut(r){Z+}, i.e., the setwise stabilizer of the color class Z+ in Aut(r). Obviously, X < G for every bicyclic group X of r. Since A = G x (d) and d normalizes C, it follows that the conjugacy class of subgroups of A containing C is equal to the conjugacy class of subgroups of G containing C. Using this and Theorem 2.6, we obtain that S is a BCI-subset if and only if every bicyclic group is conjugate to C in G. H. Koike and I. Kovacs: Isomorphic tetravalent cyclic Haar graphs 221 Let W = {0+,a-} and consider the setwise stabilizer A{W}. Since A0+ = Aa-, A0+ < A{W}. By [5, Theorem 1.5A], the orbit of 0+ under A{W} is a block of im-primitivity (for short a block) for A. Denote this block by A and the induced system of blocks by S (i.e., S = { Aa : g G G}). Consider the element g = dca from D. We see that g switches 0+ and a-, hence A{W} = A0+ (g). Therefore, A = (0+)A{W} = (0+)Ao+ (g) = (0+)(a) = W, and so S = { {x+, (x + a)-} : x G Zn }. Define the mapping ^ : S ^ Zn by ^ : {x+, (x + a)-} ^ x, x G Zn. Now, an action of A on Zn can be defined by letting g g A act as xa = x G Zn. For g G A we write g for the image of g under the corresponding permutation representation, and for a subgroup X < A we let X = {x : x G X}. In this action of A the subgroup G < A is faithful. Also notice that, a subgroup X < G is a bicyclic group of r if and only if X is a regular cyclic subgroup of G. In particular, for the canonical bicyclic group C, C = (Zn)right, where (Zn)right denotes the group generated by the affine transformation x ^ x + 1, x G Zn. Pick g G G and (x, x + s - a) G Zn x Zn, where s G S. Then g maps the directed edge (x+, (x + s)-) to a directed edge (y+, (y + q)-) for some y G Zn and q G S. Since S is a system of blocks for G, g maps (x + s - a)+ to (y + q - a)+, and so g maps the pair (x, x + s - a) to the pair (y, y + q - a). We have just proved that g leaves the set { (x, x + s - a) : x G Zn, s G S } setwise fixed. As the latter set is the set of all directed edges of the digraph Cay(Zn, S - a), G < Aut(Cay(Zn, S - a)). For an automorphism h of Cay(Zn, S - a), define the permutation g of V by „ i(xh)+ if £ = +, q : xe ^ < xG Zn, £G {+,-}. g \ ((x - a)h + a)- if £ = -, } The reader is invited to check that the above permutation g is an automorphism of r. It is clear that g G G and g = h; we conclude that (5 = Aut(Cay(Zn, S - a)). Now, the proposition follows along the following equivalences: (1) ^^ Every bicyclic group of r is conjugate to C in G ^^ Every regular cyclic subgroup of G is conjugate to C in G ^ (2). The last equivalence is Theorem 2.1. □ Remark 2.9. Let us remark that the equality Aut(r)0+ = Aut(r)a- does not hold in general. For example, take r as the incidence graph of the projective space PG(d, q) where d > 2 and q is a prime power (i.e., r is the bipartite graph whose color classes are identified by the set of points and the set of hyperplanes, respectively, and the edges are defined by the incidence relation of the space). It is well-known that PG(d, q) admits a cyclic group of automorphisms (called a Singer subgroup) acting regularly on both the points and the hyperplanes. This shows that r is isomorphic to a cyclic Haar graph, and we may identify the set of points with Z+, and the set of hyperplanes with Z-, where 222 Ars Math. Contemp. 7 (2014) 201-213 n = (qd - 1)/(q - 1). The automorphism group Aut(T) = PrL(d + 1, q) x Z2; and as PrL(d + 1, q) acts inequivalently on the points and the hyperplanes, Aut(r)0+ cannot be equal to Aut(r)a- for any a G Zn. 3 Haar graphs H(Z2m, {0,u, + m}) In this section we prove Theorem 1.1 for Haar graphs H(Zn, S) satisfying certain additional conditions. Theorem 3.1. Let n = 2m and S = {0, u, v, v + m} such that (a) Zn = (u, v); (b) 1 < u < m, u | m; (c) Aut(H (Zn, S))0+ leaves the set {0-,u-} setwise fixed. Then H (Zn, S) = H (Zn, T) if and only if there exist a G Zn and b G Zn such that (1) aT + b = S; or (2) aT + b = {0, u + m, v, v + m}, and 2 | u, 2u | m, u/2 ^ v + m/(2u)(mod m/u). By (b) of Theorem 3.1 we have 2u < m. We prove the extremal case, when 2u = m, separately. Notice that, in this case the conditions in (2) of Theorem 3.1 that 2 | u, 2u | m and u/2 ^ v + m/(2u)(mod m/u) can be replaced by one condition: u = 2(mod 4). Lemma 3.2. Let S be the set defined in Theorem 3.1. If 2u = m, then H(Zn, S) = H (Zn, T) if and only if there exist a G Zn and b G Zn such that (1) aT + b = S; or (2) aT + b = {0, u + m, v, v + m} and u = 2(mod 4). Proof. Let d = gcd(n, v). Because of (u, v) = Zn we have that gcd(u, v, n) = 1, i.e., gcd(n/4, v) = 1, and this gives that d G {1,2,4}. Note that, if d =1, then necessarily 2 { u. Let us write v = «id, where gcd(v^ n) = 1. Let v-1 denote the inverse of v1 in the group Zn. Then the following hold in Zn (here we use that u = n/4): v-1v = d, v-1(v + m) = d + m and v-1u G {u, 3u}. We conclude that S is affinely equivalent to one of the sets Sj(d), i G {1,2} and d G { 1 , 2, 4} , where S1(d) = {0, u, d, d +2u} or S2(d) = {0, 3u, d, d + 2u}. The lemma follows from the following claims: (i) H(Zn,S1(1)) = H(Zn,S2(1)). (ii) H(Zn, S1(1)) =aff H(Zn, S1(d)) for d G {2,4}; (iii) H(Zn,S1(d)) =aff H(Zn,S2(d)) ^ d G {2,4} or (d =1 and u ^ 2(mod 4)); H. Koike and I. Kovacs: Isomorphic tetravalent cyclic Haar graphs 223 u-2 u-1 u-1 0 0 1 12 u-2 u-1 u-1 0 0 1 12 Figure 1: Haar graphs H(Z„,Si(l)) and H(Z„,S2(1)). (i): Define the mapping f : V ^ V by „ „ fxe if x e {0, 1,....u - 1} U {2u, .. . .3u - 1}, f : xe ^ < I (x + 2u)e otherwise. We leave for the reader to verify that f is in fact an isomorphism from H(Zn, S1(1)) to H(Zn, S2(1)) (compare the graphs in Figure 1; here the white vertices represent the color class Z+, while the black ones represent the color class Z-). (ii): Since d e {2,4}, u is an odd number. For d e {2,4} define rd e Zn as follows: _ i2 + u if u = 1(mod 4), _ i4 + u if u = 3(mod 4), r2 [2 + 3u ifu = 3(mod4), r4 [4 + 3u ifu = 1(mod4). It can be directly checked that rdS1(1)+ u = S1(d), so H (Zn,S1(1)) =aff H (Zn,S1(d)) for d e {2, 4}. (iii): If u is odd, then (2u+1)S1(d) = S2(d), hence H(Zn,S1(d)) =aff H(Zn,^2(d)). Since u is odd whenever d e {2, 4}, we are left with the case that d = 1 and u is even. If also u = 0(mod 4), then (u + 1)S1(1) + 3u = £2(1), and again H(Zn,S1(1)) =aff H (Zn,S2(1)). Suppose that d =1 and u = 2(mod 4). We finish the proof by showing that in this case H(Zn, S1(1)) =^aff H(Zn, S2(1)). Suppose that, there is an affine transformation ^ : x ^ rx + s, r e Z; and s e Zn, which maps the set S1(1) to S1(2). Then - (1+2u)^ = 2u in Zn. This implies that {1,1 + 2u}^ = {1,1 + 2u} and {0, u}^ = {0, 3u}, and hence r + s e {1,1 + 2u} and r{0,u} + s = {0, 3u}. A direct analysis shows that the above equations cannot hold if u = 2(mod 4). Thus H(Zn, £1(1)) =aff H(Zn, £2(1)), this completes the proof of (iii). □ Now, we turn to the case when 2u = m. Recall that the canonical bicyclic group C is generated by the permutation c defined in (1). For a divisor I | n, C will denote the H. Koike and I. Kovacs: Isomorphic tetravalent cyclic Haar graphs 242 u + 2 u + 2v + m 2v + u + u+m Jcb + u + m 2v + 2u 2u+m 2V+ 2u + m Vo Vi V2 Figure 2: The Haar graph H(Zn, S) subgroup of C generated by c£. It will be convenient to denote by S^ the partition of V into the orbits of C£, i.e., Sn = Orb(C£, V). Furthermore, we set nn,e for the homomorphism Vn,£ : Zn ^ Z^ defined by nn/(1) = 1. Observe that, if Se is, in addition, a system of blocks for the group A = Aut(H(Zn, S)), then an action of A can be defined on H(Z^, nn/(S)) by letting g g A act as for x g Z^ and for e, e' g {+, -}, (xe)g = ye {z£ : z G g = K : z G . (3.1) We denote by A(^) the corresponding kernel, and by gSe the image of an element g g G. Note that, if X is a bicyclic group of H(Zn, S), then XSe = {x^ : x g X} is a bicyclic group of H(Z£,nn,i(s)). Let S = {0, u, v, v + m} be the subset of Zn defined in Theorem 3.1. Let S be the partition of V defined by S = {X U X^1-0'0 : X G Orb(Cu, V)}, (3.2) where ^1,0,0 is defined in (2.2). We write S = {V0,..., VM-1}, where V = {(iv + ju)+, (iv + ju)- : j G {0,1,. .., (n/u) - 1}}. A part of H(Zn, S) is drawn in Figure 2 using the partition S. White and black colors represent again the color classes Z+ and Z-, respectively. For i G {0,1,..., u - 1}, let ej be the involution of V defined by (x + m)e if xe G Vi, xe otherwise. It is clear that each ej G Aut(H (Zn, S)), and also that e^j = ej ej for all i, j G {0,1,..., u - 1}. Let E = (e0, e1,..., eM-1). Thus E < Aut(H(Zn, S)) and E = Z^. For a subset I C {0,1,..., u - 1} let eI be the element in E defined by eI = f]j£/ ej. The following lemma about imprimitivity systems of blocks (systems of blocks for short) will be used throughout the paper. H. Koike and I. Kovacs: Isomorphic tetravalent cyclic Haar graphs 225 Lemma 3.3. Let r = H(Zn, R) be a Haar graph and suppose that R* C R such that the point stabilizer Aut(r)0+ fixes setwise R_, and let d = |(R* — R*)|, where R - R = jri — r2 : ri, r2 G R*}. Then the partition n of V defined by n = {X U X: X G Orb(Cn/d, V)}, where r G R*, is a system of blocks for Aut(r).2 Proof. For short we set A = Aut(r). Since R_ is fixed setwise by A0+, we may write R* = Ri U---U Rfc, where R__ is an A0+ -orbit for every i G {1,2,..., k}. Choose an arc (0+, r__) of r where we fix an element r G Ri for every i G {1,..., k}. We claim that, the orbital graph of A containing (0+, r__) is self-paired, and in fact it is equal to the Haar graph H(Zn, Rj) (for a definition of an orbital graph, see [5]). Define A as the color preserving subgroup of A. Then A = A x (^_1,0,0). Also, A = A0+ C, as C is transitive on Z+. Then the orbit of the arc (0+, r_) under A is (0+,r_)A = (0+,r_)Ao+ c^-1,»,^ = {(0+,rj_) : rj G Rj}C«,-1,°,o) = {(j+, (j + r^) _) : rj G Rj,j G Z„}<^-1,»,o) = {(j+, (j + ri) _): rj G Rj,j G Z„} U {((—j)_, (—j — ri) +): ri G Rj,j G Z„}, = {(j+, (j + ri) _): rj G Rj,j G Z„} U {((j + ri)_,j + ) : ri G Rj,j G Z„}, which is clearly equal to the set of arcs of H(Zn, Rj). The claim is proved. Since H(Zn,Rj) is an orbital graph, A < Aut(H(Zn,Rj)). Combining this with H(Zn, R*) = Uk=1H(Zn, Rj), we have that A < Aut(H(Zn, R*). Let £ be the connected component of H(Zn,R*) which contains 0+. Obviously, the set W of vertices contained in £ is a block for A. It is easy to verify that W = X U Xwhere X is the orbit of 0+ under Cn/d. The lemma follows. □ Lemma 3.4. Let S be the set defined in Theorem 3.1. If 2u = m, then the stabilizer Aut(H (Zn, S))0+ is given as follows. (1) If u ^ 2v(mod m/u), then Aut(H(Zn, S))0+ = E0+. (2) If u = 2v(mod m/u), then Aut(H(Zn, S))0+ = E0+ x F for a subgroup F < Aut(H(Zn, S))0+, |F| = 2. Proof. For short we set r = H(Zn, S) and A = Aut(r). Consider the partition S defined in (3.2). Applying Lemma 3.3 with R = S, R* = {0, u} and r = 0, we obtain that S is a system of blocks for A. The quotient graph r/S is a u-circuit if u > 2 and a 2-path if u = 2. Let g G A0+. Then g fixes the directed edge (V0, V1) of r/S, hence it must fix all sets V. Thus A0+ < A^), where A^) is the kernel of the action of A on S. Consider the action of A0+ on V0. The corresponding kernel is A(V»), the pointwise stabilizer of V0 in A, and the corresponding image is a subgroup of Aut(r[V0]), where 2 Notice that, n does not depend of the choice of the element r £ Rt 226 Ars Math. Contemp. 7 (2014) 201-213 r[Vo] is the subgraph of r induced by V0. Using that 2u = m, we show next that A(Vo) = E0+. It is clear that A(Vo) > E0+. We are going to prove that A(Vo) < E0+ also holds. Let g G A(Vo). Then for a suitable element e G (ei), the product ge fixes pointwise V0 and fix the vertex v- from block V1 (see Figure 2). Thus ge acts on V1 as the identity or the unique reflection of the circuit r[Vi] that fixes v-. If this action is not the identity, then ge switches v+ and (v + n - u)+, and so it must switch (v + u)- and (v + n - u)-. On the other hand, since (v + u)- is connected to u+ G V0, it follows that (v + u)- can only be mapped to (v + u + m)-, and so (v + n - u)- = (v + u + m)-, contradicting that 2u = m. We conclude that ge acts as the identity also on V1. Continuing in this way, we find that ge' is the identity with a suitable choice of e' G E0+, hence g = e'. The equality A(Vo) = E0+ together with Aut(r[V0]) = D4u imply that |A0+ : E0+1 < 2. Moreover, |A0+ : E0+1 = 2 holds exactly when A0+ contains an involution g for which g : 0- ^ u-. In the latter case A0+ = E0+ x (g) as g centralizes E (to see this, observe that g is in the kernel A(5), and acts on every block V as an element of D2n/u, whereas E acts on V as the center Z(D2n/u).) We settle the lemma by proving the following equivalence: A0+ = E0+ x Z2 ^^ u = 2v(mod m/u). (3.3) Suppose first that A0+ = E0+ x (g), where g G A0+ and g : 0- ^ u-. By (c) of Theorem 3.1, {v-, (v + m)-}Ao+ = {v-, (v + m)-}. Applying Lemma 3.3 with R = S, R* = {v, v + m} and r = v, we obtain that the set B = {0+, m+, v-, (v + m)-} is a block for A. The induced graph r[B] is a 4-circuit (again, see Figure 2). Denote by A{B} the setwise stabilizer of B in A, and by A^gj the permutation group of B induced by A{B}. As r[B] is a 4-circuit, Agg} < D8. This gives that {0+, m+} is a block for Agg}, and therefore it is also a block for A. We conclude that Sm = {X : X g Orb(Cm, V)} is a system of blocks for A. Consider the action of A on H(Zm, nn,m(S)) defined in (3.1). Then E < A(5m), while g G A(^m). This implies that gSm is an automorphism of H(Zm, nn,m(S)) which normalizes its canonical bicyclic group. This means that gSm = ¥V,s,t for some r G Z*m and s,t G Zm. Using that gSm : 0+ ^ 0+ and 0- ^ nn,m(u)-, we find that s = 0 and t = nn,m(u), and so ASm = ,^r,0,n„,m („)). (3.4) Also, gSm : nn,m(u)- ^ 0- and nn,m(v)- ^ nn,m(v)-, hence rn„,m(u) = -nn,m(u) and rn„,m(v) = (v - u) hold in Zm. From these r = — 1(mod m/u) and rv = v - u(mod m/u), i.e., u = 2v(mod m/u). The implication in (3.3) is now proved. Suppose next that u = 2v(mod m/u). Define the permutation g of V by J(«v - (i + j)u) + if £ = +, 1 (iv - (i + j - 1)^ if £ = -, g : (iv + ju)£ where i G {0,1,..., u - 1} and j G {0,1,..., n/u - 1}. We complete the proof by verifying that g G A0+. Since 0+ g =0+ and g : 0- ^ u-, this will imply that A0+ = E0+ x (g). Thus part of (3.3) is also proved. Choose an arbitrary vertex w G Z+ such that w = (iv + ju)+, i G {0,1,..., u - 1} and j G {0,1,..., n/u - 1}, and suppose for the moment that i < u - 1. Then w has the following neighbors: (iv + ju) , (iv + (j + 1)u) , ((i + 1)v + ju) , ((i + 1)v + (j + m/u)u) , H. Koike and I. Kovacs: Isomorphic tetravalent cyclic Haar graphs 227 where v + 1 G {0,1,..., u — 1}, and j + 1 and j + m/u are from {0,1,..., n/u — 1}. Thus these vertices are mapped by g to (iv — (i+j — 1)u)-, (iv — (i + j)u)-, ((i+ 1)v — (i + j)u)-, ((i+ 1)v — (i + j + m/u)u)-. A direct check shows that these are just the neighbors of wg = (iv — (i + j)u) + . Let i = u — 1. Then the neighbors of w are: (iv + ju)-, (iv + (j + 1)u)-, ((j + v)u)-, ((j + v + m/u)u)-, where j + v and j + v + m/u are from {0,..., n/u — 1}. Then these vertices are mapped by g to (iv — (i + j — 1)u)-, (iv — (i + j)u)-, ( —(j + v — 1)u)-, ( —(j + v + m/u — 1)u)-. The first two are clearly connected with wg = (iv — (i + j)u) + ; whereas the rest two are connected with wg if and only if the following equality holds in Zn: {iv — (i + j)u + v, iv — (i + j)u + v + m} = { —(j + v — 1)u, —(j + v + m/u — 1)u}. Using that v = u — 1, this reduces to { — (u — v)u, —(u — v)u + m} = {—vu, —vu + m}. Finally, observe that this equality holds if (u — v)u = vu(mod m), and the latter congruence follows from the initial assumption that u = 2v(mod m/u). □ Lemma 3.5. Let S be the set defined in Theorem 3.1. If 2u = m, then for the normalizer NAut(H(z„,S))(C) of C in Aut(H(Zn, S)), {2"-2 if 2 | u and (u = 2v(mod m/u) or u/2 = v(mod m/u)), 2u-1 otherwise. (3.5) Proof: For short we set A = Aut(H(Z„, S)) and N = NA(C). Since A = DA0+ and D < N, N = D(N n A+). The cases (1) and (2) in Lemma 3.4 are considered separately. Case 1. u = 2v(mod m/u). In this case, from Lemma 3.4, A0+ = E0+, hence |A| = 2"n. Let g G N n A+. Since g G E0+, it follows quickly that g = 1A or 2 | u and g = e1e3 • • • eM-1. Combining this with N = D(N n G+) we find that |N| = 4n if 2 | u, and |N| = 2n if 2 \ u. Formula (3.5) follows. 0 Case 2. u = 2v(mod m/u). From Lemma 3.4, A0+ = E0+ x F for a subgroup F < A0+, |F| = 2, hence |A| = 2"+1n. It follows from the proof of Lemma 3.4 that, there exists r G Z*m such that the following hold: rnn,m (u) = —nn,m(u) and rn„,m(v) = nn,m(v — u). 228 Ars Math. Contemp. 7 (2014) 201-213 Let s € Z*n such that nn,m(s) = r. Then su € { —u, — u + m} and sv € {v — u, v — u + m}. (3.6) Suppose that 2 { u. Then we get as before that N n E0+ is trivial. Notice also that, u = 2v + m/u(mod n/u), which follows from the assumption that u = 2v(mod m/u) and that 2 { u. Thus 2 \ m and 2 | (u + m), implying that in (3.6) we have su = —u. We obtain that ys,„,o € N n (A0+ \ E0+), and so |N n A0+1 = 2. Suppose next that 2 | u. Then |N n E0+1 = 2. It is easily seen that |N n A0+1 = 4 if and only if there exists r € Z*n such that ru = —u and rv = v — u hold in Zn. Consider the following system of linear congruences: xu = u(mod n), xv = v — u(mod n). (3.7) From the first congruence we can write x in the form x = yn/u — 1. Substitute this into the second congruence. We obtain that yvn/u = 2v — u(mod n). This has a solution if and only if gcd(vn/u, n) | (2v — u). Suppose that gcd(v, n) = 1. Using that (u, v) = Zn and that 2 | u, we obtain that gcd(v, m/u) = 1. However, then from the assumption that u = 2v(mod m/u) it follows that also gcd(v, u) = 1, which contradicts that (u, v) = Zn. Hence gcd(v, n) = 1, gcd(vn/u, n) = n/u, and so (3.7) has a solution if and only if u = 2v(mod n/u), or equivalently, u/2 = v(mod m/u) (recall that 2 | u and u | m). It is not hard to show that any solution to (3.7) is necessarily prime to n, hence is in Z*n. The above arguments can be summarized as follows: |N| = 8n if 2 | u and u/2 = v(mod m/u), and |N| = 4n otherwise. This is consistent with (3.5). The lemma is proved. □ Lemma 3.6. Let r € Z*n, r = 1 and s € Zn such that the permutation ^y,0,s is of order 2. Then the group (D, yv,0,s) contains a bicyclic subgroup different from C if and only if 8 | n, r = n/2 + 1, and s = 0 or s = n/2. Proof. Suppose that (D, yv,0,s) contains a bicyclic subgroup X such that X = C. Then X is generated by a permutation in the form c®^r,0,s. Since ^>2,0,s = , r2 = 1 in Zn, and we calculate that (cVr,0,s)2 sends x+ to (x + r(r + 1)i) + for every x € Zn. That Z+ is an orbit of X is equivalent to the condition that gcd(n, r + 1) = 2. Using this and that r2 — 1 = (r — 1)(r + 1) = 0(mod n), we find that n/2 divides r — 1, so r = 1 or r = n/2 + 1. Since r = 1, we have that r = n/2 + 1 and 8 | n. Then (^y,0,s)2 sends x-to (x + (n/2 + 2)s) Since (^y,0,s)2 = , we obtain that s = 0 or s = n/2. On the other hand, it can be directly checked that, if 8 | n, r = n/2 + 1 and s € {0, n/2}, then the permutation c^y,0,s generates a bicyclic subgroup of (D, yv,0,s). Obviously, this bicyclic subgroup cannot be C. The lemma is proved. □ Everything is prepared to prove the main result of the section. Proof of Theorem 3.1. The case that 2u = m is settled already in Lemma 3.2, hence let 2u = m. We consider the action of A = Aut(H(Zn, S)) on the system of blocks Sm defined in (3.1). We claim that the corresponding image ASm has a unique bicyclic subgroup (which is, of course, CSm). This is easy to see if A0+ = E0+, because in this case ASm = (DA0+ )Sm = DSm. Let A0+ = E0+. Then A0+ = E0+ x F for some subgroup F, |F| = 2. By (3.4), ASm = (D5m, yv,o,nn m(u)). Also, r = — 1(mod m/u), hence r =1 in Zm. By Lemma 3.5, ASm contains more than one bicyclic subgroup if and only if 8 | m, r = m/2 + 1 and H. Koike and I. Kovacs: Isomorphic tetravalent cyclic Haar graphs 229 Vn,m(u) e {0, m/2}. In the latter case u e {m, m/2}, which is impossible as u < m/2. Hence ASm contains indeed a unique bicyclic subgroup. We calculate next the number of bicyclic groups of H(Zn, S); we denote this number by B. In fact, we are going to derive the following formula: B i2"-2 if 2 | u and 2 { (m/u), (38) (2"-1 otherwise. Let g e G such that (g) is a bicyclic group of H(Zn, S). Since G = DA0+, g can be written as g = xy with x e D and y e A0+. Since (g) is a bicyclic group, g fixes the color classes setwise, implying that x e C. The image (g)5m is also a bicyclic subgroup of ASm, hence by the previous paragraph, (g)5m = CSm. Now, since x e C, y5m e C, from which y5m = . We conclude that x = c® e C for some i e {1,..., n — 1} with gcd(i, m) = 1, and y e E0+, and so y = e/ for a subset I C {1,..., u — 1}. Obviously, the product ^(n)B calculates the number of elements g e G such that (g) is a bicyclic group of H(Zn,S), where ^ denotes the Euler's totient function. Therefore, ^(n)B is equal to the number of elements in the form c®e/ that i e {1,..., n — 1}, gcd(i, m) = 1, I C {1,..., u — 1}, and (c®e/) is a bicyclic group of H(Zn, S). Let us pick c®e/ with i e {1,..., n — 1}, gcd(i, m) = 1, and I C {1,..., u — 1}. It is easily seen that e/c® = c®e/+®, where I + i = {x + i : x e I}, here the addition is taken modulo u. Using this and induction on u, it follows that (c®e/)u = cu®e/e/+® • • • e/+(„_i)®. Since gcd(i, m) = 1 and u | m, gcd(i, u) = 1, from which e/e/+® • • • e/+(„_i)® = (eoei • • • eu-i)11 cm|/| Thus (c®e/)u = cu(®+ m 1/1). This and gcd(i,u) = 1 show that (c®e/) is a semiregular group. Therefore, (c®e/) is a bicyclic group if and only if c®e/ is of order n, or equivalently, gcd (i + ^^|11, ^^) =1. (3.9) uu Notice that, since gcd(i, m) = 1, the greatest common divisor above is always equal to 1 or 2. Suppose at first that 2 | (m/u). Then 2 | m and i is odd. Hence (3.9) always holds. We obtain that the number of elements in A which generate a bicyclic group is ^(n)2u-1, and so B = 2u-1, as claimed in (3.8). Suppose next that 2 \ (m/u). Now, if 2 | u, then 2 | m, hence 2 \ i, and so (3.9) holds if and only if |11 is even. We deduce from this that B = 2u_2, as claimed in (3.8). Finally, if 2 \ u, then 2 \ m, and in this case (3.9) holds if and only if gcd(i, n) = 1 and |11 is even, or gcd(i, n) = 2 and |11 is odd. We calculate that B = 2u-1, and this completes the proof of (3.8). Let S be a bicyclic base of H(Zn, S). By (3.5) and (3.8) we obtain that, |S| > 1 if and only if |A : Na(C)| = 2u_2 andB = 2u-1. This happens exactly when (2 | u and (u ^ 2v(mod m/u) or u/2 = v(mod m/u)^ and (2 { u or 2u | 230 Ars Math. Contemp. 7 (2014) 201-213 After some simplification, |S| > 1 ^^ 2 | u, 2u | m and u/2 ^ v + m/(2u)(mod m/u). Suppose that |S| > 1. Then A contains exactly 2n-1 bicyclic subgroups, 2n-2 of which are conjugate to C. These 2n-1 subgroups are enumerated as: (ce/}, I C {1,..., u - 1}. For i € {1,..., u - 2}, ejcej = ce{i i+1}. We can conclude that the bicyclic subgroups split into two conjugacy classes: {(ce/} : I C {1, ...,u - 1}, |11 is even } and {(ce/} : I C {1,.. .,u - 1}, |11 is odd }. In particular, |S| = 2. Choose £ from Sym(V) which satisfies £c£-1 = ce1 and £ : 0+ ^ 0+, 0- ^ 0-. Then S can be chosen as S = {idV, £}. Also, {v-, (v + m)-}« = {v-, (v + m)-}, and since (ce1)u+m = cu, (u-)« = (0-)(cei)"+m« = (0-)«c"+m = (u + m)-. Thus H(Zn, S)« = H(Zn, {0, u + m, v, v + m}). The theorem follows from Theorem 2.6. □ 4 Proof of Theorem 1.1 Theorem 1.1 follows from Theorem 3.1 and the following theorem. Theorem 4.1. Let H(Zn, S) be a connected Haar graph such that |S| = 4 and S is not a BCI-subset. Then n = 2m, and there exist a € Z^ and b € Zn such that aS + b = {0, u, v, v + m} and the conditions (a)-(c) in Theorem 3.1 hold. Before we prove Theorem 4.1 it is necessary to give three preparatory lemmas. For an element i € Zn, we denote by |i| the order of i viewed as an element of the additive group Zn. Thus we have |i| = n/ gcd(n, i). Lemma 4.2. If R = {i,n - i, j} is a generating subset of Zn with |i| odd, then R is a Cl-subset. Proof. For short we set A = Aut(Cay(Zn, R)) and denote by A0 the stabilizer of 0 € Zn in A. Clearly, A0 leaves R setwise fixed. If A0 acts on R trivially, then A = Zn, and the lemma follows by Theorem 2.1. If A0 acts on R transitively, then Cay(Zn, R) is edge-transitive. This condition forces that R is a Cl-subset (see [10, page 320]). We are left with the case that R consists of two orbits under A0. These orbits must be {i, n - i} and {j}. It is clear that A0 leaves the subgroups (i} and (j} fixed; moreover, the latter set is fixed pointwise, and since |i| is odd, (i} consists of (|i| - 1)/2 orbits under A0, each of length 2, and one orbit of length 1. We conclude that Zn = (i} x (j}, and also that A is permutation isomorphic to the permutation direct product ((Z|j|)right x (n}) X (Z|j| )right. For I € {|i|, |j|}, (Z£)righi is generated by the affine transformation x ^ x + 1, and n is the affine transformation x ^ -x. We leave for the reader to verify that the above group has a unique regular cyclic subgroup. The lemma follows by Theorem 2.1. □ Lemma 4.3. Let n = 2m and R = {i, n - i, j, j + m} be a subset of Zn such that (a) R generates Zn; (b) |i| is odd; H. Koike and I. Kovacs: Isomorphic tetravalent cyclic Haar graphs 231 (c) the stabilizer Aut(Cay(Zn, R))0 leaves the set {i, n — i} setwise fixed. Then R is a Cl-subset. Proof. For short we set A = Aut(Cay(Zn, R)). Let T be a subset of Zn such that Cay(Zn, R) = Cay(Zn, T) and let f be an isomorphism from Cay(Zn, R) to Cay(Zn, T) such that f (0) = 0. Let us consider the subgraphs ri = Cay(Z„, {i, n — i}) and r = Cay(Z„, {j,j + m}). By condition (c), the group A preserves both of these subgraphs, that is, A < Aut(r^) for I G {1, 2}. As f is an isomorphism between two Cayley graphs, f (Zn)rightf-1 < A. Then f(Zn)rightf-1 < A < Aut(r), implying that f maps r to a Cayley graph Cay(Z„,T£) for both I G {1,2}. Clearly, T = T1 U T2. It was proved by Sun [15] (see also [10]) that every subset of Zn of size 2 is a CI-set. Using this, it follows from Cay(Zn, {i,n — i}) = Cay(Zn,T1) that T = a{i, n — i} for some a G Z£. Letting t1 = ai, we have T = {t1,n —11} such that |i| = |t1|. In the same way, T2 = a'{j,j + m} for some a' G Z£, and letting t2 = a'j, we have T2 = {t2,t2 + m} with |t21 = |j|. Since f (0) = 0, f maps {i, n — i} to T\ = {t1, n — t1} and {j, j + m} to T2 = {t2, t2 + m}. We claim that the partition of Zn into the cosets of (m) is a system of blocks for Aut(r2), hence also for the group A < Aut(r2). Let us put A = Aut(r2). Then A0 leaves the set T = {j, j+m} setwise fixed. Thus the setwise stabilizer A{T} of the set T in A can be written as A{T} = A{T} n A = A{T} n Ao(Z„)right = Ao(A{T} n (Z„)right) = A40(mright). Here (Zn)right is generated by the affine transformation x ^ x +1, and mright is the permutation x ^ x + m for every x G Zn. Thus A0(mright) is a subgroup of A which clearly contains A0. By [5, Theorem 1.5A], the orbit of 0 under the group A0 (mright) is a block for A. Now, the required statement follows as the latter orbit is equal to 0A0 {mright > =0(mright) = (m) . Since the partition of Zn into the cosets of (m) is a system of blocks for A, the isomorphism f induces an isomorphism from Cay(Zm, nn,m(R)) to Cay(Zm, nn,m(T)), we denote this isomorphism by /. Note that, f (0) = 0 for the identity element 0 G Zm. The set nn,m(R) satisfies the conditions (a)-(c) of Lemma 4.2, hence it is a CI-subset. This means that f is equal to a permutation x ^ rx for some r G Z^. Let s G Z^ such that nn,m(s) = r. Then nn,m(si) = nn,m(s)n«,m(i) = n«,m(t1), and so the following holds in Zn: si = t1 or si = t1 + m. (4.1) The order |t1| = |i| is odd by (b), implying that |t1| = |t1 + m|, and so si = t1 holds in (4.1). We conclude that sR = T, so R is a CI-subset. The lemma is proved. □ Lemma 4.4. Let n = 2m and S = {0, u, v, v + m} such that (a) S generates Zn; (b) 1 < u < n, u | n but u \ m; (c) Aut(H (Zn,S))0+ leaves the set {0-,u-} setwise fixed. Then S is a BCI-subset. 232 Ars Math. Contemp. 7 (2014) 201-213 Proof. Let 6 be the partition of V defined in (3.2). Applying Lemma 3.3 with R = S, R* = {0, u} and r = 0, we obtain that 6 is a system of blocks for A = Aut(H(Zn, S)). Thus the stabilizer A0+ leaves the set V0 setwise fixed, and we may consider the action of A0+ on V0. The subgraph of H(Zn, S) induced by the set V0 is a circuit of length 2n/u, thus A0+ fixes also the vertex on this circuit antipodal to 0+. We find that this antipodal vertex is (u/2 + m)-. Therefore, A0+ = A(m+u/2)-, and thus S is a BCI-subset if and only if S — u/2 + m is a CI-subset of Zn, see Proposition 2.8. The latter set is S — u/2 + m = { u/2 + m, —u/2 + m, v — u/2, v — u/2 + m }. Since u { m, u is even and the order |u/2 + m| is odd. Lemma 4.3 is applicable to the set S — u/2 + m (choose i = u/2 + m and j = v — u/2), it gives us that S — u/2 + m is a CI-subset. This completes the proof. □ Proof of Theorem 4.1. Let S be the subset of Zn given in Theorem 4.1. We deal first with the case when the canonical bicyclic group C is normal in A = Aut(H(Zn, S)). Case 1. C < A. By Theorem 2.6, there is a bicyclic group X of H(Zn, S) such that X = C. Since C < A, X is generated by a permutation in the form c®^rj0jS, r G , s G Zn, andord(^yj0jS) > 2. The permutation ^yj0jS acts on both Z+ and Z- as an affine transformation. This fact together with the connectedness of H(Zn, S) imply that, ^yj0jS acts faithfully on S-. Thus ord(^r,0,s) < 4. Suppose that ord(^yj0jS) = 4. We may assume without loss of generality that S- can be obtained as S- = { (0-) 2. We prove first that Cn/ni < A. Applying Lemma 3.3 with R = S, R* = S1 and r = s1 G S1, we obtain that the partition S = {X U X^1,'i,_'i : X G Orb(Cn/ni, V)}, m m 234 Ars Math. Contemp. 7 (2014) 201-213 is a system of blocks for A. Let us consider the action of A(^ (the kernel of A acting on S) on the block of S which contains 0+. Denote this block by A, and by A' the block which contains s- for some s G S2. Notice that, the subgraph of H(Zn, S) induced by any block of S is a circuit of length 2ni, and when deleting these circuits, the rest splits into pairwise disjoint circuits of length 2n2. Let E denote the unique (2n2)-circuit through s-. Now, suppose that g G A(^ which fixes A pointwise. If V(E) n A = {0+}, then g must fix the edge {0+, s-}, and so fixes also s-. If V(E) n A = {0+}, then |V(E) n A| = n > 2. This implies that g fixes every vertex on E, in particular, also s-. The block A' has at least n1 vertices having a neighbor in A, hence by the previous argument we find that all are fixed by g. Since n1 > 2, A' is fixed pointwise by g. It follows, using the connectedness of H(Zn, S), that g = idV, hence that A(^ is faithful on A. Thus Cn/ni is a characteristic subgroup of A(5), and since A^) < A, Cn/ni < A. Let G be the unique normal subgroup of A that fixes the color classes Z+ and Z-. We consider N = G n CA(Cn/ni). Then C < N and N < A. Pick g G N0+ such that g acts non-trivially on S-. Since N centralizes Cn/ni, g fixes pointwise the orbit of 0+ under Cn/ni, and hence also A. Then g2 fixes S- pointwise, and so also A'. We conclude that g2 = idV, and that either N = C, or N = C x (g). The case N = C is impossible because C ^ A. Let N = C x (g). Then (S-)g = S- (for both i G {1, 2}), hence S, is a union of orbits of g. As g normalizes C and fixes 0+, g = yv,0,s. Recall that ord(g) = 2. If r =1, then by Lemma 3.6, either C is the unique cyclic subgroup of N, or 8 | n, r = n/2 +1 and s = 0 or s = n/2. In the former case C is characteristic in N, and since N < A, C < A, a contradiction. Therefore, we are left with the case that r = 1 (and so s = n/2), or 8 | n, r = n/2 + 1 and s = 0 or s = n/2. Then every orbit of g is of length 1 or 2, and if it is of length 2, then is in the form {je, (j + m)e} as we proved in Case 1. Since n, > 2, we see that S- must be fixed pointwise by g for both i G {1,2}. This, however, contradicts that g was assumed to act non-trivially on S-; and so n1 = 2. This means that 2 | n, say n = 2m, and the group generated by the set S1 - S1 = {x - y : x, y G S1} is equal to {0, m}. Then we can write S1 = {s, s + m}. It can be proved as before that there exist a G and b G Zn such that aS2 + b = {0, u} for some divisor u of n. Then, letting v = as + b, we get aS1 + b = {v, v + m}. We finish the proof of this case by showing that the set R = aS + b = {0, u, v, v + m} satisfies the conditions (a)-(c) of Theorem 3.1. (a): As H(Zn, S) is connected, H(Zn, R) is also connected. This implies that {u, v} is a generating set of Zn. (c): Since S1 and S2 are left fixed setwise by A, Aut(H(Zn,R))0+ leaves the set {0-, u- } setwise fixed. (b): If u =1, then Aut(H(Zn, {0, u})) < D4n. But then C < A, which is a contradiction. We conclude that 1 < u, and by Lemma 4.4, u | m also holds, i.e., 1 < u < m and u | m, as required. □ Acknowledgements In this research both authors have been supported in part by "Javna agencija za raziskovalno dejavnost Republike Slovenije", program no. P1-0285. The authors are much grateful to one of the anonymous referees, whose constructive comments helped to improve the quality of the presentation considerably. H. Koike and I. Kovacs: Isomorphic tetravalent cyclic Haar graphs 235 References [1] L. Babai, Isomorphism problem for a class of point-symmetric structures, Acta Math. Acad. Sci. Hungar. 29 (1977), 329-336. [2] M. Boben, T. Pisanski, and A. Zitnik, I-graphs and the corresponding configurations, J. Com-bin. Designs 13 (2005), 406-424. [3] T. G. Boreham, I. Z. Bouwer, and R. W. Frucht, A useful family of bicubic graphs, Graphs Combin. (1973), 213-225. [4] W. Bosma, J. Cannon, and C. Playoust, The Magma Algebra System I: The User Language, J. Symbolic Comput. 24 (1997), 235-265. [5] J. D. Dixon and B. Mortimer, Permutation groups, Graduate Texts in Mathematics 163, Springer-Verlag, New York, 1996. [6] M. Hladnik, D. Marusic, and T. Pisanski, Cyclic Haar graphs, Discrete Math. 244 (2002), 137152. [7] W. Jin, W. Liu, A classification of nonabelian simple 3-BCI-groups, European J. Combin. 31 (2010), 1257-1264. [8] I. Kovacs, B. Kuzman, and A. Malnic, On non-normal arc transitive 4-valent dihedrants, Acta Math. Sinica (Engl. ser.) 26 (2010), 1485-1498. [9] I. Kovacs, B. Kuzman, A. Malnic, and S. Wilson, Characterization of edge-transitive 4-valent bicirculants, J. Graph Theory 69 (2012), 441-463. [10] C. H. Li, On isomorphisms of finite Cayley graphs - a survey, Discrete Math. 256 (2002), 301-334. [11] M. Muzychuk, On the isomorphism problem for cycic combinatorial objects, Discrete Math. 197/198 (1999), 589-606. [12] M. Muzychuk, A solution of the isomorphism problem for circulant graphs, London Math. Soc. 88 (2004), 1-41. [13] H. Qu, J. Yu, On isomorphism of Cayley digraphs on dihedral groups, Australian J. Combin. 15 (1997), 213-220. [14] P. Spiga, On the Cayley isomorphism problem for a digraph with 24 vertices, Ars Math. Con-temp. 1 (2008), 38-43. [15] L. Sun, Isomorphisms of circulants with degree 2, J. Beijing Ins. Technol. 9 (1984), 42-46. [16] D. Wiedemann, M. E. Zieve, Equivalence of sparse circulants: the bipartite Adam problem, preprint arXiv:0706.1567v1 [math. CO] (2007). [17] S. J. Xu, W. Jin, Q. Shi, and J. J. Li, The BCI-property of the Bi-Cayley graphs, J. Guangxi Norm. Univ.: Nat. Sci. Edition 26 (2008), 33-36.