Accepted manuscript
ISSN 2590-9770
The Art of Discrete and Applied Mathematics
https://doi.org/10.26493/2590-9770.1617.83c
(Also available at http://adam-journal.eu)
SymmetriesoftheWoollyHatgraphs
*
Leah Wrenn Berman
University of Alaska Fairbanks, Department of Mathematics and Statistics,
Fairbanks, AK, USA
Hiroki Koike
National Autonomous University of Mexico, Institute of Mathematics, Mexico City, Mexico
Elías Mochán
Northeastern University, Department of Mathematics, Boston, MA, USA
Alejandra Ramos-Rivera
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Primož Šparl
†
University of Ljubljana, Faculty of Education, Ljubljana, Slovenia and
University of Primorska, Institute Andrej Marušiˇ c, Koper, Slovenia and
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Stephen E. Wilson
Northern Arizona University, Department of Mathematics and Statistics,
Flagstaff, AZ, USA
Received 2 February 2023, accepted 7 September 2023
Abstract
A graph is edge-transitive if the natural action of its automorphism group on its edge set
is transitive. An automorphism of a graph is semiregular if all of the orbits of the subgroup
generated by this automorphism have the same length. While the tetravalent edge-transitive
graphs admitting a semiregular automorphism with only one orbit are easy to determine,
those that admit a semiregular automorphism with two orbits took a considerable effort
*
The authors are grateful to Primož Potoˇ cnik for fruitful conversations on the topic. They would also like to
thank the organizers of the 2017 CMO workshop Symmetries of Discrete Structures in Geometry held in Oaxaca,
Mexico, the 2018 and 2022 SIGMAP conferences held in Morelia, Mexico, and Fairbanks, USA, respectively, and
the 2022 Workshop on Symmetries of Graphs, held in Kranjska Gora, Slovenia, during which a considerable part
of the research that lead to the results of this paper was performed.
†
Corresponding author. The author acknowledges financial support by the Slovenian Research Agency (re-
search program P1-0285 and research projects J1-2451 and J1-3001).
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/

Accepted manuscript
2 Art Discrete Appl. Math.
and were finally classified in 2012. Of the several possible different “types” of potential
tetravalent edge-transitive graphs admitting a semiregular automorphism with three orbits,
only one “type” has thus far received no attention. In this paper we focus on this class of
graphs, which we call the Woolly Hat graphs. We prove that there are in fact no edge-
transitive Woolly Hat graphs and classify the vertex-transitive ones.
Keywords: Edge-transitive, vertex-transitive, tricirculant, Woolly Hat graph.
Math. Subj. Class.: 05C25, 20B25
1 Introduction
Investigation of tetravalent graphs admitting a large degree of symmetry has been an active
topic of research attracting many researchers as is witnessed by numerous publications on
the subject. Among such graphs, the edge-transitive ones (for which the automorphism
group acts transitively on the edge set of the graph) have received by far the most atten-
tion. An edge-transitive tetravalent graph Γ can be arc-transitive (the automorphism group
Aut(Γ) acts transitively on the set of all arcs, that is ordered pairs of adjacent vertices).
If, however, Γ is not arc-transitive (but still is edge-transitive), then it is either half-arc-
transitive or semisymmetric, depending on whether Aut(Γ) acts transitively on the vertex
setV (Γ) of Γ or not, respectively (see for instance [21, 26]).
The tetravalent edge-transitive graphs of each of these three “types” have been thor-
oughly investigated, but these families of graphs are simply far too rich and diverse to
admit a complete classification. There is thus still an abundance of questions to be an-
swered and problems to be solved. In attacking such a wide-ranging topic, it makes sense
to investigate and possibly classify certain subfamilies of these graphs. When attempting
to solve any such problem or decide what kind of subfamilies to study, it is beneficial to
have a large database of tetravalent edge-transitive graphs. With this aim in mind, Potoˇ cnik
and Wilson constructed a Census [24] of all known tetravalent edge-transitive graphs up
to order 512 (known to be complete for the arc-transitive and half-arc-transitive graphs but
possibly incomplete for the semisymmetric ones) where for each graph in the Census, vari-
ous properties of the graph are given, together with several known ways on how to construct
it.
To be able to describe the graphs from the Census and more generally within the whole
family of tetravalent edge-transitive graphs it is desirable to have a large list of known infi-
nite families of such graphs. One very natural way of obtaining such families is to analyze
and possibly classify the examples admitting a semiregular automorphism (an automor-
phism having all orbits of equal length) with few orbits. It is an easy exercise to classify
all tetravalent edge-transitive graphs admitting an automorphism with just one orbit (such
graphs are known as circulants). The situation becomes much more interesting for graphs
admitting a semiregular automorphism with two orbits (these are called bicirculants). It
has taken a considerable effort of several researchers in a handful of papers before the last
step of the classification was obtained in [13]. For instance, one of the major steps was
the classification of edge-transitive Rose window graphs [11], a family of graphs intro-
E-mail addresses: lwberman@alaska.edu (Leah Wrenn Berman), hiroki.koike@im.unam.mx (Hiroki
Koike), j.mochanquesnel@northeastern.edu (Elías Mochán), alejandra.ramosrivera@fmf.uni-lj.si (Alejandra
Ramos-Rivera), primoz.sparl@pef.uni-lj.si (Primož Šparl), stephen.wilson@nau.edu (Stephen E. Wilson)

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 3
duced in [27] that have since been the object of investigation in various contexts (see for
instance [9]).
While all of the examples in the case of circulants and bicirculants turn out to be arc-
transitive, the situation gets even more interesting when one considers the tetravalent edge-
transitive tricirculants, that is, graphs admitting a semiregular automorphism with three
orbits. Here, for the first time, half-arc-transitive examples start to appear. In fact, the
smallest half-arc-transitive graph, the Doyle-Holt graph (see [1, 4, 8]) turns out to be a
tricirculant. Moreover, infinite families of tetravalent half-arc-transitive tricirculants have
been constructed (see for instance [1]).
To be able to explain why we focus on a particular family of tetravalent tricirculants
in this paper we introduce a notion of a diagram and its simplifed version. We point out
that our diagrams are essentially what are known as voltage graphs and the corresponding
graphs are what are known as cyclic covers of the corresponding simplified diagrams (see
for instance [6, 15]).
A tetravalent tricirculant can succinctly be represented by a diagram in the following
way. Letρ be a corresponding semiregular automorphism, letn be its order, letu,v and
w be representatives of the three orbits of⟨ ρ ⟩ and let us denote these orbits byU,V and
W, respectively. We represent each of these three orbits by a circle, and then for each pair
of distinctx,y∈{ u,v,w} we join the circle representing the orbitX of x to the circle
representing the orbitY ofy byk edges, wherek is the number of neighbors ofx within
Y. We orient all of these edges in one of the two possible ways, say fromX toY, and for
eacha, 0≤ a<n, such thatx is adjacent toyρ a
, we put the labela onto this set of edges
(where we usually omit the label 0). For eachx∈{ u,v,w} we also put a semiedge, a loop,
or a semiedge and a loop atX , wheneverx has 1, 2 or 3 neighbors withinX , respectively.
Note that a semiedge will be present at the circle representingX if and only ifn is even
andx is adjacent toxρ
n/ 2
. On a loop we put the labela, where 0≤ a<n/2 is such that
x is adjacent toxρ
a
(andxρ
− a
). To indicate thatρ is of ordern we also put ann in the
middle of the diagram. An example of a diagram is given in the left part of Figure 2 (where
we in addition indicate the names of the vertices from each of the three orbits as chosen in
Construction 2.1). The simplified diagram is obtained from the diagram by omittingn and
the labels and arrows on the edges.
Distinguishing cases depending on the maximal indegree of the three orbits of⟨ ρ ⟩ (the
valency of the subgraph induced on that orbit), it is easy to see that there are 9 possible
simplified diagrams for tetravalent tricirculants (depicted in Figure 1). Considering the
number of 4-cycles through each edge, it is not difficult to show that none of the diagrams
with an orbit of indegree 3 (the first three) can give rise to edge-transitive graphs. Similar
considerations reveal that the simplified diagram IV gives rise to a unique edge-transitive
example (it is the graph of order 18, named C4[18,2] in [24], which in fact also corresponds
to the simplified diagram IX, of course for a different semiregular automorphism of order
6). The simplified diagram VIII takes a bit more work, but using the results of [20] one can
show that this diagram also gives rise to a unique edge-transitive example, namely the so
called wreath graph of order 6 (or equivalently the complement of the complete multipartite
graphK
2, 2, 2
).
The results of [25] show that there are infinitely many edge-transitive examples for the
simplified diagram V , while those of [16, 17, 26] show that there are infinitely many edge-
transitive (in fact, infinitely many half-arc-transitive and also infinitely many arc-transitive)
examples for each of the simplified diagrams VI and IX.

Accepted manuscript
4 Art Discrete Appl. Math.
I II
III
IV V
VI
VII
VIII
IX
Figure 1: The nine simplified diagrams for tetravalent tricirculants.
This leaves us with the simplified diagram VII. We call the corresponding diagram the
Woolly Hat diagram. The corresponding graphs (see Section 2) have thus far not been
investigated. It is the aim of this paper to investigate their symmetries. One of the main
results of this paper (see Theorem 3.7) is that the Woolly Hat diagram yields no edge-
transitive examples.
When constructing semisymmetric tetravalent graphs, certain structures, called LR-
structures (see [21, 22, 23]), can be very useful. The underlying graphs of these struc-
tures are tetravalent vertex-transitive graphs, which are not arc-transitive, but have some
additional properties regarding their symmetries (see [21] for a definition). Inspecting the
above mentioned Census [24], we find out that some semisymmetric graphs from the Cen-
sus arise via LR-structures corresponding to the Woolly Hat diagram. This motivates the
second part of this paper, in which we give a complete classification of the vertex-transitive
graphs corresponding to the Woolly Hat diagram (see Theorem 4.11).
2 Thefamilyandbasicproperties
In this section we introduce the family of graphs corresponding to the Woolly Hat diagram
and state some of their basic properties (but see also [24] where the graphs were first de-
fined). Before doing this we would like to point out that throughout the paperZ
n
will
always denote the residue class ring modulon, wheren is a positive integer.
Construction 2.1. For each integern≥ 3, for eacha,b,c,d∈ Z
n
, where 2a̸= 0,b,c,d
are pairwise distinct andn,a,b,c andd have no common prime divisor, the Woolly Hat
graph WH
n
(a,b,c,d) is the graph of order 3n with vertex set
{ A
i
: i∈ Z
n
}∪{ B
i
: i∈ Z
n
}∪{ C
i
: i∈ Z
n
}

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 5
and in which for eachi∈ Z
n
we have the following adjacencies
A
i
∼ A
i− a
,A
i+a
,B
i
,C
i
B
i
∼ A
i
,C
i+b
,C
i+c
,C
i+d
C
i
∼ A
i
,B
i− b
,B
i− c
,B
i− d
,
where all of the subscripts are computed modulon. The Wooly Hat diagram and a corre-
sponding drawing of the graph WH
4
(1, 0, 1, 3) are given in Figure 2.
A
B C
a
b
c
d
n
A0
B0 C0
A1
B1 C1
A2
B2 C2
A3
B3 C3
Figure 2: The Wooly Hat diagram and the graph WH
4
(1, 0, 1, 3).
Note that, by definition, the subscripts of the vertices of WH
n
(a,b,c,d) are always
computed modulon. Note also that the assumptions that 2a̸= 0 inZ
n
and thatb,c and
d are pairwise distinct ensure that the graph is regular of valency 4, while the assumption
thatn,a,b,c andd have no common prime divisor ensures that the graph is connected.
Throughout the paper we abbreviate the term “a Woolly Hat graph” to a WH-graph.
We also make an agreement that the vertices of a WH-graph of the formA
i
,B
i
andC
i
are
called theA-vertices, theB-vertices and theC-vertices, respectively.
We first record some fairly obvious symmetries of the WH-graphs. The proof is straight-
forward and is left to the reader.
Lemma 2.2. Let Γ = WH
n
(a,b,c,d) be a WH-graph. Then Γ admits the semiregular
automorphismρ , mapping according to the rule
A
i
ρ =A
i+1
, B
i
ρ =B
i+1
, C
i
ρ =C
i+1
, i∈ Z
n
, (2.1)
and the automorphismτ , mapping according to the rule
A
i
τ =A
− i
, B
i
τ =C
− i
, C
i
τ =B
− i
, i∈ Z
n
. (2.2)
In Figure 3 a symmetric drawing of the graph WH
4
(1, 0, 1, 3) from Figure 2 is given
in which the automorphismρ corresponds to a 4-fold rotation while the automorphismτ corresponds to reflection over the dotted line. We remark that in Figures 2 and 3, as well as

Accepted manuscript
6 Art Discrete Appl. Math.
in Figures 5 and 6 from Section 4, the vertices and edges are colored in such a way that the
vertices (or edges) from the same⟨ ρ ⟩ -orbit receive the same color. The sole purpose of this
coloring is to make it easier to keep track of vertices and edges in these figures and should
not be confused with the coloring of the edges we will be talking about in Section 4.
A0
B0
C0
A1
B1 C1
A2
B2
C2
A3
B3
C3
Figure 3: A symmetric drawing of the graph WH
4
(1, 0, 1, 3).
Note that WH
n
(a,b,c,d) = WH
n
(− a,b,c,d) and that for Γ = WH
n
(a,b,c,d) and
anyq∈ Z
n
, coprime ton, relabeling eachA
i
,B
i
andC
i
byA
qi
,B
qi
andC
qi
, respectively,
yields WH
n
(qa,qb,qc,qd). This shows that the following holds.
Lemma 2.3. Let Γ = WH
n
(a,b,c,d) be a WH-graph and letq∈ Z
n
be coprime ton.
Then Γ ∼ = WH
n
(qa,qb,qc,qd). In particular, Γ ∼ = WH
n
(a,− b,− c,− d).
Let Γ be a WH-graph and letρ ∈ Aut(Γ) be as in (2.1). The subgroup⟨ ρ ⟩ of Aut(Γ)
then has six orbits in its action on the edge set of Γ . We call the edges from the⟨ ρ ⟩ -orbit
ofA
0
A
a
thea-edges, those from the orbit ofA
0
B
0
the left edges, those from the orbit of
A
0
C
0
the right edges, and for each x∈{ b,c,d} the edges from the orbit of B
0
C
x
the
x-edges.
We also point out that each WH-graph has certain 6-cycles. These will play an im-
portant role in the determination of the automorphism group of the WH-graphs. For each
i∈ Z
n
we clearly have the 6-cycles (recall thatb,c andd are pairwise distinct)
(B
i
,C
i+b
,B
i+b− c
,C
i+b− c+d
,B
i− c+d
,C
i+d
). (2.3)
We call the 6-cycles of this form the canonical 6-cycles. Observe that these 6-cycles are
characterized by the fact that for any pair of antipodal edges on such a 6-cycle there exists
anx∈{ b,c,d} such that both of these edges arex-edges.

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 7
3 Nonexistenceofedge-transitiveWH-graphs
In this section we prove Theorem 3.7 which states that there are no edge-transitive WH-
graphs. One of the main tools in our proof is the following nice result of A. Lucchini, which
can be found in the book [10] (we point out that the result was discovered independently by
Herzog and Kaplan, see [7]), and has been used successfully several times before in various
classification results concerning symmetries of graphs (for instance in [2, 5, 11, 12, 14] to
name just a few).
Proposition3.1 ([7, 10]). LetG be a group containing a nontrivial cyclic subgroupH. If
|G|≤| H| 2
, thenH contains a nontrivial subgroup which is normal inG.
We will be applying the above result in the setting whereG is the automorphism group
of a WH-graph andH is the cyclic subgroup generated by the semiregular automorphism
ρ from (2.1). Before stating and proving the next proposition we recall the definition of a
2-arc-transitive graph and define the notion of a quotient graph that we will be using in this
paper.
A 2-arc of a graph is an ordered triple (u,v,w) of its vertices such thatu̸=w andv is
adjacent tou andw. A graph is 2-arc-transitive if its automorphism group acts transitively
on the set of its 2-arcs. Let Γ be a graph andK≤ Aut(Γ) . The quotient graph Γ K
of Γ with respect toK is the graph whose vertex set consists of the orbits ofK in its action on
the vertex set of Γ and in which two distinct orbitsO
1
andO
2
are adjacent whenever there
areu∈O
1
andv∈O
2
which are adjacent in Γ . Therefore, such a quotient graph is by
definition simple (in the sense that there are no loops or multiple edges).
Proposition 3.2. Let Γ = WH
n
(a,b,c,d) be a WH-graph and let ρ ∈ Aut(Γ) be as
in (2.1). Suppose Γ is edge-transitive and K ≤⟨ ρ ⟩ is a nontrivial normal subgroup of
Aut(Γ) . Then the quotient graph Γ K
of Γ with respect to K is also an edge-transitive
WH-graph. Moreover, if Γ is 2-arc-transitive, then Γ K
is also 2-arc-transitive.
Proof. SinceK is normal in Aut(Γ) , its orbits are blocks of imprimitivity for Aut(Γ) , and
so edge-transitivity implies that there are no edges of Γ joining two vertices from the same
K-orbit. Moreover, asB
0
is clearly the only neighbor ofA
0
in theK-orbit ofB
0
, edge-
transitivity also implies that for each vertex of Γ its four neighbors are in four different
K-orbits. Therefore, the quotient graph Γ K
is regular of valency 4. Since K ≤⟨ ρ ⟩ it
is now clear that Γ K
is a WH-graph. Moreover, the induced action of Aut(Γ) on Γ K
is
edge-transitive, and if Aut(Γ) acts 2-arc-transitively on Γ , then so does this induced action
of Aut(Γ) on Γ K
.
Our proof that there are no edge-transitive WH-graphs is carried out in two steps. We
first show that there are no 2-arc-transitive WH-graphs and then show that there are also no
edge-transitive ones. But first we make a useful observation.
Lemma3.3. There are no edge-transitive WH-graphs of girth 3. Consequently, if the graph
WH
n
(a,b,c,d) is edge-transitive, thenb,c andd are all nonzero.
Proof. Suppose Γ = WH
n
(a,b,c,d) is edge-transitive and is of girth 3. Letx∈{ b,c,d} .
Since Γ is edge-transitive, the edge B
0
C
x
is contained in a 3-cycle, and so B
0
and C
x
have a common neighbor. By definition of Γ this is only possible if x = 0 (and this
common neighbor is A
0
). But then b = c = d = 0, contradicting the assumption from
Construction 2.1 thatb,c andd are pairwise distinct.

Accepted manuscript
8 Art Discrete Appl. Math.
Using Lemma 2.3 by which we can assume thata dividesn, together with Lemma 3.3,
a computer search for all relatively small edge-transitive WH-graphs can be performed.
A couple of hours of computation using a suitable package such as MAGMA [3] on an
ordinary computer reveals that there are no edge-transitive WH-graphs of order up to 3· 71
(that is, withn≤ 71). For ease of reference we record this fact as an observation.
Observation3.4. There exists no edge-transitive WH-graph WH
n
(a,b,c,d) withn≤ 71.
Proposition3.5. There are no 2-arc-transitive WH-graphs.
Proof. By way of contradiction, suppose 2-arc-transitive WH-graphs exist and let Γ =
WH
n
(a,b,c,d) be a smallest 2-arc-transitive WH-graph. Letρ be as in (2.1). By Proposi-
tion 3.2, no nontrivial subgroup of⟨ ρ ⟩ is normal in Aut(Γ) , and so Proposition 3.1 implies
that| Aut(Γ) | >n
2
. Since Γ is of order 3n and is 2-arc-transitive,| Aut(Γ) | = 3n· 12· t,
wheret is the order of a stabilizer of a 2-arc in Aut(Γ) . Thenn < 36t, and so Observa-
tion 3.4 implies thatt> 2. Analysing 6-cycles of Γ we now show that this is not possible.
Since Γ is 2-arc-transitive and possesses the canonical 6-cycles, there exists a positive
constantλ such that each 2-arc of Γ lies onλ different 6-cycles. Clearly, any 6-cycle of Γ containing the 2-pathP = (B
0
,A
0
,C
0
) is of the form
(C
x
,B
0
,A
0
,C
0
,B
− y
,A
− y
), (3.1)
where x,y ∈{ b,c,d} are such that x =− y. Therefore, the above 2-path P lies on a
6-cycle of Γ if and only if 2x = 0 for somex∈{ b,c,d} orx +y = 0 for a pair of distinct
x,y∈{ b,c,d} (or both). Since b,c and d are pairwise distinct and are all nonzero (by
Lemma 3.3), 2x = 0 for at most onex∈{ b,c,d} andx +y = 0 for at most one pair of
distinctx,y∈{ b,c,d} . Therefore, since a condition of the form 2x = 0 gives rise to one
6-cycle throughP , while a condition of the formx +y = 0 forx̸= y gives rise to two
6-cycles throughP , we have thatλ ∈{ 1, 2, 3} .
Suppose first thatλ = 1. Inspecting the canonical 6-cycles from (2.3) we see that in this
case, for any 2-path containing noA-vertices, the unique 6-cycle through it is a canonical 6-
cycle. It thus follows that the unique 6-cycle through the 2-path (A
0
,A
a
,C
a
) must contain
a 4-path of the form (A
0
,A
a
,C
a
,B
a− x
,A
a− x
), wherex∈{ b,c,d} . Therefore,A
0
and
A
a− x
must have a common neighbor, which obviously must be an A-vertex and is thus
A
− a
(and soa− x =− 2a). But then this 6-cycle and the one obtained by applyingρ a
are
two 6-cycles containing the 2-path (A
− a
,A
0
,A
a
), contradictingλ = 1.
Suppose next thatλ = 3. The above discussion shows that we can assume thatb =n/2
andc+d = 0. Consider the corresponding three 6-cycles from (3.1). The successors ofB
0
(in the direction of the 2-arc (C
0
,A
0
,B
0
)) on them areC
b
,C
c
andC
d
, and so each 3-arc
whose initial 2-arc is (C
0
,A
0
,B
0
) lies on a 6-cycle. As Γ is 2-arc-transitive, each 3-arc
lies on a 6-cycle. But this clearly is not the case for the 3-arc (B
0
,A
0
,A
a
,B
a
), since no
twoC-vertices are adjacent, showing thatλ ̸= 3.
We are left with the possibility λ = 2. Recall that in this case we can assume that
c +d = 0 andb̸= n/2. Again, inspecting the corresponding 6-cycles from (3.1) we find
that for each 2-arc (u,v,w) of Γ there is a uniquez∈ Γ( w)\{ v} (here Γ( w) is the set
of all neighbors ofw in Γ ) such that Γ has no 6-cycle containing the 3-arc (u,v,w,z), and
moreover, that the two 6-cycles of Γ through (u,v,w) have precisely these three vertices
in common. We now show that this contradicts t > 2. To this end, let (u,v,w) be any
2-arc of Γ , let x ∈ Γ( u)\{ v} and y ∈ Γ( w)\{ v} be the unique vertices such that

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 9
Γ has no 6-cycle through (x,u,v,w) or (u,v,w,y), and let u
′ ,u
′′ ,w
′ ,w
′′ be such that
Γ( u) ={ x,u
′ ,u
′′ ,v} , Γ( w) ={ v,w
′ ,w
′′ ,y} and that Γ has a 6-cycle through each of
(u
′ ,u,v,w,w
′ ) and (u
′′ ,u,v,w,w
′′ ), see Figure 4. Since one of the two 6-cycles through
u
′′ v
′′ w
′′ x u w v y
u
′ v
′ w
′ Figure 4: The local situation around a 2-arc in the case ofλ = 2.
(u
′ ,u,v) contains (u
′ ,u,v,w), we can also assume that Γ( v) ={ u,v
′ ,v
′′ ,w} , wherev
′′ is such that there are no 6-cycles through (u
′ ,u,v,v
′′ ) (note however that there is a 6-
cycle through (u
′ ,u,v,v
′ )). Suppose now thatα ∈ Aut(Γ) fixes each ofu,v andw. By
definition ofx andy it then also fixes each ofx andy. Now, suppose that in additionα also
fixes at least one ofu
′ ,u
′′ ,v
′ ,v
′′ ,w
′ ,w
′′ . Because of the two 6-cycles through (u,v,w) it
is clear that ifα fixes any ofu
′ ,u
′′ ,w
′ ,w
′′ it fixes each of them. Because of the two 6-
cycles through (u
′ ,u,v) it now follows that ifα fixes any ofu
′ ,u
′′ ,w
′ ,w
′′ it then also fixes
v
′ and thus alsov
′′ . Conversely, ifα fixes any ofv
′ andv
′′ , it fixes both, and then the fact
thatu
′ ∈ Γ( u)\{ v} is the unique vertex such that there is no 6-cycle through (v
′′ ,v,u,u
′ )
implies thatα also fixesu
′ (and thus each ofu
′ ,u
′′ ,w
′ ,w
′′ ). This thus shows that ifα fixes
any ofu
′ ,u
′′ ,v
′ ,v
′′ ,w
′ ,w
′′ it fixes each of them. It is now easy to see that any suchα also
fixes each neighbor of any ofx,y,u
′ ,u
′′ ,v
′ ,v
′′ ,w
′ ,w
′′ . Since Γ is connected, an inductive
approach then shows thatα is the identity. Therefore, the stabilizer of (u,v,w) in Aut(Γ)
has at most one nontrivial element, and sot≤ 2, a contradiction.
Before stating and proving the main result of this section we review a concept from [18]
that will play an important role in our proof. Here we only describe the part essential to our
proof, but see [18] for details. Suppose Γ is a tetravalent arc-transitive graph andC is a set
of cycles of Γ such that each edge of Γ lies on precisely one cycle fromC (in other words,
C is a decomposition of the edge set of Γ into cycles). If a subgroupG≤ Aut(Γ) preserves
the setC (that is, each element ofG maps cycles fromC to cycles fromC) then we say that
C is aG-invariant cycle decomposition of Γ . Our argument in the proof of Theorem 3.7
will rely on the following corollary of [18, Theorem 4.2].
Proposition 3.6 ([18]). Let Γ be a tetravalent arc-transitive graph. If Γ is not 2-arc-
transitive, then there exists at least one Aut(Γ) -invariant cycle decomposition of Γ .
Theorem3.7. There are no edge-transitive WH-graphs.
Proof. We first point out that since each WH-graph admits the automorphism τ from
Lemma 2.2 a WH-graph is edge-transitive if and only if it is arc-transitive. It thus suf-
fices to show that there are no arc-transitive WH-graphs. By way of contradiction, suppose

Accepted manuscript
10 Art Discrete Appl. Math.
arc-transitive WH-graphs do exist and let Γ = WH
n
(a,b,c,d) be a smallest arc-transitive
WH-graph. Proposition 3.5 implies that Γ is not 2-arc-transitive, and so Proposition 3.6
implies that Γ admits at least one Aut(Γ) -invariant cycle decomposition. LetC be one
of them. For an adjacent pair of vertices u, v of Γ we denote the unique member ofC
containing the edgeuv byC
uv
.
Just as in the proof of Proposition 3.5 we obtain that| Aut(Γ) | >n
2
. Since Γ is of order
3n and is arc-transitive,| Aut(Γ) | = 3n· 4· t, wheret is the order of a stabilizer of an arc
in Aut(Γ) . Thenn< 12t, and so Observation 3.4 implies thatt> 6. In particular,t> 1.
Now, letu be a vertex of Γ andv,v
′ ,w,w
′ be its four neighbors, where we have denoted
them in such a way that (v,u,v
′ ) is contained inC
uv
and (w,u,w
′ ) is contained inC
uw
.
Lets be the size of the intersection of the vertex sets ofC
uv
andC
uw
. Sincet > 1, there
exists an automorphismα ∈ Aut(Γ) fixingv andu while moving at least one ofv
′ ,w and
w
′ , but asC is Aut(Γ) -invariant,α fixesC
uv
pointwise and reflectsC
uw
with respect tou.
Consequently,α fixes each of thes common vertices ofC
uv
andC
uw
while reflectingC
uw
,
and sos≤ 2 must hold. As Γ is vertex-transitive andC is Aut(Γ) -invariant, each pair of
distinct nondisjoint cycles ofC meets ins vertices.
Consider now the left edge A
0
B
0
. With no loss of generality we can assume that
the member ofC containing this edge contains the 2-path (A
0
,B
0
,C
c
). Applying the
automorphism τρ c
, where ρ and τ are from Lemma 2.2, we see that this cycle in fact
contains the 3-path (A
0
,B
0
,C
c
,A
c
). Moreover, considering the orbits of this cycle under
the subgroup⟨ ρ ⟩ we see that the other member ofC containing the vertexB
0
consists solely
ofb- andd-edges and is thus of the form (B
0
,C
b
,B
b− d
,C
2b− d
,... ). Edge-transitivity of
Γ therefore implies that all members ofC are of length
2n
gcd(d− b,n)
. (3.2)
We distinguish two possibilities depending on what the cycleC
A0B0
looks like.
CASE 1: there is a cycle inC containing (B
0
,A
0
,C
0
).
In view of the automorphismρ it is clear that, besides the cycles consisting solely of theb-
andd-edges,C consists of all the cycles of the forms
(...,A
i
,A
i+a
,A
i+2a
,... ),i∈ Z
n
(...,B
i
,A
i
,C
i
,B
i− c
,A
i− c
,C
i− c
,B
i− 2c
,... ),i∈ Z
n
.
The first of these are of lengthn/ gcd(a,n) while the second are of length 3n/ gcd(c,n).
As both of these lengths need to equal the length from (3.2), we obtain gcd(d− b,n) =
2 gcd(a,n) and gcd(c,n) = 3 gcd(a,n). In particular,⟨ c⟩ is an index 3 subgroup of⟨ a⟩ in
Z
n
. The intersection of the two members ofC containing the vertexA
0
is thus
{ A
i
: i∈⟨ a⟩∩⟨ c⟩} ={ A
i
: i∈⟨ c⟩} ,
and so s≤ 2 implies that 2c = 0. Lemma 3.3 thus forces n to be even and c = n/2.
The cycles fromC are therefore of length 6,n is divisible by 6, and the two members of
C containing A
0
meet in their antipodal pair of vertices. However, considering the two
members ofC containingB
0
we see that the antipodal vertex in one of them isB
n/ 2
, while
in the other one it is aC-vertex, which contradicts vertex-transitivity of Γ .
CASE 2: no cycle inC contains (B
0
,A
0
,C
0
).
With no loss of generality we can then assume that the cycleC
A0B0
contains (B
0
,A
0
,A
a
),

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 11
and so applyingρ we see that besides the cycles consisting solely of theb- andd-edges, the
only other members ofC are of the form
(...,B
i
,A
i
,A
i+a
,C
i+a
,B
i+a− c
,A
i+a− c
,A
i+2a− c
,C
i+2a− c
,B
i+2a− 2c
,... ), i∈ Z
n
.
This implies that the two members ofC containing the vertexB
0
are of the form
C
B0C
b
: (...,C
2d− b
,B
d− b
,C
d
,B
0
,C
b
,B
b− d
,... )
C
B0Cc
: (...,C
a
,A
a
,A
0
,B
0
,C
c
,A
c
,... ).
Since t > 1, there exists an automorphism α ∈ Aut(Γ) fixing each ofB
0
and C
b
but
interchanging A
0
and C
c
. It follows that α fixes the cycleC
B0C
b
pointwise and reflects
C
B0Cc
with respect toB
0
. In particular,α fixesB
b− d
and interchangesA
0
withC
c
, and
thus alsoC
A0C0
withC
CcB
c− d
. Observe that these two cycles are of the form
C
A0C0
: (...,B
− a
,A
− a
,A
0
,C
0
,B
− c
,... )
C
CcB
c− d
: (...,C
c− b+d
,B
c− b
,C
c
,B
c− d
,C
b+c− d
,... ).
Therefore, α maps C
b+c− d
to one of B
− a
and B
− c
. However, the fixed vertexB
b− d
is
adjacent toC
b+c− d
but is clearly not adjacent to any ofB
− a
andB
− c
, bringing us to the
final contradiction.
4 Thevertex-transitiveWH-graphs
While there are no edge-transitive WH-graphs, one can find vertex-transitive examples.
In fact, as the next two propositions show, there are infinitely many of them. Before
introducing the corresponding two infinite families we make a simple observation. Let
Γ = WH
n
(a,b,c,d) be a WH-graph and recall that Γ admits the automorphismsρ andτ from Lemma 2.2. The subgroup⟨ ρ,τ ⟩ of Aut(Γ) has two orbits on the vertex set of Γ with
one orbit consisting of all theA-vertices. It thus follows that Γ is vertex-transitive if and
only if there is an automorphism of Γ mapping at least oneA-vertex to aB- or aC-vertex.
Proposition 4.1. Letn≥ 4 be an even integer and leta,b,c,d be integers with 1≤ a <
n/2 and 0≤ b,c,d<n such thatb,c andd are pairwise distinct,a,b andd are odd, while
c is even, and each of the following holds:
• d = 2a +b;
• 2c = 3a + 3b.
Then the graph WH
n
(a,b,c,d) is vertex-transitive.
Proof. By the comment preceding the statement of this proposition we only need to exhibit
an automorphism of Γ = WH
n
(a,b,c,d) mapping anA-vertex to aB- or aC-vertex. Let
σ be the permutation of the vertex set of Γ defined by the rule given via the following table,
wherei∈ Z
n
:
i mod 2 A
i
σ B
i
σ C
i
σ 0 B
i
C
i+c
A
i
1 C
i− a+d
A
i+a+b
B
i− b+c− d
Due to the assumptions on the parity ofa,b,c andd it is clear thatσ is indeed a permutation
of the vertex set of Γ . Using the assumption that 2a = d− b and 2c = 3a + 3b one can

Accepted manuscript
12 Art Discrete Appl. Math.
also verify that it preserves adjacencies. For instance, while it is clear that the a-edges
A
i
A
i+a
withi even are mapped to edges of Γ , one can use the assumptiond = 2a +b to
see that also fori odd the vertexA
i+a
σ =B
i+a
is adjacent toA
i
σ =C
i− a+d
=C
i+a+b
.
Similarly, to see that the right edgesA
i
C
i
withi odd are mapped to edges of Γ , one needs
to show thatC
i− a+d
andB
i− b+c− d
are adjacent. Asd = 2a +b and 2c = 3a + 3b, we
see that C
i− a+d
= C
i+a+b
and B
i− b+c− d
= B
i− 2a− 2b+2c− c
= B
i+a+b− c
are indeed
adjacent. Thatσ preserves all other adjacencies is verified in a similar way and is left to
the reader.
Figure 5 shows symmetric drawings of the graphs WH
4
(1, 3, 0, 1) and WH
4
(1, 3, 2, 1),
the smallest two members of the family of vertex-transitive WH-graphs from Proposi-
tion 4.1. The colors of the vertices are consistent with Figure 2. For each of these drawings
the 6-fold rotation is an automorphism mapping an A-vertex to a B-vertex. We remark
that the counterclockwise rotation corresponds to the automorphism σρ 2
in the case of
WH
4
(1, 3, 0, 1) and to the automorphismσ in the case of WH
4
(1, 3, 2, 1), whereσ is as in
the proof of Proposition 4.1 andρ as in Lemma 2.2.
0
2
0
2
0
2
1
3
1 3
1
3
(a) WH
4
(1, 3, 0, 1)
0
0
0
2
2
2
1
1
1
3
3
3
(b) WH
4
(1, 3, 2, 1)
Figure 5: The smallest two examples of the family of WH-graphs from Proposition 4.1.
Proposition 4.2. Let m≥ 3 be an odd integer. Then the WH-graph WH
4m
(2,m− 2,
0,m + 2) is vertex-transitive.
Proof. As in the previous proof, we only need to show that there exists an automorphism
of Γ = WH
4m
(2,m− 2, 0,m + 2) which maps anA-vertex to aB- or aC-vertex. Since
m is odd, there is a uniqueδ ∈{ 1, 3} such thatm≡ δ (mod 4). Letθ be the permutation
of the vertex set of Γ defined by the rule given via the following table, wherei∈ Z
n
:
i mod 4 A
i
θ B
i
θ C
i
θ 0 B
i
A
i
C
i
δ C
i
B
i
A
i
2 C
i+m
A
i+m
B
i+m
4− δ B
i− m
C
i− m
A
i− m
Using the fact that m is odd and m≡ δ (mod 4), it is easy to verify that θ is indeed a
permutation of the vertex set of Γ . Sincec = 0, it is clear thatθ maps all of thec-edges, the

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 13
left edges and the right edges of Γ to edges of Γ . Asa = 2 it is also easy to verify that the
a-edges of Γ are all mapped to edges of Γ . To see that the b- and the d-edges are also
mapped to edges of Γ observe thatm− 2≡ m+2≡ 4− δ (mod 4). It is now not difficult
to verify that theb- and thed-edges are mapped to edges of Γ . For instance, in the case of
i≡ 0 (mod 4), we see thatB
i
θ = A
i
is indeed adjacent toC
i+m− 2
θ = A
i+m− 2− m
=
A
i− 2
and C
i+m+2
θ = A
i+m+2− m
= A
i+2
. We leave the remaining three cases to the
reader.
It turns out that WH
8
(2, 1, 0, 5) and WH
8
(2, 1, 4, 5) are both vertex-transitive and are
nonisomorphic. A symmetric drawing of each of them which is given in Figure 6 shows that
the 6-fold rotation is an automorphism mapping anA-vertex to aB-vertex. Clearly, these
two graphs belong to neither of the two families from Proposition 4.1 and Proposition 4.2.
Our goal in the remainder of this section is to prove that each vertex-transitive WH-graph
which is not isomorphic to one of these two sporadic small graphs is isomorphic to a WH-
graph from one of the two infinite families given by Proposition 4.1 and Proposition 4.2.
0
1 3
4
5 7
1 3
6
5 7
2
2
6
2
6
2
6
3
4
5
7
0
1
(a) WH
8
(2, 1, 0, 5)
0 4
0
4
4
0
1
3 6
5
7 2
2
1
7
6
5
3
3
2
5
7
6
1
(b) WH
8
(2, 1, 4, 5)
Figure 6: The two sporadic vertex-transitive WH-graphs.
We start by introducing some further terminology and by making a few useful observa-
tions, which we record in Proposition 4.3 for ease of reference. Let Γ = WH
n
(a,b,c,d)
be a vertex-transitive WH-graph and letH =⟨ ρ,τ ⟩ , whereρ andτ are as in Lemma 2.2.
Since Γ is vertex-transitive, Theorem 3.7 implies that the four edges incident toA
0
are not
in the same Aut(Γ) -orbit. As these four edges come from twoH-orbits, Aut(Γ) has pre-
cisely two orbits on the edge set of Γ and each vertex is incident to two edges from each of
these two orbits. LetR be the Aut(Γ) -orbit of the edgeA
0
A
a
. Applyingρ − a
we see that
A
− a
A
0
∈R , and soA
0
A
a
andA
− a
A
0
are the two edges fromR incident toA
0
. LettingB
be the Aut(Γ) -orbit of the edgeA
0
B
0
we thus see thatR andB are the two Aut(Γ) -orbits
on the edge set of Γ . We call the edges fromR red and the ones fromB blue. Since each
vertex is incident to two red and to two blue edges this gives rise to red cycles and blue
cycles.
The red cycle containing the red edgeA
0
A
a
is (A
0
,A
a
,A
2a
,...,A
− a
) and is thus of
length n/ gcd(a,n). Since A
0
B
0
is blue, there is precisely one x∈{ b,c,d} such that
B
0
C
x
is also blue. With no loss of generality assumeB
0
C
c
is blue. Applyingρ c
we thus

Accepted manuscript
14 Art Discrete Appl. Math.
see that the blue cycles are of the form (A
i
,B
i
,C
i+c
,A
i+c
,B
i+c
,C
i+2c
,A
i+2c
,...,C
i− c
),
i∈ Z
n
. It follows that the red cycle throughB
0
is (B
0
,C
d
,B
d− b
,C
2d− b
,B
2(d− b)
,...,C
b
)
and is thus of length 2n/ gcd(d− b,n). Since all red cycles must be of the same length,
we must have that 2 gcd(a,n) = gcd(d− b,n). In particular,n and the order|a| ofa are
both even. Our agreement regarding the colors of edges can be seen in Figure 7 where the
choice of colors is represented via the Wooly Hat diagram and is shown in the case of the
WH-graph WH
4
(1, 3, 0, 1).
A
B C
a
b
c
d
n
A0
B0 C0
A1
B1 C1
A2
B2 C2
A3
B3 C3
Figure 7: The red and blue edges and a basic 6-cycle in WH
4
(1, 3, 0, 1).
Recall that each WH-graph possesses canonical 6-cycles and note that each canonical
6-cycle consists of four red and two blue edges where the blue edges are antipodal on this
cycle. We call all 6-cycles consisting of four red and two blue edges where the blue edges
are antipodal on this cycle basic. Since Γ is vertex-transitive, there exists a basic 6-cycle
containing the red 2-pathP = (A
0
,A
a
,A
2a
). Since no red 2-path can connect aB-vertex
to aC-vertex it follows that the two blue edges of any basic 6-cycle containingP are either
both left edges or are both right edges. It is thus clear that one of 2a =d− b or 2a =b− d
must hold. With no loss of generality we assume that 2a =d− b holds. An example of a
basic 6-cycle in the graph WH
4
(1, 3, 0, 1) is highlighted in Figure 7.
Suppose one of b and d is 0, say b = 0. Then the red edge B
0
C
b
lies on a 3-cycle
containing two blue edges. SinceR is an Aut(Γ) -orbit the same should hold for the red
edgeB
0
C
d
, clearly forcingd = 0 and thus contradicting the fact thatd̸= b. Therefore,b
andd must both be nonzero.
We finally look at the intersections of blue and red cycles. The intersection of the blue
and the red cycle containing the vertexA
0
is
{ A
i
: i∈⟨ a⟩∩⟨ c⟩} . (4.1)
On the other hand, taking into account thatd− b = 2a, the intersection of the blue and the
red cycle containing the vertexB
0
is
{ B
i
: i∈⟨ 2a⟩∩⟨ c⟩}∪{ C
i
: i∈ (b +⟨ 2a⟩ )∩⟨ c⟩} .
Note that the distance on the corresponding blue cycle between any two vertices from (4.1)
is a multiple of 3. However, the distance on the corresponding blue cycle between B
0

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 15
and any potential vertex from{ C
i
: i∈ (b +⟨ 2a⟩ )∩⟨ c⟩} is never a multiple of 3. By
vertex-transitivity we thus get
(b +⟨ 2a⟩ )∩⟨ c⟩ =∅ and ⟨ a⟩∩⟨ c⟩ =⟨ 2a⟩∩⟨ c⟩ . (4.2)
This shows that lcm(gcd(a,n), gcd(c,n)) = lcm(gcd(2a,n), gcd(c,n)). Since the order
ofa is even, gcd(2a,n) = 2 gcd(a,n), and so gcd(c,n) is even. In fact, if we define the 2-
part of a positive integerm to be 2
k
, wherek≥ 0 is the largest integer such that 2
k
divides
m, we have thus shown that the 2-part of gcd(c,n) is larger than the 2-part of gcd(a,n).
We record all of the above observations for ease of future reference.
Proposition4.3. Let Γ = WH
n
(a,b,c,d) be a vertex-transitive WH-graph. Then, chang-
ing the roles ofb,c andd if necessary, the following hold:
• n is even.
• b andd are both nonzero.
• 2a =d− b.
• The 2-part of gcd(c,n) is larger than the 2-part of gcd(a,n). In particular,c is even.
• The two Aut(Γ) -orbits on the edge set of Γ areB andR, whereB consists of all the
left, the right and thec-edges, whileR consists of all thea-, theb- and thed-edges.
Our classification of the vertex-transitive WH-graphs relies heavily on the analysis of
certain structures in these graphs in relation to the two colors of edges. In particular, the
following notion will play an important role. We say that two vertices of a WH-graph are
basicallyR-antipodal if there exists a basic 6-cycle on which each of them is incident to
two red edges (and so they are antipodal on this cycle). We also say that a path, a walk
or a cycle is red (blue, respectively) if all of its edges are red (blue, respectively) and is
alternating if no two consecutive edges of it are of the same color.
Before proceeding with our analysis a remark is in order. Observe that the above result
ensures that for a vertex-transitive Γ = WH
n
(a,b,c,d) the order ofa is even. Therefore,
d− b = 2a implies that the orbits of the subgroup⟨ ρ 2a
⟩ , where ρ is as in (2.1), are
blocks of imprimitivity for Aut(Γ) (each of them coincides with a set consisting of every
other vertex of a red cycle). One could thus consider the quotient graph with respect to
these blocks (where we regard the “double” red edge as a single edge) and obtain a cubic
graph on which the induced action of Aut(Γ) is vertex-transitive. This graph is of course
a tricirculant (in the sense that it admits a semiregular automorphism with three orbits),
and so one could use the results of [19] where all cubic vertex-transitive tricirculants were
classified. Nevertheless, the relevant result, namely [19, Theorem 4.2], only classifies the
graphs up to isomorphism, its proof is very long and technical (about 11 pages), and even
so one would still need to carefully examine what the conclusions of that result on our
quotient graph say about the original parametersn,a,b,c andd. Especially so since the
quotient might (and in fact quite often is) be one of the sporadic small graphs of orders 6
(the prism) and 12 (the truncation ofK
4
) from [19, Table 1]. This is why we have decided
to take a direct approach without referring to the results of [19].
We start our analysis with a useful observation regarding red 2-paths and basic 6-cycles.
Lemma4.4. Let Γ = WH
n
(a,b,c,d) be a vertex-transitive WH-graph where the param-
etersn,a,b,c andd are as in Proposition 4.3. Then the following hold:

Accepted manuscript
16 Art Discrete Appl. Math.
• If 4a̸= 0 then each red 2-path lies on precisely two basic 6-cycles.
• If 4a = 0 then each red 2-path lies on precisely four basic 6-cycles.
Proof. Let us consider the basic 6-cycles containing the red 2-path (B
0
,C
d
,B
d− b
). Clearly,
if at least one of its two blue edges is a left edge (and so there are also twoa-edges on this
cycle) then both are left edges. If this is indeed the case, then the 6-cycle must contain
(A
0
,B
0
,C
d
,B
d− b
,A
d− b
). Since d− b = 2a, one of the possibilities for the remaining
vertex of this basic 6-cycle is A
a
. The only other possibility is A
− a
which gives rise to
a 6-cycle if and only if− 2a = 2a (which is equivalent to 4a = 0). A similar situation
occurs if both blue edges arec-edges, where we seek for red 2-paths connectingC
c
and
C
d− b+c
. One possibility results in a canonical 6-cycle while the other is only possible if
2(d− b) = 0, which is of course equivalent to 4a = 0.
Let Γ = WH
n
(a,b,c,d) be a vertex-transitive WH-graph, where a,b,c,d are as in
Proposition 4.3. Consider the part of Γ depicted on Figure 8. We see that the blue edge
B0 A0 C
a+b
A
a+b
Aa Ba
C
3a+b
A
3a+b
A2a B2a
A
2a+b
C
2a+b
Figure 8: The situation around the blue edgeA
a
B
a
.
A
a
B
a
has the property that each of its endvertices has a basicallyR-antipodal vertex, say
u for one endvertex andv for the other, such thatu andv are connected by a blue edge. Let
ρ andτ be as in Lemma 2.2. SinceB is an Aut(Γ) -orbit andτρ c
flips the blue edgeB
0
C
c
,
there is an automorphismη ∈ Aut(Γ) such thatA
a
η =B
0
andB
a
η =C
c
. ThenC
2a+b
η is basicallyR-antipodal toB
0
,A
2a+b
η is basicallyR-antipodal toC
c
, andC
2a+b
η is con-
nected toA
2a+b
η by a blue edge. The next result gives the three possible conditions on the
parameters that are obtained from the corresponding analysis of the different possibilities.
Proposition 4.5. Let Γ = WH
n
(a,b,c,d) be a vertex-transitive WH-graph where the
parametersn,a,b,c andd are as in Proposition 4.3. Then one of the following holds:
• 2c = 3a + 3b.
• 4a = 0 and 4c = 4b +n/2.
• 4c = 4a + 4b.
Proof. Letη ∈ Aut(Γ) be as in the paragraph preceding this proposition. We consider the
possibilities for C
2a+b
η and A
2a+b
η and analyse the different corresponding conditions
under which these two vertices are connected by a blue edge.
Suppose first that 4a̸= 0. Then Lemma 4.4 implies that there are only two possibilities
for each ofC
2a+b
η andA
2a+b
η . It is easy to verify (see Figure 9) that in this case
C
2a+b
η ∈{ A
a+b
,C
2a+2b− c
} and A
2a+b
η ∈{ A
c− a− b
,B
2c− 2a− 2b
} .

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 17
A
b
A
c− b
A
c− a− b
A
a+b
C
b
B
c− b
A
2a+b
A
c− 2a− b
B0 Cc
C
2c− b
B
b− c
C
2a+2b− c
B
2c− 2a− 2b
C
2a+b
B
c− 2a− b
C
2c− 2a− b
B
2a+b− c
Figure 9: The situation around the blue edgeB
0
C
c
when 4a̸= 0.
IfC
2a+b
η =A
a+b
, then for this vertex to be connected toA
2a+b
η by a blue edge we must
have thatA
2a+b
η =B
2c− 2a− 2b
anda +b = 2c− 2a− 2b, that is 2c = 3a + 3b. Similarly,
if A
2a+b
η = A
c− a− b
, then C
2a+b
η = C
2a+2b− c
and c− a− b = 2a + 2b− c, again
yielding 2c = 3a + 3b. The only remaining possibility is thatC
2a+b
η = C
2a+2b− c
and
A
2a+b
η =B
2c− 2a− 2b
with 3c− 2a− 2b = 2a + 2b− c, that is 4c = 4a + 4b.
Suppose now that 4a = 0. Since 2a̸= 0, this implies thatn is divisible by 4 and that
a∈{ n/4, 3n/4} . This time Lemma 4.4 implies that there are four possibilities for each
ofC
2a+b
η andA
2a+b
η . However, as is evident from Figure 10 the extra possibilities are
just the antipodal vertices on the corresponding red 4-cycles (which are just the vertices
obtained by addingn/2 to the subscript) of the vertices obtained in the case of 4a̸= 0. In
other words,
C
2a+b
η ∈{ A
b+n/ 4
,A
b+3n/ 4
,C
2b− c
,C
2b− c+n/ 2
} and
A
2a+b
η ∈{ A
c− b+n/ 4
,A
c− b+3n/ 4
,B
2c− 2b
,B
2c− 2b+n/ 2
} .
If one ofA
b+n/ 4
,A
b+3n/ 4
is connected by a blue edge to one ofB
2c− 2b
,B
2c− 2b+n/ 2
, then
A
a+b
A
b
A
c− b
A
c− a− b
C
b
B0 Cc B
c− b
A
a+b+n/ 2
A
b+n/ 2
A
c− b+n/ 2
A
c− a− b+n/ 2
B
2c− 2b
C
2c− b
B
b− c
C
2b− c
C
b+n/ 2
B
n/ 2
C
c+n/ 2
B
c− b+n/ 2
B
b− c+n/ 2
B
2c− 2b+n/ 2
C
2b− c+n/ 2
C
2c− b+n/ 2
Figure 10: The situation around the blue edgeB
0
C
c
when 4a = 0.
2c = 3b+n/4 or 2c = 3b+3n/4. Exchanging the roles ofa and− a if necessary (note that
2a = 2(− a), and so we do not violate the assumptiond = 2a+b this way) we thus see that

Accepted manuscript
18 Art Discrete Appl. Math.
2c = 3a + 3b. A similar conclusion can be made if one ofC
2b− c
,C
2b− c+n/ 2
is connected
by a blue edge to one ofA
c− b+n/ 4
,A
c− b+3n/ 4
. Finally, suppose one ofC
2b− c
,C
2b− c+n/ 2
is connected by a blue edge to one ofB
2c− 2b
,B
2c− 2b+n/ 2
. Then one of 4c = 4b(= 4b+4a)
or 4c = 4b +n/2 holds, as claimed.
We now show that each of the three possibilities from the above proposition leads to the
graphs from Proposition 4.1, Proposition 4.2 or to the two sporadic examples withn = 8,
mentioned at the beginning of this section. The first possibility is easy to handle, while the
other two require a more detailed analysis of the structure of the corresponding graphs.
Proposition 4.6. Let Γ = WH
n
(a,b,c,d) be a vertex-transitive WH-graph where the
parametersn,a,b,c andd are as in Proposition 4.3. If 2c = 3a + 3b thena,b andd are
all odd, and so Γ belongs to the family of graphs from Proposition 4.1.
Proof. Proposition 4.3 implies thatn is even, and so 2c = 3a + 3b implies thata +b is
also even. Therefore,a andb are of the same parity. Sinced = 2a +b andc is even, the
fact that by definition Γ is connected implies thata,b andd must all be odd.
Proposition4.7. Let WH
n
(a,b,c,d) be a vertex-transitive WH-graph where the parame-
tersn,a,b,c andd are as in Proposition 4.3, 4a = 0 and 4c = 4b +n/2. Thenn = 8,
c∈{ 0, 4} and, exchanging the pair{ b,d} with{− b,− d} if necessary,{ b,d} ={ 1, 5} .
Proof. Let Γ = WH
n
(a,b,c,d) and suppose 4a = 0 and 4c = 4b +n/2. Since 2a̸= 0
but 4a = 0,n is divisible by 4 anda∈{ n/4, 3n/4} . Consequently, as 4(c− b) =n/2,n
in fact must be divisible by 8. Sincea is thus even,b must be odd (otherwise, asc is even
andd =b + 2a, Γ is not connected). Moreover, no odd prime divisor ofn can divideb as
otherwise it would also dividec (and of coursea), again contradicting the assumption that
Γ is connected. Therefore,b is coprime ton, and so Lemma 2.3 implies that we can assume
b = 1. We thus get 4c = 4 +n/2, and so 2(c− 1)∈{ n/4, 3n/4} ={ a,− a} . Consider
now the situation around the blue 2-path (A
0
,B
0
,C
c
) depicted on Figure 11. By vertex-
A0 Cc
B2c− 2 C2c− 1
Bc− 1 A2c− 2
A
2c− 2+n/ 2
B
2c− 2+n/ 2
C
2c− 1+n/ 2
B
c− 1+n/ 2
B0
Figure 11: The situation around the blue 2-path (A
0
,B
0
,C
c
).
transitivity and sinceτ ∈ Aut(Γ) there existsη ∈ Aut(Γ) mappingA
0
toB
0
,B
0
toA
0
andC
c
toC
0
. Note that{ B
2c− 2
η,B
2c− 2+n/ 2
η } and{ C
2c− 1
η,C
2c− 1+n/ 2
η } are pairs of
antipodal vertices on the same red 4-cycle. Since{ A
2c− 2
η,A
2c− 2+n/ 2
η } ={ C
1
,C
1+n/ 2
} and{ B
c− 1
η,B
c− 1+n/ 2
η } ={ B
− 1
,B
− 1+n/ 2
} , we see that
{ B
2c− 2
η,B
2c− 2+n/ 2
η }∈{{ A
1
,A
1+n/ 2
} ,{ B
1− c
,B
1− c+n/ 2
}}

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 19
and
{ C
2c− 1
η,C
2c− 1+n/ 2
η }∈{{ A
− 1
,A
− 1+n/ 2
} ,{ C
c− 1
,C
c− 1+n/ 2
}} .
Since all of the indices of these twoB-vertices and these twoC-vertices are odd (recall that
c andn/2 are both even) andb = 1 andd = 1 +n/2 are also odd, it thus follows that there
are no red edges between the pairs{ B
1− c
,B
1− c+n/ 2
} and{ C
c− 1
,C
c− 1+n/ 2
} , and so the
only possibility is that{ A
1
,A
1+n/ 2
} and{ A
− 1
,A
− 1+n/ 2
} are the two pairs of antipodal
vertices on the same red 4-cycle. But then− 1 +n/4∈{ 1, 1 +n/2} which is clearly only
possible if− 1 +n/4 = 1, implying thatn = 8. To complete the proof, observe that since
a is even, Proposition 4.3 implies thatc is divisible by 4, and soc∈{ 0, 4} , completing the
proof.
We now finally analyse the last of the three possibilities from Proposition 4.5. In fact,
in view of Proposition 4.6, it suffices to consider the possibility that 4c = 4a + 4b but
2c̸= 3a + 3b. Before making this analysis we introduce some more terminology. Suppose
Γ = WH
n
(a,b,c,d) is a vertex-transitive WH-graph where the parametersn,a,b,c andd
are as in Proposition 4.3 and 4c = 4a + 4b but 2c̸= 3a + 3b. Note that this implies that we
cannot at the same time have 4a = 0 with 4c = 4b +n/2.
Suppose first that 4a̸= 0. The proof of Proposition 4.5 then reveals that for the blue
edgeB
0
C
c
there is a unique basicallyR-antipodal vertex ofB
0
(namelyC
2a+2b− c
) and a
unique basicallyR-antipodal vertex ofC
c
(namelyB
2c− 2a− 2b
) such that these two vertices
are connected by a blue edge. SinceB is an Aut(Γ) -orbit this means that for any blue edge
uv there is a unique blue edge u
′ v
′ such that u
′ is basicallyR-antipodal to v and v
′ is
basicallyR-antipodal tou. In this case we say that the blue edgeu
′ v
′ corresponds to the
blue edgeuv and more precisely that the blue arc (u
′ ,v
′ ) corresponds to the blue arc (u,v).
Of course, the relation of correspondence is symmetric and if (u
′ ,v
′ ) corresponds to (u,v),
then (v
′ ,u
′ ) corresponds to (v,u). Using the automorphismρ from (2.1) and the fact that
we have the situation from Figure 8 we clearly get the following.
Lemma 4.8. Let WH
n
(a,b,c,d) be a vertex-transitive WH-graph where the parameters
n,a,b,c andd are as in Proposition 4.3. Suppose 4a̸= 0, 4c = 4a + 4b and 2c̸= 3a + 3b.
Then the following holds for eachi∈ Z
n
:
• (A
i
,B
i
) corresponds to (A
i+a+b
,C
i+a+b
).
• (B
i
,C
i+c
) corresponds to (B
i+2c− 2a− 2b
,C
i+3c− 2a− 2b
).
The situation is slightly different in the case where 4a = 0. Namely, the proof of
Proposition 4.5 reveals that in this case there are two blue edges that correspond to a given
blue edge in the above sense. However, in the case of 4a = 0 each blue edge clearly
lies on four basic 6-cycle but on each of them the antipodal blue edge is the same. We
can thus speak about basic pairs of blue edges (two blue edges lying on the same basic
6-cycle). In this sense however each basic pair of blue edges corresponds in the above way
to a unique basic pair of blue edges and it is also clear how to again introduce this concept
for blue arcs. Since the “basic counterpart” of (A
i
,B
i
) is (A
i+n/ 2
,B
i+n/ 2
) and similarly
for the other two types of blue edges, we simplify the notation by writing (A
i
,B
i
) for
{ (A
i
,B
i
), (A
i+n/ 2
,B
i+n/ 2
)} (and similarly for the other types of blue edges). With this
agreement it is now easy to see (see also Figure 10) that we get the following.

Accepted manuscript
20 Art Discrete Appl. Math.
Lemma 4.9. Let WH
n
(a,b,c,d) be a vertex-transitive WH-graph where the parameters
n,a,b,c andd are as in Proposition 4.3. Suppose 4a = 0 and 4c = 4b but 2c̸= 3a + 3b.
Then the following holds for eachi∈ Z
n
:
• (A
i
,B
i
) corresponds to (A
i+a+b
,C
i+a+b
).
• (B
i
,C
i+c
) corresponds to (B
i+2c− 2b
,C
i+3c− 2b
).
Proposition 4.10. Let Γ = WH
n
(a,b,c,d) be a vertex-transitive WH-graph where the
parametersn,a,b,c andd are as in Proposition 4.3. If 4c = 4a + 4b but 2c̸= 3a + 3b
thenn = 4m for an odd integerm,c = 0 and, using an isomorphism from Lemma 2.3 if
necessary, we have thata = 2,b =m− 2 andd =m + 2. In particular, Γ belongs to the
family of graphs from Proposition 4.1.
Proof. As was explained in the paragraphs preceding Lemma 4.8 and Lemma 4.9 we have
the notion of corresponding pairs of blue arcs (if 4a̸= 0) or corresponding pairs of basic
pairs of blue arcs. We claim thata +b is of order 4 (inZ
n
). We describe how to see this
in the case that 4a̸= 0 but a completely analogous argument works also in the case of
4a = 0, where one needs to work with correspondence between basic pairs of blue arcs
instead of correspondence between blue arcs. Suppose then that 4a̸= 0 and let us consider
the following. We start at a given blue arc (u,v) and then inductively construct a sequence
of blue arcs as follows. Let (u
′ ,v
′ ) be the corresponding blue arc of (u,v). There is then
a unique blue arc of the form (u
′ ,w), wherew̸= v
′ . The blue arc in our sequence that
follows (u,v) is then set to be (u
′ ,w). Now, using Lemma 4.8 and taking into account the
assumption 4c = 4a + 4b we find that starting with the initial blue arc (B
0
,C
c
) we get the
sequence
(B
0
,C
c
)→ (B
2c− 2a− 2b
,A
2c− 2a− 2b
)→ (C
2c− a− b
,B
c− a− b
)→ → (C
a+b
,A
a+b
)→ (B
0
,C
c
)→··· which thus has precisely four distinct elements. AsB is an Aut(Γ) -orbit and we have the
automorphismτ from (2.2), the same must hold for the sequence starting with the blue arc
(A
0
,B
0
). Here we get the sequence
(A
0
,B
0
)→ (A
a+b
,B
a+b
)→ (A
2a+2b
,B
2a+2b
)→··· ,
thus showing thata +b is of order 4 inZ
n
, as claimed.
This implies thatn is divisible by 4 and 4c = 0. Moreover, no odd prime divisor ofn
(which of course dividesc) can divide any ofa andb since otherwise it divides both (and
thus alsod = 2a +b), contradicting the assumption that Γ is connected. Moreover, sincec
is even at least one ofa andb is odd, and so is coprime ton. Now, supposeb is even. Then
a is odd and thus coprime ton, and so 0∈ b +⟨ 2a⟩ , contradicting (4.2). Therefore,b is
odd and thus coprime ton.
If a is odd, then Lemma 2.3 implies that we can assume a = 1, and so a +b being
even and of order 4 forces n to be divisible by 8 and b ∈ { n/4− 1, 3n/4− 1} . Us-
ing Lemma 2.3 with q =− 1 if necessary we can thus assume that{ b,d} ={ n/4− 1,
n/4 + 1} . Now, 4c = 0 implies that c ∈ { 0,n/4,n/2, 3n/4} . Consider the closed
walk (A
0
,A
1
,A
2
,...,A
n/ 4− 1
,C
n/ 4− 1
,B
0
,A
0
) of lengthn/4 + 2 and note that its first
n/4− 1 edges are red, which are then followed by a blue, a red and another blue edge.
Vertex-transitivity and the fact that we have the automorphism τ imply that there is an

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 21
automorphism η ∈ Aut(Γ) mapping this walk to a walk starting with the red 2-path
(B
0
,C
n/ 4+1
,B
2
). ThenA
n/ 4− 2
η =B
n/ 4− 2
(recall thatn/4 is even) and thusA
n/ 4− 1
η =
C
n/ 2− 1
. Clearly, ifη maps at least one of the two blue edges of the above walk to a left
or a right edge, none of them can be mapped to ac-edge. But asA
0
andA
n/ 2− 1
are not
adjacent, this shows that η maps both blue edges of the walk to c-edges, and so C
c
and
B
n/ 2− 1− c
are adjacent via a red edge, that is 2c + 1 +n/2∈{ n/4− 1,n/4 + 1} . Since
2c∈{ 0,n/2} , this is only possible ifn = 8 and 2c = 4. But then the blue edgeB
0
C
c
lies
on two alternating 4-cycles, while the blue edgeA
0
B
0
lies on just one, a contradiction.
This finally shows that b is odd and a is even. Since 4(a + b) = 0 and a + b is
odd,n≡ 4 (mod 8). Since the 2-part of gcd(a,n) is at least 2 and the 2-part ofn is 4,
Proposition 4.3 and 4c = 0 imply that in factc = 0 and the 2-part of gcd(a,n) is 2. In
view of Lemma 2.3 we can thus assume thata = 2. Asa +b is of order 4 inZ
n
, we must
have thatb∈{ n/4− 2, 3n/4− 2} . Ifb =n/4− 2 thend =b + 2a =n/4 + 2. If however
b = 3n/4− 2, thend = 3n/4 + 2 and using Lemma 2.3 withq =− 1 shows that we can
in fact assume{ b,d} ={ n/4− 2,n/4 + 2} , as claimed.
This finally proves the main result of this section.
Theorem 4.11. Let Γ = WH
n
(a,b,c,d) be a WH-graph. Then Γ is vertex-transitive if
and only ifn is even and after possibly changing the roles ofb,c andd, possibly replacing
a by− a and possibly using an isomorphism from Lemma 2.3 we have thatd = 2a +b and
one of the following holds:
(1) Γ is one of WH
8
(2, 1, 0, 5) and WH
8
(2, 1, 4, 5), or
(2) a,b andd are all odd,c is even and 2c = 3a + 3b, or
(3) n = 4m withm> 1 odd and Γ = WH
4m
(2,m− 2, 0,m + 2).
We remark that the smallest two members of the family from item (2) of the above theo-
rem are the nonisomorphic graphs WH
4
(1, 3, 0, 1) and WH
4
(1, 3, 2, 1), while the smallest
member of the family from item (3) of Theorem 4.11 is the graph WH
12
(2, 1, 0, 5).
5 Concludingremarks
As was mentioned in the Introduction, tetravalent vertex-transitive but not arc-transitive
graphs can be useful when constructing tetravalent semisymmetric graphs. In particu-
lar, [21, Theorem 5.2] states that each worthy (no two vertices have the same set of neigh-
bors) tetravalent semisymmetric graph of girth 4 arises from what is called a “suitable
LR-structure” (see [21] for the definition). Not to add too much to the length of this paper,
let us simply say that the results of the previous sections imply that vertex-transitive WH-
graphs are very good candidates for suitable LR-structures. In particular, Lemma 2.2 and
Theorem 3.7 imply that a vertex-transitive WH-graph together with the natural coloring of
its edges, described in Section 4, giving rise to the red and blue cycles, is a suitable LR-
structure if and only if it has no alternating 4-cycles and for any of its vertices there exists
an automorphism fixing this vertex and two of its neighbors while interchanging the other
two neighbors.
It is easy to see that, of the WH-graphs appearing in Theorem 4.11, precisely those from
item (2) with the extra conditiona∈{± b,± d} have alternating 4-cycles. Moreover, one
can verify that the two sporadic examples WH
8
(2, 1, 0, 5) and WH
8
(2, 1, 4, 5) do admit

Accepted manuscript
22 Art Discrete Appl. Math.
automorphisms fixing a vertex and two of its neighbors while swapping the remaining two
neighbors. Moreover, as the automorphismθ from the proof of Proposition 4.2 fixes the
vertexC
0
and each ofB
− m− 2
andB
− m+2
while swappingB
0
withA
0
, the only vertex-
transitive WH-graphs that might not give rise to suitable LR-structures, are the ones from
item (2) of Theorem 4.11 for which eithera∈{± b,± d} or the only nontrivial automor-
phism fixing the vertexA
0
is the automorphismτ from Lemma 2.2.
It is easy to see that if there is aq∈ Z
n
such thatqa =− a,qc =c andqb =d (in which
cased = 2a +b impliesqd =b), then the permutation mapping eachA
i
toA
qi
,B
i
toB
qi
andC
i
toC
qi
is an automorphism of WH
n
(a,b,c,d) fixingA
0
,B
0
andC
0
but swapping
A
a
with A
− a
. Thus all WH-graphs admitting such a q∈ Z
n
are suitable LR-structures
(provided thata / ∈{± b,± d} ). We leave it as an open problem to determine if there are any
other LR-structures among the graphs from item (2) of Theorem 4.11 (that is those that do
not admit a “suitable”q).
Problem5.1. Determine whether there exist graphs from the second item of Theorem 4.11
for whicha / ∈{± b,± d} , there is noq∈ Z
n
withqa =− a,qc = c andqb = d, but they
do admit an automorphism fixingA
0
,B
0
andC
0
while swappingA
a
andA
− a
. In the case
they do, determine all such examples.
Finally, there is the natural question of which pairs of vertex-transitive WH-graphs are
isomorphic. Up to isomorphism, the only three members of the family from item (2) of
Theorem 4.11 of order 24 are WH
8
(1, 3, 2, 5), WH
8
(1, 7, 0, 1) and WH
8
(1, 7, 4, 1), none
of which is isomorphic to any of the two sporadic graphs from item (1) of Theorem 4.11.
Suppose Γ 1
= WH
n
(a,b,c,d) and Γ 2
= WH
4m
(2,m− 2, 0,m + 2) are isomorphic
graphs from items (2) and (3) of Theorem 4.11, respectively. Of course, n = 4m has to
hold. The blue cycles in Γ 2
are 3-cycles, while the red cycles of Γ 1
are of even length
(recall thata is odd). Therefore, a corresponding isomorphism maps the red cycles of Γ 1
to the red cycles of Γ 2
. But sincem is odd and the red cycles of Γ 2
are of length 2m, while
those of Γ 1
are of length 4m/ gcd(a, 4m), which is divisible by 4, this is not possible.
This contradiction shows that the only possible isomorphisms are among the graphs from
item (2) of Theorem 4.11. Of course, by Lemma 2.3 it suffices to consider the examples
witha dividingn. This brings us to our second open problem.
Problem5.2. Determine a necessary and sufficient condition for two graphsWH
n
(a,b,c,d)
and WH
n
(a,b
′ ,c
′ ,d
′ ) with a dividing n, both satisfying the conditions from item (2) of
Theorem 4.11, to be isomorphic.
References
[1] B. Alspach, D. Marušiˇ c and L. Nowitz, Constructing graphs which are 1/ 2-transitive, J. Aust.
Math. Soc. Ser. A 56 (1994), 391–402, doi:10.1017/S1446788700035564, https://doi.
org/10.1017/S1446788700035564.
[2] I. Antonˇ ciˇ c, A. Hujdurovi´ c and K. Kutnar, A classification of pentavalent arc-transitive bicir-
culants, J. Algebraic Comb. 41 (2015), 643–668, doi:10.1007/s10801-014-0548-z, https:
//doi.org/10.1007/s10801-014-0548-z.
[3] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J.
Symb. Comput.24 (1997), 235–265, doi:10.1006/jsco.1996.0125,https://doi.org/10.
1006/jsco.1996.0125.
[4] P. G. Doyle, On transitive graphs, Senior thesis, Harvard College, 1976.

Accepted manuscript
L. W. Berman et al.: Symmetries of the Woolly Hat graphs 23
[5] B. Frelih and K. Kutnar, Classification of cubic symmetric tetracirculants and pentacirculants,
Eur. J. Comb.34 (2013), 169–194, doi:10.1016/j.ejc.2012.08.005,https://doi.org/10.
1016/j.ejc.2012.08.005.
[6] J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley-Intersci. Ser. Discrete Math.
Optim., John Wiley & Sons, New York, 1987.
[7] M. Herzog and G. Kaplan, Large cyclic subgroups contain non-trivial normal subgroups,
J. Group Theory 4 (2001), 247–253, doi:10.1515/jgth.2001.022, https://doi.org/10.
1515/jgth.2001.022.
[8] D. F. Holt, A graph which is edge transitive but not arc transitive, J. Graph Theory
5 (1981), 201–204, doi:10.1002/jgt.3190050210, https://doi.org/10.1002/jgt.
3190050210.
[9] I. Hubard, A. Ramos-Rivera and P. Šparl, Arc-transitive maps with underlying rose window
graphs, J. Graph Theory 96 (2021), 203–230, doi:10.1002/jgt.22608,https://doi.org/
10.1002/jgt.22608.
[10] I. M. Isaacs, Finite Group Theory, volume 92 of Graduate Studies in Mathematics, American
Mathematical Society, Providence, RI, 2008, doi:10.1090/gsm/092, https://doi.org/
10.1090/gsm/092.
[11] I. Kovács, K. Kutnar and D. Marušiˇ c, Classification of edge-transitive rose window graphs,
J. Graph Theory 65 (2010), 216–231, doi:10.1002/jgt.20475, https://doi.org/10.
1002/jgt.20475.
[12] I. Kovács, K. Kutnar, D. Marušiˇ c and S. Wilson, Classification of cubic symmetric tricirculants,
Electron. J. Comb. 19 (2012), Paper 24, 14 pp., doi:10.37236/2371, https://doi.org/
10.37236/2371.
[13] I. Kovács, B. Kuzman, A. Malniˇ c and S. Wilson, Characterization of edge-transitive 4-valent
bicirculants, J. Graph Theory 69 (2012), 441–463, doi:10.1002/jgt.20594, https://doi.
org/10.1002/jgt.20594.
[14] I. Kovács, D. Marušiˇ c and M. Muzychuk, On G-arc-regular dihedrants and regular dihedral
maps, J. Algebraic Comb. 38 (2013), 437–455, doi:10.1007/s10801-012-0410-0,https://
doi.org/10.1007/s10801-012-0410-0.
[15] A. Malniˇ c, R. Nedela and M. Škoviera, Lifting graph automorphisms by voltage assignments,
Eur. J. Comb. 21 (2000), 927–947, doi:10.1006/eujc.2000.0390, https://doi.org/10.
1006/eujc.2000.0390.
[16] D. Marušiˇ c, Half-transitive group actions on finite graphs of valency4, J. Comb. Theory Ser.
B 73 (1998), 41–76, doi:10.1006/jctb.1997.1807, https://doi.org/10.1006/jctb.
1997.1807.
[17] D. Marušiˇ c and P. Šparl, On quartic half-arc-transitive metacirculants, J. Algebraic Comb.
28 (2008), 365–395, doi:10.1007/s10801-007-0107-y, https://doi.org/10.1007/
s10801-007-0107-y.
[18] Š. Miklaviˇ c, P. Potoˇ cnik and S. Wilson, Arc-transitive cycle decompositions of tetrava-
lent graphs, J. Comb. Theory Ser. B 98 (2008), 1181–1192, doi:10.1016/j.jctb.2008.01.005,
https://doi.org/10.1016/j.jctb.2008.01.005.
[19] P. Potoˇ cnik and M. Toledo, Classification of cubic vertex-transitive tricirculants, Ars Math.
Contemp. 18 (2020), 1–31, doi:10.26493/1855-3974.1815.b52, https://doi.org/10.
26493/1855-3974.1815.b52.
[20] P. Potoˇ cnik and S. Wilson, Tetravalent edge-transitive graphs of girth at most 4, J. Comb. The-
ory Ser. B 97 (2007), 217–236, doi:10.1016/j.jctb.2006.03.007, https://doi.org/10.
1016/j.jctb.2006.03.007.

Accepted manuscript
24 Art Discrete Appl. Math.
[21] P. Potoˇ cnik and S. Wilson, Linking rings structures and tetravalent semisymmetric graphs,
Ars Math. Contemp. 7 (2014), 341–352, doi:10.26493/1855-3974.311.4a8, https://doi.
org/10.26493/1855-3974.311.4a8.
[22] P. Potoˇ cnik and S. Wilson, Linking rings structures and semisymmetric graphs: Cayley con-
structions, Eur. J. Comb. 51 (2016), 84–98, doi:10.1016/j.ejc.2015.05.004, https://doi.
org/10.1016/j.ejc.2015.05.004.
[23] P. Potoˇ cnik and S. Wilson, Linking rings structures and semisymmetric graphs: combinato-
rial constructions, Ars Math. Contemp. 15 (2018), 1–17, doi:10.26493/1855-3974.1007.3ec,
https://doi.org/10.26493/1855-3974.1007.3ec.
[24] P. Potoˇ cnik and S. Wilson, Recipes for edge-transitive tetravalent graphs, Art Discrete
Appl. Math. 3 (2020), #P1.08, doi:10.26493/2590-9770.1269.732, https://doi.org/
10.26493/2590-9770.1269.732.
[25] M. C. Sterns, Classification of edge-transitive propeller graphs, 2016,arXiv:1510.08491
[math.CO].
[26] P. Šparl, On the classification of quartic half-arc-transitive metacirculants, Discrete Math.
309 (2009), 2271–2283, doi:10.1016/j.disc.2008.05.006, https://doi.org/10.1016/
j.disc.2008.05.006.
[27] S. Wilson, Rose window graphs, Ars Math. Contemp.1 (2008), 7–19, doi:10.26493/1855-3974.
13.5bb,https://doi.org/10.26493/1855-3974.13.5bb.