ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 63-75
The automorphism groups of non-edge-transitive rose window graphs
Edward Dobson *
Department of Mathematics and Statistics, Mississippi State University PO Drawer MA Mississippi State, MS 39762
Istvan Kovacs , Stefko Miklavic
UP IAM and UP FAMNIT, University of Primorska Muzejski trg 2, 6000 Koper, Slovenia
Received 2 August 2012, accepted 7 September 2012, published online 20 June 2014
In this paper, we will determine the full automorphism groups of rose window graphs that are not edge-transitive. As the full automorphism groups of edge-transitive rose window graphs have been determined, this will complete the problem of calculating the full automorphism group of rose window graphs. As a corollary, we determine which rose window graphs are vertex-transitive. Finally, we determine the isomorphism classes of non-edge-transitive rose window graphs.
Keywords: Rose window graphs, automorphism group, isomorphism problem, vertex-transitive graph. Math. Subj. Class.: 05E18
1 Introduction
Rose windows graphs are defined as follows (we are using the notation and terminology as in [18]).
Definition 1.1. Let n be a positive integer and a,r e Zn (so arithmetic with a and r is done modulo n). The rose window graph Rn(a, r) is defined to be the graph with vertex set V = {Ai,Bi : i e Zn} and four kinds of edges:
• Aj Ai+1 These edges are called rim edges.
* Project sponsored by the National Security Agency under Grant Number H98230-11-1-0179. E-mail address: dobson@math.msstate.edu (Edward Dobson), istvan.kovacs@upr.si (Istvan Kovacs), stefko.miklavic@upr.si (Stefko Miklavic)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
64
Ars Math. Contemp. 9 (2015) 115-124
•	AiBi These edges are called in-spoke edges.
•	Ai+aBi These edges are called out-spoke edges.
•	BiBi+r These edges are called hub edges.
Rose window graphs were introduced recently by Steve Wilson [18], whose initial motivation was concerned with determining which of these graphs are edge-transitive (and if so what is their full automorphism group), as well as which of these graphs are the underlying graph of a rotary map. He proposed four conjectures concerning questions that he was interested in, and subsequently all of the conjectures have been shown to be true. Edge-transitive rose window graphs were characterized in [5, Theorem 1.2], verifying [18, Conjecture 11] (a graph is edge-transitive if its automorphism group acts transitively on the set of edges). The full automorphism groups of edge-transitive rose window graphs was determined in [6, §3], verifying [18, Conjectures 3 and 5]. The rose window graphs which are the underlying graph of a rotary map were found in [6, Theorem 1.1], answering [18, Question 3], Finally, [18, Conjecture 6] suggesting certain rose window graphs are isomorphic was verified in [6, Theorem 3.6].
Our goal is to essentially complete the work that has already been done regarding calculating the full automorphism groups of rose window graphs, as well determining exactly when two rose window graphs are isomorphic. In this paper, we will calculate the full automorphism groups of rose window graphs that are not edge-transitive (which will finish the problem of determining the full automorphism groups of rose window graphs), see Corollary 3.5 and Corollary 3.9. In Section 4, we will determine the isomorphism classes of rose window graphs that are not edge-transitive. The conclusion of the isomorphism problem for rose window graphs will be given in a sequel to this paper, where the isomorphism classes of edge-transitive rose window graphs will be found.
There are a few additional results in this paper that should be mentioned. First, in Lemma 2.2, we correct a small error in [18, Lemma 2] giving conditions on when a rose window graph has an automorphism that maps every rim edge to a hub edge and vice versa. Also, once the full automorphism groups of rose windows graphs are known, it is relatively straightforward to determine which of these graphs are vertex-transitive, and this is given in Theorem 3.10.
We should point out that our goal is a classical one. Namely, with graphs that have a large amount of symmetry, it is quite standard to ask for their full automorphism groups as well as their isomorphism classes. Perhaps the first family for which this has been done are the generalized Petersen graphs. The automorphism groups of these graphs were obtained by Frucht, Graver, and Watkins [4] in 1971, while the isomorphism classes were found by by Boben, Pisanski, and Zitnik [1]. Using very differrent techniques, Steimle and Staton [16] also determined the isomorphism classes for some, but not all, generalized Petersen graphs, and then used that result to enumerate the generalized Petersen graphs whose isomorphism classes they determined. Using Boben, Pisanski, and Zitnik's determination of the isomorphism classes of all generalized Petersen graphs, Petkovsek and Zakrajsek [9] enumerated generalized Petersen graphs. Determining the isomorphism classes of the rose window graphs should also yield an enumeration of the rose window graphs using techniques similar to those in [9].
Finally, in the last decade or so there has been considerable interest in tetravalent graphs satisfying various properties or in studying certain families of such graphs (for a sample of such work see [3, 7, 10, 11, 12, 13, 17]). See also [14], where a census of all locally
E. Dobson et al.: The automorphism groups of non-edge-transitive rose window graphs
65
imprimitive tetravalent arc-transitive graphs on up to 640 vertices was computed. This work will certainly contribute to the understanding of such graphs.
2 Preliminary results
We first give some obvious automorphisms of rose window graphs. Let Rn(a, r) be a fixed rose window graph and let G be the automorphism group of Rn(a, r). Observe that
Rn(a,r) = Rn(a, -r).	(2.1)
Define p, p : V ^ V by
p(Ai)= Ai+1 and p(Bi) = Bi+1 (i e Zn),	(2.2)
p(Ai) = A-i and p(Bi) = B-a-i (i e Zn).	(2.3)
Note that p,p e G, and therefore (p, p) < G. The action of (p, p) on the set of edges of Rn(a, r) has three orbits: the set of rim edges, the set of hub edges and the set of spoke edges.
The following result characterizes edge-transitive rose window graphs in terms of rim and spoke edges (we remark that the full automorphism groups of edge-transitive rose window graphs are given in [5], but the following formulation is nonetheless useful).
Lemma 2.1. The following are equivalent:
(i)	Rn(a,r) is edge-transitive.
(ii)	There is an automorphism of Rn(a, r) which sends a rim edge to a spoke edge.
(iii)	There is an automorphism of Rn(a, r) which sends a spoke edge to a hub edge.
Proof. It is clear that (i) implies (ii). To show that (ii) implies (iii), suppose that AiAi+1 is a rim edge mapped to a spoke edge by, say, a e G. Then a(AiAi+1) = AjBk for some j, k e Zn, and a(A£) = Bk for I = i or i +1. Of course, e1 = A£B£ and e2 = A£B£-a are spoke edges, and a(e1) and a(e2) are two edges incident with the spoke edge AjBk, and all three of these edges are incident with a(A£) = Bk. However, Bk is incident with two hub edges and two spoke edges, so at least one of a(e1) and a(e2) must be a hub edge.
To show (iii) implies (i), recall that the hub, spoke and rim edges are the edge orbits of (p, p). If a maps some spoke edge to a hub edge, we have that H = (p, p, a) has at most two edge orbits, and if there are two edge orbits, these consist of spoke and hub edges in one orbit and rim edges being the other orbit. However, if the rim edges form an orbit, then H must map {Ai : i e Zn} to itself, and so must map {Bi : i e Zn} to itself, and so must map hub edges to themselves. This then implies that H has three edge orbits, a contradiction. So H has one edge orbit and Rn (r, a) is edge-transitive.	□
It follows that if Rn(a, r) is not edge-transitive, then it has either two orbits or three orbits on edges. If Rn(a, r) has two orbits on edges, then one orbit consists of rim and hub edges, and the other consists of spoke edges. If Rn(a, r) has three orbits on edges, then the first one consists of rim edges, the second one consists of hub edges, and the third one consists of spoke edges.
Lemma 2 in [18] states that there is an automorphism of Rn(a, r) sending rim edges to hub edges and vice-versa if and only if r2 = ±1 (mod n) and ra = ±a (mod n).
66
Ars Math. Contemp. 9 (2015) 115-124
However, this is not entirely true. Namely, one can check that the rose window graph Ri6 (8,3) has an automorphism sending rim edges to hub edges and vice-versa via the map (i, j) ^ (i, 11 j). However it is clear that r2 =9 = ±1 (mod 16). We now wish to give a correct statement of [18, Lemma 2], and begin with a preliminary lemma.
Lemma 2.2. Let a be the automorphism of Rn(a, r), which sends every rim edge to a hub edge and vice versa. Assume also that a(A0) = B0 and a(B0) = A0. Then one of the following holds for every i G Zn:
(i)	a(Aj) = Bri and a(Bj) = Ari;
(ii)	a(Ai) = Bri anda(Bi) = A(r+a)i;
(iii)	a(Ai) = B-ri and a(Bi) = A-ri;
(iv)	a(Ai) = B-ri anda(Bi) = A(_r+a)i
Proof. Since a(A0) = B0 and a(Ai) are adjacent, we have a(Ai) G {Br, B-r}. It is easy to see that if a(Ai) = Br then a(Ai) = Bri for i G Zn, and that if a(Ai) = B-r then a(Ai) = B-ri for i G Zn. Now let s G Zn be such that a(Bi) = As and note that a(Bi) = Asi for i G Zn. Moreover, a(Ai) and a(Bi) = As are adjacent. Therefore, if
a(Ai) = Br, then s G {r, r + a}, and if a(Ai) = B-r, then s G {—r, —r + a}. The result follows.	□
Theorem 2.3. Let n > 3 bean integer and a, r G Zn \ {0}. Then there is an automorphism of Rn (a, r) sending every rim edge to a hub edge and vice-versa if and only if one of the following holds:
(i)	a = n/2, r2 = 1 (mod n) and ra = ±a (mod n);
(ii)	a = n/2, r2 = ±1 (mod n) and ra = ±a (mod n);
(iii)	n is divisible by 4, gcd(n, r) = 1, a = n/2 and (r2 + n/2) = ±1 (mod n).
Proof. We first show that if (i), (ii) or (iii) holds, then there is an automorphism of Rn(a, r) sending rim edges to hub edges and vice-versa. By (2.1) we can assume that ra = —a (mod n). Observe that if one of conditions (i), (ii) or (iii) holds, then gcd(n, r) = 1. If condition (i) or (ii) holds, then let a : V ^ V be defined by a(Ai) = Bri and a(Bi) = Ari. As gcd(n, r) = 1, a is a bijection. It is straightforward to check that a is also an automorphism of Rn(a, r).
If condition (iii) holds, then let a : V ^ V be defined by a(Ai) = Bri and a(Bi) = Ari+(n/2)i. Let us show that a is a bijection. As gcd(n, r) = 1, a maps {Ai | i G Zn} to {Bi | i G Zn} bijectively. As gcd(n, r) = 1, r is odd and n/2 is even, a maps {Bi | i G Zn} to {Ai | i G Zn} bijectively. Hence a is a bijection. It is then straightforward to check that a is also an automorphism of Rn(a, r).
We now show that if there is an automorphism a of Rn(a, r) sending rim edges to hub edges and vice-versa, then either (i), (ii) or (iii) holds. Note that in this case it must be the case that gcd(n, r) = 1. Since (p, acts transitively on the sets of hub, rim and spoke edges, we may assume (by replacing a by an appropriate element of (p, p, a}) that a(A0) = B0 and a(B0) = A0. Using (2.1) we can further assume that a(Ai) = Br. Therefore, by Lemma 2.2, a(Ai) = Bri and a(Bi) = Asi for i G Zn, where s G {r, r+a}. Since a2 sends A0 to A0 and Ai to Ars, we have rs = ±1 (mod n).
E. Dobson et al.: The automorphism groups of non-edge-transitive rose window graphs
67
Consider an in-spoke AjBj and an out-spoke BiAi+a. The automorphism a maps the in-spoke AjBj to BriAsi, and the out-spoke BiAi+a to AsiBri+ra. Hence one of BriAsi and AsiBri+ra is an in-spoke, and the other one is an out-spoke. Therefore, for every i e Zn either
ri = si (mod n) and ri + ra + a = si (mod n)	(2.4)
or
ri + ra = si (mod n) and ri + a = si (mod n).	(2.5)
Note that if (2.5) holds for i = 0, then a = 0, a contradiction. Therefore (2.4) holds for i = 0, implying ra = — a (mod n).
If (2.4) holds for i = 1, then we have r = s. Since rs = ±1 (mod n) this implies r2 = ±1 (mod n). If a = n/2, then (ii) holds. If a = n/2, then multiplying the congruence ra = —a (mod n) by r, we obtain r2a = —ar = a (mod n). If r2 = —1 (mod n), then —a = a (mod n). This implies that a = n/2, a contradiction. So if a = n/2, then r2 = 1 (mod n). Thus (i) holds.
Suppose now that (2.5) holds for i = 1. Then r + ra = s (mod n) and r + a = s (mod n). The two congruences then imply that ra = a (mod n) and r + a = s (mod n). Since also ra = —a (mod n), we have that a = n/2 and r is odd. Combining together r + n/2 = s (mod n) and rs = ±1 (mod n) gives us (r2 + n/2) = ±1 (mod n).
Observe that a(Bn/2) = As(n/2) = A(r+n/2)(n/2). Suppose n is not divisible by 4. As r and n/2 are both odd in this case, we have a(Bn/2) = A0 = a(B0). But this implies that a is not a bijection, a contradiction. Therefore, condition (iii) holds.	□
It follows from Theorem 2.3 that Rn(a, r) has two orbits of edges if and only if one of conditions (i) or (ii) in Theorem 2.3 is satisfied. We will also use the following result.
Lemma 2.4. Assume that Rn(a, r) is not edge-transitive and a = n/2. Then at least one of
(i)	r2 = ±1 (mod n)
(ii)	r2 + n/2 = ±1 (mod n)
does not hold.
Proof. If both (i) and (ii) above hold, then n/2 is congruent to 2, 0 or —2 modulo n. But this is only possible if n = 4. If n = 4, then r e {1, 3}. In both cases Rn(a, r) is edge transitive, a contradiction.	□
3 Groups of non edge-transitive rose window graphs
Before proceeding, we will require some additional notation. Let N = gcd(n, r) denote the number of inner cycles, and let L = n/N denote the length of an inner cycle. Here an inner cycle is a cycle induced by some set of vertices {Bi | i e Zn}. We now define three types of permutations on V(Rn(r, a)). To do this we assume that n is even. For
0 < I < n/2 — 1, we define a permutation on V(Rn(r, a)) by
a = (B^ B£+n/2).
If L is even, then for 0 < i < N — 1 we let
68
Ars Math. Contemp. 9 (2015) 115-124
pe — (Be, Be+n/2)(Be+N, Be+N+„/2)(B£+2W, Bi+2N+n/2) • • • (Bi+n/2-N, Bi+n-N).
Observe that pe interchanges every two antipodal vertices of the inner cycle containing Be. If L is odd, then for 0 < t < N/2 — 1 we let
Ye — (Be+o, Be+n/2)(Be+N ,Be+N+n/2)(Be+2 n ,Be+2 n+n/2) •••
(Bi+n-N, Bi+n-N+n/2).
Observe that yz interchanges the inner cycle containing Be and the inner cycle containing
Bi+n/2.
Lemma 3.1. Assume n is even. Then the following hold:
(i)	For 0 < t < n/2 — 1 we have ae — pea0p-e.
(ii)	If L is even, then for 0 < t < N — 1 we have pe — pep0p-e.
(iii)	If L is odd, then for 0 < t < N/2 — 1 we have yz — peYoP-e.
Proof. (i) It is straightforward to check that (pea0p-e)(Ai) — A for every i e Zn and that (pea0p-e)(Bi) — Bi for every i e Zn \{t,t + n/2}. Similarly we find that pea0p-e interchanges Be and Be+n/2. The result follows.
(ii)	Since Po — a0aNa2N • • • ari/2-N and Pe — aeae+Nae+2N • • • ae+n/2-N the result follows from (i) above.
(iii)	Similarly as (ii) above.	□
Lemma 3.2. Assume n is even. Then the following hold:
(i)	If L — 4 then ae is an automorphism of Rn(n/2, r) for 0 < t < n/2 — 1.
(ii)	If L is even, L — 4, then pe is an automorphism of Rn(n/2, r) for 0 < t < N — 1.
(iii)	If L is odd then Ye is an automorphism of Rn(n/2, r) for 0 < t < N/2 — 1.
Proof. Straightforward.	□
Lemma 3.3. Let Ga be the point-wise stabiliser of {Ao, A\,..., An-i} in G. Then the following hold:
(i)	If a — n/2 then Ga is trivial.
(ii)	If a — n/2 and L — 4, then Ga — (a0, a1,..., an/2-1).
(iii)	If a — n/2, L is even and L — 4, then Ga — (P0, P1,..., PN-1).
(iv)	If a — n/2 and L is odd, then Ga — (y0, Yu — ., YN/2-1).
Proof. Let a e Ga. Since the outer cycle (that is, the n-cycle induced by the vertices {Ai | i e Zn}) is fixed by a, for every i e Zn we have either a(Bi) — Bi and a(Bi-a) — Bi-a, or a(Bi) — Bi-a and a(Bi-a) — Bi. If a is nontrivial, then there exists j e Zn such that a(Bj) — Bj-a and a(Bj-a) — Bj. Applying the above comment to i — j + a we find that a(Bj+a) — Bj and a(Bj) — Bj+a. Therefore j — a — j + a, implying a — n/2. This proves (i).
E. Dobson et al.: The automorphism groups of non-edge-transitive rose window graphs	69
Assume L = 4. Every ag (1 < t < n/2 — 1) is clearly in Ga by Lemma 3.2 (i). Therefore (a0, ai,..., an/2_1) < Ga. Pick a G Ga. Since for every i (i G Zn) the automorphism a either fixes or interchanges Bj and Bi+n/2, we clearly have GA < (ao, ai,..., an/2_i). Therefore GA = (ao, ai,..., a.n/2_i).
Assume L is even, L = 4. By Lemma 3.2 (ii), (po, p1,..., pN_i) < Ga. Pick a G Ga. For every i (i G Zn) the automorphism a either fixes or interchanges Bj and Bj+n/2. However, since L = 4, if a interchanges Bj and Bj+n/2, then it must interchange every pair of antipodal vertices of the inner cycle containing Bj (and therefore also Bj+n/2). Hence Ga < (Po, Pi,..., Pn _i), implying Ga = (Po, Pi,..., Pn _i).
Assume L is odd. Again, by Lemma 3.2 (iii), we have (y0, y1, ..., yn/2_1) < Ga. Pick a G Ga and assume that a interchanges Bj and Bj+n/2. Note that Bj and Bj+n/2 are now in different inner cycles. Therefore, a must interchange every Bj of the inner cycle containing Bj with Bj+n/2 (which is contained in the same inner cycle as Bj+n/2). It is now clear that a G (70, Yi,..., Yn/2_i). This implies Ga = (yo, Yi,..., YN/2_i). □
Proposition 3.4. Let G{a} be the set-wise stabiliser of {Ao, A1,..., An_1} in G. Then the following hold.
(i)	If a = n/2 then G{ A} = (p, p).
(ii)	If a = n/2 and L = 4, then G{a} = (p, p,ao).
(iii)	If a = n/2, L is even and L = 4, then G{a} = (p, P, Po).
(iv)	If a = n/2 and L is odd, then G{a} = (p, P,Yo).
Proof. Let a G G{a}. Observe that the group induced by G{A} on A is (p, p), since the subgraph induced by A is a cycle. Therefore, pkpga G Ga for appropriate k G Zn, t G Z2. The result now follows from Lemma 3.3 and Lemma 3.1.	□
Corollary 3.5. Assume the automorphism group of Rn(a, r) has three orbits on the edge-set of Rn(a, r) (that is, Rn(a, r) does not satisfy any of the conditions (i) and(ii) of Theorem 2.3). Then the following hold.
(i)	If a = n/2 then G = (p, p).
(ii)	If a = n/2 and L = 4, then G = (p, p, ao).
(iii)	If a = n/2, L is even and L = 4, then G = (p, p,po).
(iv)	If a = n/2 and L is odd, then G = (p, p, yo).
Proof. If Rn(a, r) has three orbits on the edge-set, then one of these three orbits is the set of rim edges. Therefore G = G{a}. The result now follows from Proposition 3.4. □
We now turn our attention to the case when Rn(a, r) has two orbits on edges. In this case, in view of Lemma 2.1, the rim edges and the hub edges are in the same orbit, implying that gcd(n, r) = 1. Additionally, every automorphism of such a rose window graph must either fix the rim and hub or interchange them. Now suppose that we have an automorphism w that interchanges the rim and hub. For any automorphism S of Rn(a, r), we then have that wS or S is contained in Ga (noting that the set-wise stabilizer of {Aj : i G Zn} is the same as the set-wise stabilizer of {Bj : i g Zn}). Thus in order to calculate the automorphism groups of such graphs, we need only find one w that interchanges the rim
70
Ars Math. Contemp. 9 (2015) 115-124
and hub, and then G = (Ga, w). Of course, Ga is given in Lemma 3.3, and we need only consider the parameters listed in Theorem 2.3.
Definition 3.6. (i) Assume r2 = ±1 (mod n) and ra = —a (mod n). Then we define 6 : V ^ V by 6(A^ = Bri and 6(B^ = Ari.
(ii) Assume n is divisible by 4, r is odd, a = n/2 and (r2 + n/2) = ±1 (mod n). Then we define 7 : V ^ V by Y(Ai) = Bri and Y(Bi) = AH+(n/2)i.
Lemma 3.7. Assume r2 = ±1 (mod n) and ra = —a (mod n). Then 6 G G, where 6 is as defined in Definition 3.6(i).
Proof. Note that 6 is a bijection since gcd(n, r) = 1. The proof of the fact that 6 is an automorphism of Rn(a, r) is straightforward.	□
Lemma 3.8. Assume n is divisible by 4, r is odd, a = n/2 and (r2 + n/2) = ±1 (mod n). Then 7 G G, where 7 is as defined in Definition 3.6(ii).
Proof. We will show that 7 is a bijection as once this is established it is straightforward to verify that 7 G G. Clearly, 7 maps {Ai | i G Zn} bijectively to {Bi | i G Zn} as r is a unit. Similarly, 7 maps {Bi | i G Zn, i odd} bijectively to {Ai : i G Zn, i odd}, and {Bi | i G Zn, i even} to {Ai : i G Zn,i even}. Hence 7 is a bijection.	□
Corollary 3.9. Assume the automorphism group of Rn(a, r) has two orbits on the edge-set of Rn(a, r). Then, in view of Theorem 2.3, the following hold.
(i)	If a = n/2 and r2 = 1 (mod n), then G = (p, p, 6).
(ii)	If a = n/2, r2 = ±1 (mod n) and ra = —a (mod n), then G = (p, p, ,00, 6).
(iii)	If n is divisible by 4, r is odd, a = n/2 and (r2 + n/2) = ±1 (mod n), then
G = (P,M,^0,7).
We remark that in the case (ii) of the previous corollary when r2 = —1, listing as a generator is redundantas 62p = In (iii), is superfluous as if r2 + n/2 = —1 (mod n) then = Y2p while if r2 + n/2 = 1 (mod n) then = p-17pr7.
The full automorphism group of all rose window graphs are now known with the previous result. We may then check each case to determine which are vertex-transitive. But given that p is always an automorphism of Rn(a, r), Rn(a, r) is vertex-transitive if and only if there is an automorphism of Rn(a, r) which maps a rim vertex to a hub vertex and an automorphism which maps a hub vertex to a rim vertex. Recall that a rose window graph has either three, two or one edge orbit. It has at most two edge orbits if and only if there is an automorphism which maps rim edges (vertices) to hub edges (vertices) and vice versa. Therefore, a rose window graph is vertex-transitive if and only if it has either one or two edge orbits. The edge-transitive rose window graphs are given in [5] and their full automorphism groups were obtained in [6]. Combining this information with Theorem 2.3, we obtain the following result which characterizes exactly which rose window graphs are vertex-transitive.
Theorem 3.10. Let n > 3 be an integer and a, r G Zn \ {0}. The rose window graph Rn(a, r) is vertex-transitive if and only if one of the following holds:
(i) r2 = ±1 (mod n) and ra = ±a (mod n);
E. Dobson et al.: The automorphism groups of non-edge-transitive rose window graphs	71
(ii)	n is divisible by 4, r is odd, a = n/2 and (r2 + n/2) = ±1 (mod n);
(iii)	n is divisible by 2, a = n/2 ± 2, and r = n/2 ± 1;
(iv)	n is divisible by 12, a = ±(n/4 + 2), and r = ±(n/4 — 1) or a = ±(n/4 — 2) and r = ±(n/4 + 1); or
(v)	n is divisible by 2, a = 2b, where b2 = ±1 (mod n/2), and r is odd such that r = ±1 (mod n/2).
4 Isomorphisms of non edge-transitive rose window graphs
Let Rn(a, r) and Rn(ai, ri) be non edge-transitive rose window graphs. In this section we consider the problem of finding conditions on a, r, a1, r1 to ensure that R„(a, r) and Rn(a1, r1) are isomorphic. For the remainder of this paper, we will, as usual, denote the vertices of Rn(a, r) by {A0, A1,..., An-1} U {B0, B1,..., Bn-1}. The vertices of the rose window graph Rn(a1, r1) will be denoted in the natural way by {C0, C1,..., Cn-1}U {D0, D1,..., Dn-1}. Let p and ^ denote the automorphisms of Rn(a, r) defined at the beginning of this paper, and p1 and the corresponding automorphisms of Rn(a1, r1).
Theorem 4.1. Let R^a, r) and Rn(a1, r1) be rose window graphs. If one of the following holds, then Rn(a, r) and Rn(a1, r1) are isomorphic:
(i)	r1 = ±r and a1 = ±a;
(ii)	gcd(n,r) = 1, r1 = ±r-1, and a1 = ±ar-1;
(iii)	n is even with gcd(n, r) = gcd(n, n/2 + r), a = a1 = n/2 and r1 = ±(r + n/2);
(iv)	n is even with gcd(n, r) = gcd(n, n/2 + r) = 1, a = a1 = n/2 and r1 = ±(r + n/2)-1;
(v)	r = ±1, r1 = ±1, gcd(n, a) = gcd(n, a1) = 2 and aa1/2 = ±2(mod n);
(vi)	gcd(n, n/2—1) = 1, r = ±(n/2—1), r1 = ±(n/2—1), gcd(n, a) = gcd(n, a1) = 2 and aa1/2 = ±2(mod n).
Proof. (i) Note that Rn (a, r) = Rn (a, —r) and that an isomorphism between Rn (a, r) and Rn(—a, r) is given by ^(Aj) = C_j and ^>(Bj) = for i e Zn.
(ii)	Assume gcd(n, r) = 1, r1 = r-1, and a1 = ar-1. Then an isomorphism from Rn(a, r) to Rn(a1, r1) is given by ^>(Aj) = D_jr-i and ^>(Bj) = C_jr-i for i e Zn. The result now follows from (i) above.
(iii)	Let L = gcdnn,r) = gcd(n;/2+r), the length of the inner cycles of Rn(a, r) and Rn(a1, r1). We first claim that L is divisible by 4. To this end let n = 2jno and r = 2jro, where no and ro are odd positive integers. Since gcd(n, r) = gcd(n, n/2 + r), we also have that gcd(n, r) = gcd(n/2, r), and so j < i — 1. Assume now that j = i — 1. Then n/2 + r = 2j-1(no + ro) = 2j(no + ro)/2 (note that no + ro is even). This shows that gcd(n, n/2 + r) is divisible by 2j. Since gcd(n, r) is not divisible by 2j, we have a contradiction. Therefore, j < i — 2, and so L is divisible by 4.
Now define ^ : V(Rn(n/2, r)) ^ V(Rn(n/2, n/2 + r)) by ^(Aj) = Cj for i e Zn and ^(B£+fcr) = D£+fcr+fcn/2 for 0 < I < gcd(n, r) — 1 and 0 < k < L — 1. Choose an inner cycle C of Rn(n/2, r). Note that ^ maps C to an inner cycle of Rn(n/2, n/2 + r), and while doing so, the only change in every other vertex is changing Bj to A and on the remaining vertices ^ interchanges "antipodal vertices" of the cycle. This will produce a
72
Ars Math. Contemp. 9 (2015) 115-124
bijection if and only if L is divisible by 4, and so ^ is a bijection. It is now routine to check that ^ is an isomorphism. The result now follows from (i) above.
(iv)	Immediately from (ii) and (iii) above.
(v)	Assume r =1, r1 = 1, gcd(n, a) = gcd(n, a1) = 2 and aa1 /2 = 2 (mod n). Define a mapping from V(Rn(a,r)) to V(Rn(ai,ri)) by ^(A2i) = Ciai, ^(A2i+i) = Aai, ¿(Bk) = Ciai + 1, ^(B2i+1) = Djai+1 for 0 < i < n/2 - 1. Observe that ^ is a bijection as gcd(n, a1) = 2. It is also clear that ^ is an isomorphism. The result now follows from (i) above.
(vi)	Assume r = n/2 — 1, r1 = n/2 — 1, gcd(n, a) = gcd(n, a1) = 2 and aa1/2 = 2 (mod n). Note that since gcd(n, n/2 — 1) = 1, we have that n/2 is even. Furthermore, since gcd(n, a) = gcd(n, a1) = 2, a/2 and a1/2 are odd. Define a mapping from V(Rn(a,r)) to V(Rn(a1,n)) by ^j) = C^, ^¿+1) = Aai, ¿(Bij) = C1+iai, ^(B2i+n/2+1) = D1+iai for 0 < i < n/2 — 1. Observe that ^ is a bijection as gcd(n, a1) = 2. Furthermore, since a1/2 is odd (and so (n/4)a1 = n/2), ^ is an isomorphism. The result now follows from (i) above.	□
Theorem 4.2. Let ^ : Rn(a, r) ^ Rn(a1, r1) be an isomorphism which sends every rim edge of Rn(a, r) to a rim edge of Rn(a1, r1). Then one of the following holds:
(i)	a1 = ±a and r1 = ±r;
(ii)	n is even with gcd(n, r) = gcd(n, r + n/2), a = a1 = n/2 and r1 = ±(r + n/2).
Proof. Note that there exist k e Zn and I e {0,1} such that ^jpf ^ maps vertex Aj to vertex Q for each i e Zn. Therefore without loss of generality we can assume that ^ maps vertex Aj to vertex Cj for each i e Zn. Observe also that ^ maps the hub (spoke) edges of Rn(a, r) to the hub (spoke) edges of Rn(a1, r1). It follows that ^(B0) e {D0, D-ai}.
Claim 1: If ^(B0) = D0 then a1 = a. If, in addition, a = n/2, then r1 = ±r. Assume ^(B0) = D0. Since vertices B0 and Aa are adjacent, vertices ^(B0) = D0 and ^(Aa) = Ca are also adjacent. Since a = 0 this shows that a1 = a. Assume a = n/2. As Ar and Br are adjacent, ^(Ar) = Cr and ) are also adjacent. This shows that ) e {Dr, Dr-a}. As Ar+a and Br are adjacent, ^(Ar+a) = Cr+a and ) are also adjacent. This shows that ) e {Dr, Dr+a}. Note that since a e {0, n/2}, we have {Dr,Dr-a} n {Dr,Dr+a} = {Dr}. Therefore ) = Dr and r1 = ±r. This proves Claim 1.
Claim 2: If ^(B0) = D-ai then a1 = —a. If, in addition, a = n/2, then r1 = ±r. Rearranging the subscripts of the vertices {D0, D1,..., Dn-1} according to the rule x ^ x + a1 we get the graph Rn(—a1, r1) instead of the graph Rn(a1, r1). Furthermore, ^ : Rn(a, r) ^ Rn(—a1,r1) now maps vertex B0 to (the new) vertex D0. By Claim 1 we have —a1 = a and, if a = n/2, r1 = ±r. This proves Claim 2.
Assume now a = a1 = n/2 and r1 = ±r. Similarly as above, we find ^(B0) e {D0,Dn/2}. If ¿(B0) = D0, then ) e ,D_n} n {D,Dr+n/2}. Since n = ±r, we have r1 = ±(r+n/2). It is clear that we have gcd(n, r) = gcd(n, r1) = gcd(n, r+ n/2). The case ^(B0) = Dn/2 is treated similarly.	□
Theorem 4.3. Let ^ : Rn(a, r) ^ Rn(a1, r1) be an isomorphism which sends every rim edge of Rn(a, r) to a hub edge of Rn(a1, r1). Then one of the following holds:
(i) a1 = ±ar-1 and r1 = ±r-1;
E. Dobson et al.: The automorphism groups of non-edge-transitive rose window graphs	73
(ii) n is even with gcd(n, r) = gcd(n, r + n/2) = 1, a = ai = n/2 and ri = ±(r + n/2)-1.
Proof. Since ^ sends the rim edges of Rn (a, r) to the hub edges of Rn(a1,r1), it also sends the hub edges of Rn(a, r) to the rim edges of Rn(a1, r1). This shows that gcd(n, r) = gcd(n, r1) = 1. Rearranging the vertices of Rn(a1, r1) according to the rule Q ^ Dir-i
and Dj ^ Cir-i for i G Zn we obtain the graph Rn(-a1r-1,r-1) instead of the graph Rn(a1, r1). Moreover, ^ now satisfies the assumptions of Theorem 4.2. If Theorem 4.2 (i) holds, then r1 = ±r-1 and a1 = ±ar-1. If Theorem 4.2 (ii) holds, then n is even with
gcd(n, r + n/2) = gcd(n, r) = 1, a = —a1r-1 = n/2 and r-1 = ±(r + n/2). Since r1 is odd (recall that gcd(n, r1) = 1), —a1r-1 = n/2 is equivalent to a1 = n/2. The result follows.	□
Theorem 4.4. Let ^ : Rn(a, r) ^ Rn(a1, r1) be an isomorphism which sends every rim edge of R„(a, r) to a spoke edge of Rn(a1, r1). Then one of the following holds:
(i)	r = ±1, r1 = ±1, gcd(n, a) = gcd(n, a1) = 2 and aa1/2 = ±2 (mod n);
(ii)	gcd(n, n/2—1) = 1, r = ±(n/2—1), r1 = ±(n/2—1), gcd(n, a) = gcd(n, a1) = 2 and aa1/2 = ±2 (mod n).
Proof. Observe first that as the rim edges of Rn(a, r) are mapped to the spoke edges of Rn(a1, r1), the outer cycle of Rn(a, r) is mapped to a cycle of even length in Rn(a1, r1). This shows that n is even. Next, as the rim edges of Rn (a, r) are mapped to the spoke edges of Rn(a1, r1), the image of a rim edge has endpoints a rim vertex and a hub vertex. As hub edges and rim edges have no endpoints in common, the images of hub edges and rim edges have no endpoints in common. This implies that hub edges cannot be mapped either to the hub edges or the rim edges, and so the hub edges of Rn (a, r) are also mapped to the spoke edges of Rn(a1, r1). As the spoke edges of Rn (a1, r1) form a single edge orbit, we have that the hub and rim edges of Rn(a, r) also forms a single edge orbit. This shows that R„(a, r) and Rn(a1, r1) have two orbits on edges (and so gcd(n, r) = gcd(n, r1) = 1). We may thus assume that ^>(A0) = Q and ^(A1) g {Dj,Di-ai} for some i G Zn. Multiplying ^ by appropriate powers of and p1 we can further assume that ^(A0) = C0 and ^(A1) = D0. This implies that ^(A2i) = Ciai and ^(A2i+1) = Diai for 0 < i < n/2 — 1. Therefore, the order of a1 in Zn is n/2 and thus gcd(n, a1) = 2. Reversing the role of Rn(a, r) and Rn(a1, r1) we also obtain that gcd(n, a) = 2. Note that this also shows that n, a and a1 are all even. Since R4(2,1) is edge-transitive, we may assume that n > 6.
Observe now that ^(B0) g {C1,C-1}. We will assume ^(B0) = C1; the case ^(B0) = C-1 is treated similarly. Since B0 and Aa are adjacent, ^(B0) = C1 and
^(Aa) = C(a/2)ai are also adjacent. This shows that aa1/2 = 2(mod n). Furthermore, ) G {Co,C1,...,Cn_1} and ¿(B(2i+1)r) G {Do, D1,..., D«-} for 0 < i < n/2 — 1.
Recall that gcd(n, r) = gcd(n, r1) = 1. In particular, r, r1,r-1 and r-1 are odd. Since B1 = Br-ir this shows that ^(B1) G {D0, D1,..., Dn-1}. Since B1 and A1 are adjacent, ^(B1) and ^(A1) = D0 are also adjacent. Since B1 and Aa+1 are adjacent, ^(B1) and ^(Aa+1) = D(a/2)ai = D2 are also adjacent. Therefore ^(B1) g {Dri ,D-ri} n {D2+ri ,D2-ri}. This shows that r1 = ±1 or r1 = ±(n/2 — 1). Reversing the role of Rn(a, r) and Rn(a1, r1) we also obtain that r = ±1 or r = ±(n/2 — 1).
74
Ars Math. Contemp. 9 (2015) 115-124
Since Rn(a,r) = Rn(a, —r), we need only show r = 1 and r1 = n/2 — 1 or r = n/2 — 1 and r1 = 1 cannot occur.
Suppose that r = 1 and r1 = n/2 — 1. We saw in the previous paragraph that G {Dri, D_ri} n {D2+ri, D2-ri}. Since n > 6 this implies ^(B1) = Dn/2+1. But B0 and B1 are adjacent, and so ^(B0) = C1 and ^(B1) = Dn/2+1 are also adjacent. As 1 = n/2 +1 this implies n/2 +1 + a1 = 1 and thus a1 = n/2. It follows that gcd(n, a1) = n/2 > 3, contradicting gcd(n, a1) = 2.
Finally, if r = n/2 — 1 and r1 = 1, then by reversing the roles of Rn(a,r) and Rn(a1,r1), this case cannot occur by arguments in the previous case.	□
References
[1]	M. Boben, T. Pisanski and A. Zitnik, I-graphs and the corresponding configurations, J. Combin. Des. 13 (2005), 406-424.
[2]	E. Dobson and D. Witte, Transitive permutation groups of prime-squared degree, J. Algebraic Combin. 16 (2002), 43-69.
[3]	Y.-Q. Feng, J. H. Kwak, M.-Y. Xu, and J.-X. Zhou, Tetravalent half-arc-transitive graphs of order p4, European J. Combin. 29 (2008), 555-567.
[4]	R. Frucht, J. E. Graver and M. E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971), 211-218.
[5]	I. Kovacs, K. Kutnar and D. Marusic, Classification of edge-transitive rose window graphs, J. Graph Theory 65 (2010), 216-231.
[6]	I. Kovacs, K. Kutnar and J. Ruff, Rose window graphs underlying rotary maps, Discrete Math. 310 (2010), 1802-1811.
[7]	D. Marusic and C. E. Praeger, Tetravalent graphs admitting half-transitive group actions: alternating cycles, J. Combin. Theory Ser. B 75 (1999), 188-205.
[8]	J. D. P. Meldrum, Wreath products of groups and semigroups, Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 74, Longman, Harlow, 1995.
[9]	M. Petkovsek and H. Zakrajsek, Enumeration of I-graphs: Burnside does it again, Ars Math. Contemp. 2 (2009), 241-262.
[10]	P. Potocnik, A list of4-valent 2-arc-transitive graphs and finite faithful amalgams of index (4, 2), European J. Combin. 5 (2009), 1323-1336.
[11]	P. Potocnik and S. Wilson, Linking ring structures and tetravalent semisymetric graphs, Ars Math. Contemp. 7 (2014), 341-352.
[12]	P. Potocnik, P. Spiga and G. Verret, A census of small tetravalent arc-transitive graphs, http: //www.fmf.uni-lj.si/~potocnik/work_datoteke/Census4val-64 0.mgm
[13]	P. Potocnik, P. Spiga and G. Verret, Tetravalent arc-transitive graphs with unbounded vertex-stabilizers, Bull. Aust. Math. Soc. 84 (2011), 79-89.
[14]	P. Potocnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, J. Symb. Comp. 50 (2013), 465-477.
[15]	G. Sabidussi, On a class of fixed-point-free graphs, Proc. Amer. Math. Soc. 9 (1958), 800-804.
[16]	A. Steimle and W. Staton, The isomorphism classes of the generalized Petersen graphs, Discrete Math 309 (2009), 231-237.
[17]	X. Wang and Y.-Q. Feng, Tetravalent half-edge-transitive graphs and non-normal Cayley graphs, J. Graph Theory 70 (2012), 197-213.