Also available at http://amc.imfm.si
ARS MATHEMATICA CONTEMPORANEA 1 (2008) 7–19
Rose Window Graphs
Steve Wilson
Department of Mathematics and Statistics
Northern Arizona University, Flagstaff, AZ 86011, USA
Received 25 July 2007, accepted 17 May 2008, published online 17 June 2008
Abstract
This paper introduces a family of tetravalent graphs called rose window graphs, denoted
by Rn(a, r), and investigates their symmetry properties. Four families of these graphs are
shown to be edge-transitive and it is conjectured that every Rn(a, r) which is edge-transitive
belongs to one of these families. Proofs and conjectures about the size of a dart-stabilizer and
about regular maps containing these graphs are also offered.
Keywords: Graph, automorphism group, symmetry, edge-transitive graph, regular map, tetravalent
graph, rose window.
Math. Subj. Class.: 05C25, 20F65
1 Introduction
The graphs considered in this paper arose from a talk by the author at GEMS ’97 concerning
regular maps and their underlying graphs; the talk later became the paper [5]. At the end,
it shows pictures of five graphs of maps, the smallest graphs not then known to be part of
a family of graphs. As reported in [5], after the talk, Dragan Marušič and Tomaž Pisanski
observed that one of the graphs could be redrawn to give three of the graphs very similar
figures. The generalization of those three pictures is the topic of this paper.
2 Definitions
In this paper, all graphs considered are simple graphs. The graph Γ has vertex set V(Γ) and
edge set E(Γ). A symmetry or automorphism of a graph is a permutation of V(Γ) which
preserves E(Γ). The symmetries of Γ form a group, Aut(Γ), under composition. Each edge
{u, v} of Γ corresponds to two directed edges, also called darts or arcs; one is (u, v), the
other is (v, u).
E-mail address: stephen.wilson@nau.edu (Steve Wilson)
Copyright c© 2008 DMFA – založništvo
8 Ars Mathematica Contemporanea 1 (2008) 7–19
A mapM is an embedding of a graph Γ in a surface S so that the faces, i.e., the connected
components of the complement of the graph, are simply-connected. A symmetry or automor-
phism of a mapM is a homeomorphism of S onto itself which preservesM. Alternately, a
symmetry ofM is a symmetry of Γ which preserves the collection of cycles of edges which
surround faces ofM. The mapM is rotary provided that Aut(M) contains symmetries R
and S which act on some incident face-vertex pair (these are the central face and vertex) as
rotations one step about the face and the vertex, respectively. Then γ = RS−1 acts as a 180◦
flip about the center of an edge, and thus has order 2. A rotary mapM is reflexible provided
that Aut(M) also contains symmetries which act locally as reflections. A map which is rotary
but not reflexible is chiral. If M is rotary, its group of symmetries acts transitively on the
darts of Γ. In the literature, the word “regular” is also used, sometimes with the meaning of
“rotary”, sometimes with the meaning of “reflexible”.
In a rotary mapM, Aut(M) acts transitively on faces and on vertices. Thus, all faces are
p-cycles for some p, and all vertices are q-valent for some q. We then say the map is of type
{p, q}.
A Petrie path in a map is a cycle of edges in which each two consecutive belong to the
same face, but no three consecutive do. The map P(M) is formed from M by dissolving
every face, and then identifying each Petrie path with the boundary of a topological disk.
Clearly,M and P(M) have the same underlying graph. IfM is reflexible, so is P(M), while
ifM is chiral, P(M) is not rotary.
IfM is reflexible, all its Petrie paths have the same length r. We sayM is of type {p, q}r,
and then P(M) is of type {r, q}p.
See [5] for a more thorough description of these notions.
Definition 1. The Rose Window graph Rn(a, r) has 2n vertices: Ai, Bi for i ∈ Zn; all
arithmetic with r, a and vertex subscripts is assumed to be done in Zn. The graph has four
kinds of edges:
Rim: Ai −Ai+1
In-Spoke: Ai −Bi
Out-spoke: Bi −Ai+a
Hub: Bi −Bi+r
For example, Figure 1 shows R10(2, 3).
In this and other figures in this paper, vertices labeled 1 . . . n are verticesA1, A2, . . . , An,
while those labeled n+ 1, n+ 2, . . . , 2n are B1, B2, . . . , Bn.
Some facts about these graphs can be seen at once. First
Rn(a, r) ∼= Rn(−a, r). (1)
An isomorphism is given by Ai → A−i, Bi → B−i. Also,
Rn(a, r) = Rn(a,−r). (2)
Notice the equal sign; these graphs are identical, not just isomorphic. Also, if (n, r) = 1,
then
Rn(a, r) ∼= Rn(ar−1, r−1), (3)
the isomorphism being given by Ai → B−ir−1 , Bi → A−ir−1 .
S. Wilson: Rose Window Graphs 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Figure 1: R10(2, 3)
3 Symmetry
The group consisting of all symmetries of Rn(a, r) which preserve the cycle of rim edges
setwise is dihedral, in fact isomorphic to Dn. It is generated by the symmetries
ρ : Ai → Ai+1, Bi → Bi+1,
µ : Ai → A−i, Bi → B−a−i.
Notice that the symmetry ρ has two orbits of length n. This tells us that the graphs
Rn(a, r) are bicirculant. The classification of edge-transitive bicirculants is a topic of interest
to many authors, and classifying edge-transitive Rn’s is an important step in that project.
The action ofDn on the edges has three orbits: one is the set of rim edges, one is the set of
hub edges, and the third consists of all in-spokes and out-spokes. The symmetry µρ reverses
the edge {A0, A1}, and so if Rn(a, r) is edge-transitive, its group must act transitively on
darts.
It sometimes happens that there is a symmetry interchanging the rim and hub edges:
Lemma 2. There is a symmetry σ sending rim edges to hub edges and vice-versa if and only
if r2 = ±1 and ra = ±a.
Proof. If the two equations r2 = ±1 and ra = ±a hold, then by (2) above, we can assume
that ra = −a. Then the symmetry σ given by Ai → Bri, Bi → Ari accomplishes this
interchange.
On the other hand, suppose that σ is a symmetry which interchanges rim and hub edges.
Then the hub edges must form an n-cycle and so (r, n) must be 1. By first applying the
correct element of Dn, we can assume that A0σ = B0 and that B0σ = A0. By the correct
choice of r as in (2), we can assume that A1σ = Br. Then it must be that A2σ = B2r,
etc., and so in general, Aiσ = Bri. Now, B1σ is a rim vertex, say As. Then in general,
Biσ = Asi. Then σ2 sends A0 to itself and A1 to Ars. Thus rs = ±1. Now consider
the spoke edges joining Ai to Bi to Ai+a. Then σ sends these vertices to Bri, Asi, Bri+ra,
10 Ars Mathematica Contemporanea 1 (2008) 7–19
respectively, and so these must be joined by spoke edges. More precisely, one is an in-spoke,
the other, an out-spoke Thus, one of these two systems must hold for all i ∈ Zn:
(1) ri = si ri+ ra+ a = si
(2) ri+ ra = si ri+ a = si
Letting i = 1 in system (1) clearly yields ra = −a and r2 = ±1. In system (2), we
conclude the ra = a, and so a = (s− r)i for all i. Letting i = 0 shows that a = 0, which is
not allowed.
We are interested in answering three questions about rose window graphs:
(1) For which n, a, r is Rn(a, r) edge-transitive?
(2) When it is edge-transitive, what is the order of its symmetry group? This is equivalent
to asking for the size of H , the stabilizer of one dart.
(3) For which n, a, r is Rn(a, r) the underlying graph of a rotary map?
From our remarks above, we can see that the graph is edge-transitive exactly when it has
some symmetry sending a rim edge to some spoke.
In the next sections we will present four families of rose window graphs. For each one
we will prove that each member of the family is edge-transitive, we will discuss the order
and structure of its group, and consider which of its members occur in rotary maps. We will
use the word “occur” throughout this paper to mean “occur as the underlying graph of some
rotary map”.
At the end we will conjecture that every edge-transitive rose window graph belongs to
one of these families and that the maps described include all rotary maps on rose window
graphs.
4 Family (1)
The first family to consider is all graphs of the formRn(2, 1). These graphs are called wreath
graphs, W (n, 2), and may also be described as C2n(1, n+1). See [5] for definitions of these
graphs.
Figure 2 shows the case where n = 12.
In this family and others it is convenient to relabel the hub vertices: let Ci = Bi−1.
Then the vertices Ai and Ci have precisely the same neighbors. A graph which has two
such vertices is called unworthy and has a “local” symmetry which interchanges those two
vertices, leaving all others fixed. In our example, let σi be the symmetry which interchanges
vertices Ai and Ci while leaving all other vertices fixed. Such a symmetry sends a rim edge
to a spoke edge, and so Rn(2, 1) is edge-transitive.
The collection of pairs {Ai, Ci} forms a system of imprimitivity for the action of the
group on the vertices. The kernel of the action on the blocks isZ =< σ0, σ1, σ2, . . . , σn−1 >,
which is isomorphic to Zn2 . When n = 4, the graph is isomorphic to K4,4. In all other cases,
Aut(Rn(2, 1)) is generated byDn and σ0, and so is isomorphic to Zn2 oDn. As σ
ρi
0 = σi, the
symmetry group has order 2n(2n); thus a vertex-stabilizer has order 2n and a dart-stabilizer
has order 2n−2.
A cycle in a graph Γ is consistent provided there is a symmetry of Γ which moves vertices
in the cycle one step along it. Such a symmetry is called a shunt for the cycle. The remarkable
theorem of Conway and Biggs [1] shows that a dart-transitive action on a graph of degree d
has exactly d − 1 orbits of consistent (directed) cycles. In the graph Rn(2, 1), these are the
S. Wilson: Rose Window Graphs 11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1 2
3
4
5
6
7
8
9
10
11
121314
15
16
17
18
19
20
21
22
23
24
Figure 2: R12(2, 1) = C24(1, 13)
4-cycles, such as [A0, A1, C0, C1], the n-cycles (the rim cycle is one), and the 2n-cycles such
as [A0, A1, A2, . . . , An−1, C0, C1, C2, . . . , Cn−1].
If Rn(2, 1) underlies a rotary map M, its faces must be consistent cycles. Since each
edge meets only one of the consistent 4-cycles, the faces must be n-cycles or 2n-cycles.
Then in each face, indices of vertices must occur in the circular order 1, 2, 3, . . . . Without
loss of generality, we can assume that the central face is f = [A0, A1, A2, . . . , An−1] and
that ρ is the face-rotation R, or that f ′ = [A0, A1, A2, . . . , An−1, C0, C1, . . . , Cn−1] is the
central face and the shunt ρ′ = ρσ0 is R. Notice that (ρ′)n is equal to the product of all σ′is.
We first consider reflexible maps. Then there must be a symmetry β which fixes A0 and
A1, while sending the central face to an adjacent face. IfM is the map and G = Aut(M)
is its symmetry group, then β must be in H = G ∩ Z, and in fact it must be the unique non-
identity element of H fixing A0 and A1. H must be generated by β and all of its conjugates
under Dn.
The group H and the element β must satisfy these conditions:
(1) H is invariant under conjugation by Dn
(2) the orbit of f (resp. f ′) under H must be the set of all faces.
(3) H is generated by β and its conjugates under ρ and µ.
(4) if R = ρ, the number of faces is 8 and so |H| = 8.
(5) if R = ρ′, the number of faces is 4. Then either |H| = 4 and (ρ′)n /∈ H or |H| = 8
and (ρ′)n ∈ H
(6) no two distinct elements of H agree on any three consecutive indices.
The possibilities for β and H satisfying these requirement are limited. To describe them,
we introduce this notation: for any divisor d of n, and and subset S of Zd, let σd,S be the
product of all σi’s such that i is equivalent mod d to some number in S. For example, σ3,{2} =
σ2σ5σ8 . . . σn−1. Then σd,Sσd,T = σd,S∆T , where S∆T is the symmetric difference of the
sets S and T . Also (ρ′)n = σd,Zd for any divisor d of n.
12 Ars Mathematica Contemporanea 1 (2008) 7–19
It will also simplify our considerations if we regard elements of H as being in Zn2 ;
abbreviate σa00 σ
a1
1 σ
a2
2 . . . , σ
an−1
n−1 by the n-tuple (a0, a1, a2, . . . , an−1). Then the require-
ment that β fixes A0 and A1, while sending the central face to an adjacent face says that
β = (0, 0, 1, x, . . . , z, y, 1) for some x, y, z ∈ Z2. The conjugate of β by ρµ is then
(0, 0, 1, y, z . . . , x, 1); as this agrees with β in four consecutive places, it must be equal to
β, and so x = y.
If x = y = 0, then β = (0, 0, 1, 0, . . . , z, 0, 1), and the conjugate of β by ρ3 is
(z, 0, 1, 0, 0, 1, 0, . . . ), which again must be equal to β. Thus, the entries must repeat ev-
ery 3 places, and so β = σ3,{2}. The resulting H is the set of all σ3,S , and so (ρ′)n is
included. Thus, if n is divisible by 3, we get two reflexible maps from H , one with faces of
size n, one with faces of size 2n.
On the other hand, if x = y = 1, then β = (0, 0, 1, 1, w, . . . , a, z, 1, 1), for some w, a ∈
Z2. Again z = w. There are two subcases:
(i) if z = w = 0, then the conjugate of β by ρ4 is (a, 0, 1, 1, 0, 0, 1, 1, 0, . . . ), which again
must be equal to β. Thus β repeats every 4 entries, and so β = σ4,{2,3}; here, H is the set of
all σ4,S such that |S| is even. Again, this group has size 8 and contains (ρ′)n, so it works for
both sizes of face.
(ii) if z = w = 1, then β = (0, 0, 1, 1, 1, . . . , a, 1, 1, 1), and its conjugates under <
ρ > include (1, 0, 0, 1, 1, 1, . . . , a, 1, 1), (1, 1, 0, 0, 1, 1, 1, . . . , a, 1), and , (1, 1, 1, 0, 0, 1, 1,
1, . . . , a). The group generated by these four alone has size 16, and so is eliminated.
This shows that σ3,{2} and σ4,{2,3} are the only possibilities for β that satisfy the require-
ments, and so we have found all reflexible maps on graphs in family (1).
We summarize these maps and their properties:
Case I: n is divisible by 3. Let n = 3k, letM1 be the map using R = ρ andM2 be the
map using R = ρ′.
If k is odd, then M1 = P (M2), M1 is of type {3k, 4}6k and is a k-fold covering of
the octahedron with k-fold branching points at the face-centers. It follows thatM2 is of type
{6k, 4}3k and is a similar k-fold covering of the torus map {6, 3}2,0
If k is even then both maps are self-Petrie. M1 is of type {3k, 4}3k and is a k-fold
covering of a certain map of type {6, 4}6 on the orientable surface of genus 3.M2 is of type
{6k, 4}6k and is a k2 -fold covering of the hemi-octahedron, and hence is non-orientable.
Case II: n is divisible by 4. Let n = 4k, letM3 be the map using R = ρ andM4 be the
map using R = ρ′.
ThenM3 is self-Petrie of type {4k, 4}4k. It is a k-fold cover of the torus map {4, 4}2,2
(see [2]).
Map M4 is the map B(4, 8k, 2k − 1, 0) described in [4]. It is then a k-fold cover of
B(4, 8, 3, 0), and so is orientable.
Thus we have found all reflexible maps on family (1) rose window graphs. No chiral
maps on these graphs are known to exist and we conjecture that there are none.
5 Family (2)
We now consider graphs of the form Γ = R2m(m+ 2,m+ 1). For example, Figure 3 shows
R12(8, 7).
Again, it is convenient to re-label the hub vertices: let Ci = Bi−1, so that the edges are:
S. Wilson: Rose Window Graphs 13
1
2
3
4
5
67
8
9
10
11
12
13
14 15
16
17
18
19
2021
22
23
24
Figure 3: R12(8, 7)
Rim: Ai −Ai+1
In-Spoke: Ai − Ci+1
Out-spoke: Ci −Ai+m+1
Hub: Ci − Ci+m+1
and then the symmetries ρ and µ are:
ρ : Ai → Ai+1, Ci → Ci+1,
µ : Ai → A−i, Ci → Cm−i.
Then we can arrange part of the graph to look like Figure 4:
C
m-1
C
0
C
m+1
A
m-1
A
m
A
m+1
A
m+2
C
2
A
-1
A
0
A
1
A
2
C
-1
C
m C 1 C m+2
Figure 4: Part of R2m(m+ 2,m+ 1)
It is clear that the permutation (A0, C0)(Am, Cm)(A1, Cm+1)(Am+1, C1) is a symmetry
14 Ars Mathematica Contemporanea 1 (2008) 7–19
of the graph, and as it sends rim edges to spokes and hubs, the graph must be edge-transitive.
We gather the following from Figure 4: First, if m > 3, then the graph has girth 4, and
if m > 4, then the only 4-cycles are those of the form [Ai, Ai+1, Ci+m, Ci+1]. If m > 4,
then every edge belongs to exactly one of these cycles. It follows that for m > 4, the
equivalence relation generated by being opposite in a 4-cycle has as its equivalence classes
the sets Li = {Ai, Ai+m, Ci, Ci+m}. Then the collection of all Li is a block system for the
action of the symmetry group on the vertices. This last is also true whenm = 3, but not when
m = 4.
For the rest of this general discussion, we will assume that m > 4; the exceptional cases
m = 3, 4 we will discuss at the end.
Let σi = (AiCi)(Ai+m, Ci+m)(Ai+1Ci+m+1)(Ai+m+1Ci+1); with all other vertices
fixed. Then σm+i = σi and any σi, σj commute, and so Z =< σ0, σ1, σ2, . . . , σm−1 > is an
elementary abelian 2-group of order 2m. Clearly, Z is the kernel of the action of Aut(Γ) on
the block system {Li}. That action is dihedral, isomorphic toDm. In fact, if we let ρ′ = ρσ0,
then ρ′ has order m and sends Li to Li+1. Moreover µ′ = µρm conjugates ρ′ to its inverse.
Thus < µ′, ρ′ > is isomorphic to Dm, and so Aut(Γ) ∼= Zm2 oDm.
Now we wish to determine rotary maps on these graphs. The first step is to determine the
consistent cycles. As ρµσ0 is a shunt for [A0, A−1, C0, Cm−1], the 4-cycles are consistent.
Clearly ρ is a shunt for the rim cycle f = [A0, A1, A2, . . . , A2m−1], and it is not hard to
see that ρ′ is a shunt for the m-cycle f ′ = [A1, A2, . . . , Am−1, Cm]. Thus the lengths of
consistent cycles in this graph are 4,m, n. As in family (1), each edge belongs to only one
4-cycle, and so any rotary map on this graph must have faces of size m or n. No chiral maps
are known on these graphs, and we conjecture that none exist.
We proceed to construct several families of reflexible maps. IfM is a reflexible map on
Γ = R2m(m+ 2,m+ 1), let G = Aut(M). With no loss of generality, we can assume that
one face of such a map is f or f ′. The symmetry µ reverses f , leaving A0 fixed, while µ′
reverses f ′, leaving Cm fixed. As the point stabilizers of each of these cycles is trivial, µ and
µ′ are the only symmetries reversing those cycles and leaving those vertices fixed. Thus G
must contain ρ and µ as generators of the stabilizer of face f or ρ′ and µ′ as generators of the
stabilizer of face f ′.
Any symmetry β which acts as a reflection interchanging the two faces on either side of
a given edge must be in the kernel of the action of G on the block system {Li}, i.e., in the
subgroup H = G ∩ Z, and thus must be a product of σi’s. Such a reflection at the edge
{A0, A1}, for instance, must fix those two vertices, but move A2 and A2m−1 (in f ) or Cm−1
(in f ′). Thus the product must include σ−2 and σ2, but neither σ−1, σ0 nor σ1.
That reflection β, followed by the face-rotation ρ or ρ′, is movement one step along a
Petrie path, and so the order of βρ or βρ′ is the length of a Petrie path. As Petrie paths are
consistent cycles in a reflexible map, these must also have length m or n.
We find it clearest to describe the map by describing the group H; the set F of faces of
the map, is simply the orbit of f or f ′ under H . What are the properties that H must have?
The group H and the element β must satisfy these conditions:
(1) H is invariant under conjugation by Dm
(2) the orbit of f (resp. f ′) under H must be the set of all faces.
(3) H is generated by β and its conjugates under ρ and µ.
(4) if R = ρ′, the number of faces is 16 and so |H| = 16.
S. Wilson: Rose Window Graphs 15
(5) if R = ρ, the number of faces is 8. Then either |H| = 8 and ρn /∈ H or |H| = 16 and
ρn ∈ H
(6) no two distinct elements of H agree on any four consecutive indices.
As before, we let σd,S , where d is a divisor of m and S is a subset of Zd, be the product
of all σi such that i is equivalent mod d to some number in S.
We consider four groups and the resulting maps:
(1) If m is divisible by 4, say m = 4k, the group of all σ4,S certainly has order 16,
contains β = σ4,{2} and ρm = σ4,Z4 . Thus it allows maps of face size m and n. By using
the relation σiρ = ρσi+1, it is not hard to see that if k is odd , the maps are of types {n, 4}m
and {m, 4}n and are Petrie to each other, while if k is even, they are of types {n, 4}n and
{m, 4}m and are self-Petrie. The maps of types {m, 4}n and {m, 4}m are k-fold covers of
the torus map {4, 4}2,2, with k-fold branching at the face-centers. Those of type {n, 4}n are
2k-fold covers of the torus map {4, 4}4,0, with similar branching.
(2) If m is divisible by 5, say m = 5k, let H be the group of all σ5,S for sets S of even
size. Then H has 16 elements, but does not contain ρm = σ5,Z5 . Thus it allows only maps
of face size m. H contains β = σ5,{2,3}, and the order of βρ′ is m, and so this construction
gives maps of type {5k, 4}5k for all k. These maps are k-fold branched coverings of the map
{5, 4}5 having 40 edges. The maps are all non-orientable and self-Petrie.
(3) If m is divisible by 6, say m = 6k, one group that satisfies the requirements is
generated by β = σ6,{2,3,4} and all of its conjugates under ρ. The sets S for elements in the
group are: 012, 123, 234, 345, 045, 015, 03, 14, 25, 0134, 0235, 1245, 024, 135, 012345 as
well as the null set, 16 in all. Since Z6 is in this list, both n- and m-cycles are allowed.
As in construction (1), odd values for k give a Petrie pair of maps of types {n, 4}m and
{m, 4}n, while even values of k give two self-Petrie maps of types {n, 4}n and {m, 4}n.
(4) Another group that satisfies (1)-(6) in the case m = 6k is the set of all σ6,S such that
S contains an even number of odd numbers and an even number of even numbers. This is the
group H generated by β = σ6,{2,4} and its conjugates under ρ. H is of order 16 but does not
contain ρm, and so will construct maps of types {6k, 4}6k for all k.
It should be noted that different constructions yield nonisomorphic maps. For instance, at
m = 24, the graph Γ = R48(26, 25) allows three reflexible maps of type {24, 4}24, one each
from constructions (1), (3) and (4). These are three distinct, nonisomorphic maps.
We have shown then, that ifm is divisible by 4, 5, or 6, then the graphR2m(m+2,m+1)
has a reflexible embedding in some surface. An argument similar to the one for Family (1)
shows that the four groups presented are the only ones satisfying conditions [1], [2], [3] and
so, that we have described all rotary maps on Family (2) graphs in the general case.
To handle the exceptional cases, first consider m = 3. The resulting graph R6(5, 4)
is isomorphic to the skeleton of the cuboctahedron, i.e., to the medial graph of the cube.
Its group is the group of either polyhedron, and so is isomorphic to Z32 o D3. Then the
stabilizer of a vertex in R6(5, 4) is the same as the stabilizer of an edge in the cube, and that
is isomorphic to Z22. Thus no rotary map exists on this graph.
Second, we consider m = 4, the graph R8(6, 5). This graph is isomorphic to Q4, the
skeleton of the 4-dimensional cube. Thus its group is Z42 o S4, of order 16 · 24 = 384. This
graph is well-known and occurs in two rotary maps. One isM = {4, 4}4,0, a reflexible map
of type {4, 4}8; the other is its Petrie, of type {8, 4}4.
The paper [3] introduces a family C(p, r, s) of edge-transitive graphs. Family (2) of rose
window graphs arise as a special case: R2m(m+ 2,m+ 1) ∼= C(2,m, 2).
16 Ars Mathematica Contemporanea 1 (2008) 7–19
6 Family (3)
The third family of edge-transitive rose window graphs are those Rn(a, r) for which
(1) n is even, so n = 2m for some m
(2) a is even, a = 2b, such that b2 ≡ ±1 (mod m)
(3) r is odd and r ≡ 1 (mod m).
(4) Rn(a, r) is in neither family (1) nor family (2).
We separate Family (3) into (3a) in which b2 ≡ 1 (mod m) and (3b) in which b2 ≡ −1
(mod m).
Define a permutation σ of the vertices as follows:
In family (3a):
Aiσ =
{
Abi if i is even
Bbi−b if i is odd
, Biσ =
{
A1+bi if i is even
Bbi−b+r if i is odd
In family (3b):
Aiσ =
{
Abi if i is even
Bbi−b if i is odd
, Biσ =
{
A−1+bi if i is even
Bbi−b−r if i is odd
It is easy to check that in each case, this σ is a symmetry of the graph. As it sends the rim
edge {A0, A1} to the in-spoke {A0, B0}, the graph must be edge-transitive.
Moreover, notice that in (3a), it happens that σ, as well as µ and µσ, interchange the
neighbors of A0 in pairs, while in (3b), σ permutes them in a cycle of length 4. It is
easy to compute that in (3b), the symmetry ρ′ = µρσ acts as a shunt for the cycle α =
[A0, B0, B2−r, Ar, A1−r, Br−1, B1, A1]; if r = 1, this cycle has length 4, while if r = m+1,
it has length 8.
In order to make definitive statements about maps on graphs in this family, we need
information on the size of H , the stabilizer of a dart. Computer work suggests the following
Conjecture 3. If Γ is Rn(a, r) in family (3), then the stabilizer of a dart in Aut(Γ) is trivial.
Suppose for a moment that this conjecture holds. From this, we conclude that:
(1) In family (3a), the stabilizer of vertex A0 consists of exactly four elements. These must
be the identity, σ, µ and µσ, all of order 2. Thus, no graph in family (3a) occurs.
(2) Every graph in family (3b) occurs as the underlying graph of a chiral map. Its faces are
the cycles in the orbit of the cycle α shown above. If r = 1, this map is of type {4, 4} on the
torus. If r = m+ 1, then the map is of type {8, 4}.
To describe those maps a little more precisely, suppose B and C are natural numbers
whose greatest common divisor is 2. Let n = B
2+C2
2 , let m = n/2, and let x and y be the
least Bezout multipliers such that Bx + Cy = 2. Let a = |Cx − By|. Then the underlying
graph of the map{4, 4}B,C is Rn(a, 1) of family (3); every graph in family (3) having r = 1
arises in this way.
Each map of type {8, 4} on Γ in family (3b) is a twofold cover of one of the torus maps
(though not every torus map yields such a cover). The covering is branched at face-centers
only.
S. Wilson: Rose Window Graphs 17
7 Family (4)
The fourth and last family of edge-transitive rose window graphs are those of the form
R12m(9m+ 2, 3m+ 1) or R12m(3m+ 2, 9m+ 1). It will be convenient to think of these as
Γ = R12m(3d+ 2, 9d+ 1) where d can be m or −m mod n = 12m.
First consider the permutation σ of the vertices defined by:
Aiσ =

Ai if i ≡ 0 (mod 3)
Bi−1 if i ≡ 1 (mod 3)
Bi−a+1 if i ≡ 2 (mod 3)
, Biσ =

A1+i if i ≡ 0 (mod 3)
Ai+a−1 if i ≡ 1 (mod 3)
Bi+6d if i ≡ 2 (mod 3)
.
It is easy to check that σ is an involutary symmetry of Γ, and as it sends the rim edge
{A0, A1} to the in-spoke {A0, B0}, we see that all such graphs are edge-transitive.
We consider a special case in which Γ has another symmetry. Suppose that m is twice an
odd number, and let b = d+ 1. Then a = 3b− 1, r = 4− 3b, and it follows that 3b2 ≡ 3 and
12b ≡ 12 (mod 12m). Using that fact it is possible to show that τ defined by:
Aiτ =

Abi if i ≡ 0 (mod 3)
Bbi−b if i ≡ 1 (mod 3)
Ab+bi−1 if i ≡ 2 (mod 3)
, Biτ =

A1+bi if i ≡ 0 (mod 3)
B4+bi−4b if i ≡ 1 (mod 3)
Bb+bi−1 if i ≡ 2 (mod 3)
is a symmetry of Γ. Notice that τ fixes bothA0 andA−1 while moving bothA−2 andA1.
We then divide family (4) into (4a), in which n is an odd multiple of 12, family (4b), in
which n is an odd multiple of 24, and (4c) in which n is an even multiple of 24. Thus τ exists
only for graphs in family (4b).
Theorem 4. Every graph in family (4b) is the underlying graph of a reflexible map.
Proof. First consider the symmetries τ and µ. Each is an involution within the stabilizer of
vertex A0, and the product S = τµ has order 4. Thus, the group they generate must be of
order 8, isomorphic to D4. There are two reflexible maps having this group as the vertex-
stabilizer. One has R = ρ as its face-rotation. It is not difficult to verify that RS−1 has order
2. The other map is the Petrie of this one. Its face rotation is τρ, and its face-length is 6g
where g is the additive order of 3b− 9 mod n.
Computer work suggests the following:
Conjecture 5. The stabilizer of a dart has order 1 in family (4a), 2 in (4b), 1 in (4c).
If the conjecture is true, then no graph in (4a) or (4c) can underlie a rotary map, because
the entire stabilizer of A0 consists of the identity, µ, σ, and µσ, all of order 2.
Somewhat scantier evidence suggests:
Conjecture 6. If n is a multiple of 48, then the two graphs in family (4) are isomorphic.
18 Ars Mathematica Contemporanea 1 (2008) 7–19
8 The “if-cycle” theorems
We present four theorems, each of which says that if a cycle of a certain kind is in the orbit
of the rim cycle, then the graph must fall into a corresponding set of families. In the descrip-
tions, we use the phrase “repeating pattern”; for instance “the cycle has repeating pattern [rim,
in-spoke, hub, out-spoke]” means that the cycle is made of some k repetitions of this pat-
tern, thusly: [A0, A1, B1, Br+1, Ar+a+1, Ar+a+2, Br+a+2, B2r+a+2, A2r+2a+2, A2r+2a+3,
B...].
Theorem 7. If the graph Γ = Rn(a, r) admits a symmetry σ under which the image of the
rim cycle [A0, A1, A2, . . . , An−1] has repeating pattern [rim, in-spoke, hub, out-spoke], then
Γ is in family (1) or n is divisible by 8 and Γ is in family (2).
Theorem 8. If the graph Γ = Rn(a, r) admits a symmetry σ under which the image of the
rim cycle [A0, A1, A2, . . . , An−1] has repeating pattern [in-spoke, out-spoke], then n is even,
and Γ is in family (1) or Γ is in family (3).
Theorem 9. If the graph Γ = Rn(a, r) admits a symmetry σ under which the image of the
rim cycle [A0, A1, A2, . . . , An−1] has repeating pattern [in-spoke, hub, out-spoke], then n is
divisible by 3 and Γ is in family (1) or family (3) or family (4).
Theorem 10. If the graph Γ = Rn(a, r) admits a symmetry σ under which the image of the
rim cycle [A0, A1, A2, . . . , An−1] has repeating pattern [out-spoke,rim, in-spoke], then n is
divisible by 3 and Γ is in family (1) or n is divisible by 12 and Γ is in family (2) or n is an
odd multiple of 24 and Γ is in family (4).
We will prove one of these, Theorem 8. The other theorems are proved with similar
methods.
Proof of Theorem 8. We can without any loss of generality assume that there is a symmetry
σ such that [A0, A1, A2, . . . , An−1]σ = [A0, B0, Aa, Ba, A2a, B2a, . . . ]. The length of this
second cycle is twice the additive order of amod n, and if this length is to be n, we must have
(a, n) = 2. Let a = 2b, n = 2m, so that (b,m) = 1. Then, letting Ci = Aiσ and Di = Biσ,
we have that
C2i = Aai and C2i+1 = Bai.
It is perhaps simpler to write:
Cj =
{
Abj if j is even
Bbj−b if j is odd
.
Now, of the four neighbors of A0 = C0, we know that B0 = C1, while B−a = C−1; D0,
which also must be a neighbor of A0 = C0, must then be A1 or A−1.
Case 1: D0 = A1. Then A2 must be Ca, which we know is Aba. Thus ba ≡ 2 (mod n),
and so b2 ≡ 1 mod m. Then Ca+1 = B2. The common neighbor of C1 and Ca+1 must be
D1 and it must be a B vertex, and a neighbor of B0. By a correct choice for r, we can insist
that D1 = Br. Then r is odd and B2 = B2r, so 2r = 2. Thus either r is 1 or m is even and
r = m+ 1.
S. Wilson: Rose Window Graphs 19
Case 2: D0 = A−1. Then A−2 must be Ca, which we know is Aba. Thus ba ≡ −2 (mod
n), and so b2 ≡ −1 mod m. In a similar fashion, we can choose r so that 2r = 2, and so
r = 1 or m+ 1.
Thus, in either case, Γ is in family (1) or (3).
9 The Big Conjecture
Conjecture 11. Every edge-transitive Rose Window graph belongs to one of the four families
of graphs introduced in this paper.
This conjecture has been verified for all n ≤ 100.
References
[1] N. Biggs, Aspects of symmetry in graphs, Algebraic methods in graph theory, Vol. I, II (Szeged,
1978), pp. 27–35, Colloq. Math. Soc. János Bolyai, 25, North-Holland, Amsterdam-New York,
1981.
[2] H. S. M. Coxeter, W. O. J. Moser, Generators and relations for discrete groups, Fourth edition,
Ergebnisse der Mathematik und ihrer Grenzgebiete 14., Springer-Verlag, Berlin-New York, 1980.
[3] C. E. Praeger, M. Y. Xu, A characterization of a class of symmetric graphs of twice prime valency,
European J. Combin. 10 (1989), no. 1, 91–102.
[4] S. Wilson, Bicontactual regular maps, Pacific J. Math. 120 (1985), no. 2, 437–451.
[5] S. Wilson, Families of Regular Graphs in Regular Maps, J. Comb. Theory, Ser. B 85 (2002), no.
2, 269–289.