ISSN 2590-9770
The Art of Discrete and Applied Mathematics 3 (2020) #P1.08
https://doi.org/10.26493/2590-9770.1269.732
(Also available at http://adam-journal.eu)
Recipes for edge-transitive tetravalent graphs*
Primož Potočnik†
University of Ljubljana, Faculty of Mathematics and Physics,
Jadranska 19, SI-1000 Ljubljana, Slovenia
Stephen E. Wilson‡
Department of Mathematics and Statistics, Northern Arizona University,
Box 5717, Flagstaff, AZ 86011, USA
Received 2 September 2018, accepted 1 October 2019, published online 17 August 2020
Abstract
This paper presents all constructions known to the authors which result in tetravalent
graphs whose symmetry groups are large enough to be transitive on the edges of the graph.
Keywords: Graph, automorphism group, symmetry.
Math. Subj. Class. (2020): 05C15, 05C10
1 The census
This paper is to accompany the Census of Edge-Transitive Tetravalent Graphs, available at
http://jan.ucc.nau.edu/∼swilson/C4FullSite/index.html,
which is a collection of all known edge-transitive graphs of valence 4 up to 512 vertices.
The Census contains information for each graph. This information includes parame-
ters such as group order, diameter, girth etc., all known constructions, relations to other
graphs in the Census (coverings, constructions, etc.), and interesting substructures such as
colorings, cycle structures, and dissections.
*The authors wish to express their gratitude for the efforts of the anonymous referee of this paper. What you
have read here is greatly improved over the previous version because of the referee’s thorough, careful examination
and insightful suggestions.
†This author gratefully acknowledges the support of the US Department of State and the Fulbright Scholar
Program who sponsored his visit to Northern Arizona University in spring 2004.
‡Corresponding author.
E-mail addresses: primoz.potocnik@fmf.uni-lj.si (Primož Potočnik), stephen.wilson@nau.edu (Stephen
E. Wilson)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Art Discrete Appl. Math. 3 (2020) #P1.08
We try to present most graphs as members of one or more parameterized families, and
one purpose of this paper is to gather together, here in one place, descriptions of each of
these families, to show how each is constructed, what the history of each is and how one
family is related to another. We also discuss in this paper the theory and techniques behind
computer searches leading to many entries in the Census.
We should point out that similar censi exist for edge transitive graphs of valence 3
[8, 10]. Unlike our census, these censi are complete in the sense that they contain all the
graphs up to a given order. The method used in these papers relies on the fact that in the
case of prime valence, the order of the automorphism group can be bounded by a linear
function of the order of the graph, making exhaustive computer searches possible – see [9]
for details.
Even though our census is not proved to be complete, it is complete in some segments.
In particular, the census contains all dart-transitive tetravalent graphs up to 512 vertices
(see [32, 36]) and all 12 -arc-transitive tetravalent graphs up to 512 vertices (see [33, 38]).
Therefore, if a graph is missing from our census, then it is semisymmetric (see Section 2).
2 Basic notions
A graph is an ordered pair Γ = (V, E), where V is an arbitrary set of things called vertices,
and E is a collection of subsets of V of size two; these are called edges. We let V(Γ) = V
and E(Γ) = E in this case. If e = {u, v} ∈ E , we say u is a neighbor of v, that u and v are
adjacent, and that u is incident with e and vice versa. A dart or directed edge is an ordered
pair (u, v) where {u, v} ∈ E . Let D(Γ) be the set of darts of Γ. The valence or degree of a
vertex v is the number of edges to which v belongs. A graph is regular provided that every
vertex has the same valence, and then we refer to that as the valence of the graph.
A digraph is an ordered pair ∆ = (V, E), where V is an arbitrary set of things called
vertices, and E is a collection of ordered pairs of distinct elements of V . We think of the
pair (u, v) as being an edge directed from u to v. An orientation is a digraph in which for
all u, v ∈ V , if (u, v) ∈ E then (v, u) /∈ E .
A symmetry, or automorphism, of a graph or a digraph Γ = (V, E) is a permutation of
V which preserves E . If v ∈ V(Γ) and σ is a symmetry of Γ, then we denote the image of
v under σ by vσ, and if ρ is also a symmetry of Γ, then the product σρ is a symmetry that
maps v to (vσ)ρ. Together with this product, the set of symmetries of Γ forms a group,
the symmetry group or automorphism group of Γ, denoted Aut(Γ). We are interested in
those graphs for which G = Aut(Γ) is big enough to be transitive on E . Such a graph is
called edge-transitive. Within the class of edge-transitive graphs of a given valence, there
are three varieties:
(1) A graph is symmetric or dart-transitive provided that G is transitive on D = D(Γ).
(2) A graph is 12 -arc-transitive provided that G is transitive on E and on V , but not
on D. A 12 -arc-transitive graph must have even valence [48]. The G-orbit of one
dart is then an orientation ∆ of Γ such that every vertex has k in-neighbours and k
out-neighbors, where 2k is the valence of Γ. The symmetry group Aut(∆) is then
transitive on vertices and on edges. We call such a ∆ a semitransitive orientation
and we say that a graph which has such an orientation is semitransitive [54].
(3) Finally, Γ is semisymmetric provided thatG is transitive on E but not on V (and hence
not onD). In this case, the graph must be bipartite, with each edge having one vertex
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 3
from each class. More generally, we say that a graph Γ is bi-transitive provided that
Γ is bipartite, and its group of color-preserving symmetries is transitive on edges
(and so on vertices of each color); a bi-transitive graph is thus either semisymmetric
or dart-transitive.
There is a fourth important kind of symmetricity that a tetravalent graph might have,
in which Aut(Γ) is transitive on vertices but has two orbits on edges. Graphs satisfying
this and certain other conditions are called LR structures. These are introduced and defined
in Section 18 but referred to in several places before that. These graphs, though not edge-
transitive themselves, can be used directly to construct semisymmetric graphs.
For σ ∈ Aut(Γ), if there is a vertex v ∈ V such that vσ is adjacent to v and vσ2 6= v we
call σ a shunt and then σ induces a directed cycle [v, vσ, vσ2, . . . , vσm], with vσm+1 = v,
called a consistent cycle. The remarkable theorem of Biggs and Conway [4, 30] says that if
Γ is dart-transitive and regular of degree d, then there are exactly d− 1 orbits of consistent
cycles. A later result [5] shows that a 12 -arc-transitive graph of degree 2e must have exactly
e orbits of consistent cycles. For tetravalent graphs, the dart-transitive ones have 3 orbits
of consistent cycles and the 12 -arc-transitive ones have two such orbits. An LR structure
might have 1 or 2 orbits of consistent cycles.
3 Computer generated lists of graphs
3.1 Semisymmetric graphs arising from amalgams of index (4, 4)
Let L and R be two finite groups intersecting in a common subgroup B and assume that no
non-trivial subgroup of B is normal in both L and R. Then the triple (L,B,R) is called
an amalgam. For example, if we let L = A4, the alternating group of degree 4, B ∼= C3,
viewed as a point-stabiliser in L, and R ∼= C12 containing B as a subgroup of index 4, then
(L,B,R) is an amalgam.
If G is a group that contains both L and R and is generated by them, then G is called a
completion of the amalgam. It is not too difficult to see that there exists a completion that
is universal in the sense that every other completion is isomorphic to a quotient thereof.
This universal completion is sometimes called the free product of L and R amalgamated
over B (usually denoted by L ∗B R) and can be constructed by merging together (disjoint)
presentations of L and R and adding relations that identify copies of the same element of
B in both L and R. For example, if the amalgam (L,B,R) is as above, then we can write
L = 〈x, y, b|x2, y2, [x, y], b3, xby, ybxy〉, R = 〈z|z12〉,
yielding
L ∗B R = 〈x, y, b, z|x2, y2, [x, y], b3, z12, xby, ybxy, z4 = b〉.
Completions of a given amalgam (L,B,R) up to a given order, say M , can be computed
using a LOWINDEXNORMALSUBGROUPS routine, developed by Firth and Holt [12] and
implemented in MAGMA [6].
Given a completion G of an amalgam (L,B,R), one can construct a bipartite graph,
called the graph of the completion, with white and black vertices being the cosets of L and
R in G, respectively, and two cosets Lg and Rh adjacent whenever they intersect. Note
that white (black) vertices are of valence [L : B] ([R : B], respectively). In particular, if B
is of index 4 in both L and R, then the graph is tetravalent. We shall say in this case that
the amalgam is of index (4, 4).
4 Art Discrete Appl. Math. 3 (2020) #P1.08
The group G acts by right multiplication faithfully as an edge-transitive group of au-
tomorphisms of the graph and so the graph of a completion of an amalgam always admits
an edge- but not vertex-transitive group of automorphisms, and so the graph is bi-transitive
(and thus either dart-transitive or semisymmetric). This now gives us a good strategy for
constructing tetravalent semisymmetric graphs of order at most M : Choose your favorite
amalgams (L,B,R) of index (4, 4), find their completions up to order 2M |B| and con-
struct the corresponding graphs.
We have done this for several amalgams of index (4, 4) and the resulting graphs ap-
pear in the census under the name SS. The graph SS[n, i] is the i-th graph in the list of
semisymmetric graphs of order n. These graphs are available in magma code at [33].
3.2 Dart-transitive graphs from amalgams
If Γ is a tetravalent dart-transitive graph, then its subdivision, obtained from Γ by inserting
a vertex of valence 2 on each edge, is edge-transitive but not vertex-transitive. This process
is reversible, by removing vertices of degree 2 in a bi-transitive graph of valence (4, 2) one
obtains a tetravalent dart-transitive graph.
In the spirit of the previous section, each such graph can be obtained from an amalgam
of index (4, 2). Amalgams of index (4, 2) were fully classified in [11, 34, 53], however,
unlike in the case of amalgams of index (3, 2), giving rise to cubic dart-transitive graphs, the
number of these amalgams is infinite. This fact, together with existence of relatively small
tetravalent dart-transitive graphs with very large automorphism groups (see Section 14)
made the straightforward approach used in [9, 8] in the case of cubic graphs impossible in
the case of valence 4. This obstacle was finally overcome in [37] and now a complete list
of dart-transitive tetravalent graphs of order up 640 is described in [36] and available in
magma code at [33]. We use AT[n, i] for these graphs to indicate the i-th graph of order n
in this magma file.
3.3 Semitransitive graphs from universal groups
Every semitransitive tetravalent graph arises from an infinite 4-valent tree T4 and a group
G acting on T4 semitransitively and having a finite stabiliser by quotienting out a normal
semiregular subgroup of G. All such groups G were determined in [27]. This result in
principle enables the same approach as used in the case of tetravalent dart-transitive graphs,
and indeed, by overcoming the issue of semitransitive graphs with large automorphism
groups (see [45]), a complete list of semitransitive tetravalent graphs (and in particular 12 -
arc-transitive graphs) of order up to 1000 was obtained in [38] and is available at [33].
We include the 12 -arc-transitive graphs from this list in our census with the designation
HT[n, i].
We now begin to show the notation and details of each construction used for graphs in
the Census.
4 Wreaths, unworthy graphs
A general Wreath graph, denoted W(n, k), has n bunches of k vertices each, arranged in a
circle; every vertex of bunch i is adjacent to every vertex in bunches i+ 1 and i− 1. More
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 5
precisely, its vertex set is Zn × Zk; edges are all pairs of the form {(i, r), (i+ 1, s)}. The
graph W(n, k) is regular of degree 2k. If n = 4, then W(n, k) is isomorphic to K2k,2k
and its symmetry group is the semidirect product of S2k × S2k with Z2. If n 6= 4, then
its symmetry group is the semidirect product of Snk with Dn; this group is often called the
wreath product of Dn over Sk.
Those of degree 4 are the graphs W(n, 2). Here, for simplicity, we can also notate
the vertex (i, 0) as Ai, and (i, 1) as Bi for i ∈ Zn, with edges then being of the forms
{Ai, Ai+1}, {Ai, Bi+1}, {Bi, Ai+1}, {Bi, Bi+1}. For example, Figure 1 shows W (7, 2).
Figure 1: W (7, 2)
A wreath graph W(n, 2) has dihedral symmetries ρ and µ, where ρ sends (i, j) to
(i + 1, j) and µ sends (i, j) to (−i, j). The important aspect of this graph is that for each
i ∈ Zn, there is a symmetry σi, called a “local” symmetry, which interchanges (i, 0) with
(i, 1) and leaves every other vertex fixed. Notice that ρ acts as a shunt for a cycle of length
n, and ρσ0 acts as a shunt for a cycle of length 2n. The third orbit of consistent cycles
are those of the form [Ai, Ai+1, Bi, Bi+1] The symmetry ρµσ0 is a shunt for the cycle
[A0, B0, A1, B1] in this orbit.
Since every σi for i 6= 0 is in the stabilizer of A0, we see that vertex stabilizers in these
graphs can be arbitrarily large. In fact, the order of the vertex-stabilizer grows exponentially
with respect to the order of the graph.
A graph Γ is unworthy provided that some two of its vertices have exactly the same
neighbors. The graph W (n, 2) is unworthy because for each i, the vertices Ai and Bi have
the same neighbors. The symmetry groups of vertex-transitive unworthy graphs tend to be
large due to the symmetries that fix all but two vertices sharing the same neighborhood.
The paper [39] shows that there are only two kinds of tetravalent edge-transitive graphs
which are unworthy. One is the dart-transitive W(n, 2) graphs. The other is the “sub-
divided double” of a dart-transitive graph; this is a semisymmetric graph given by this
construction:
Construction 4.1. Suppose that Λ is a tetravalent graph. We construct a bipartite graph
Γ = SDD(Λ) in the following way. The white vertices of Γ correspond to edges of Λ. The
black vertices correspond two-to-one to vertices of Λ; for each v ∈ V(Λ), there are two
vertices v0, v1 in V(Γ). An edge of Γ joins each e to each vi where v is a vertex of e in Λ.
6 Art Discrete Appl. Math. 3 (2020) #P1.08
The Folkman graph on 20 vertices [13] is constructible as SDD(K5). It is clear that
SDD(Λ) is tetravalent, and that if Λ is dart-transitive, then SDD(Λ) is edge-transitive.
The paper [39] shows that any unworthy tetravalent edge-transitive graph is isomorphic
to some W(n, 2) if it is dart-transitive, and to SDD(Λ) for some dart-transitive tetravalent
Λ if it is semisymmetric. There are no tetravalent unworthy 12 -arc-transitive graphs.
5 Circulants
In general, the circulant graph Cn(S) is the Cayley graph for Zn with generating set S.
Here S must be a subset of Zn which does not include 0, but does, for each x ∈ S, include
−x as well. Explicitly, vertices are 0, 1, 2, . . . , n − 1, considered as elements of Zn, and
two numbers i, j are adjacent if their difference is in S. Thus the edge set consists of all
pairs {i, i + s} for i ∈ Zn, and s ∈ S. If S = {±a1,±a2, . . . }, we usually abbreviate
the name of each graph Cn(S) as Cn(a1, a2, . . . ). The numbers ai are called jumps and
the set of edges of the form {j, j + ai} for a fixed i is called a jumpset. Figure 2 shows an
example, the graph C10(1, 3).
1
2
3
4
56
7
8
9
0
Figure 2: C10(1, 3)
For general n, if S is a subgroup of the group Z∗n of units mod n, then Cn(S) is dart-
transitive, though it may be so in many other circumstances as well. In the tetravalent case,
there are two possibilities for an edge-transitive circulant:
Theorem 5.1. If Γ is a tetravalent edge-transitive circulant graph with n vertices, then it
is dart-transitive and either:
(1) Γ is isomorphic to Cn(1, a) for some a such that a2 ≡ ±1 (mod n), or
(2) n is even, n = 2m, and Γ is isomorphic to C2m(1,m+ 1).
Proof. Note first that every edge-transitive circulant Cn(a, b) is dart-transitive, due to an
automorphism which maps a vertex i to the vertex a − i mod n, and thus inverts the edge
{0, a}.
In (1), the dihedral group Dn acts transitively on darts of each of the two jumpsets, and
because a2 ≡ ±1 (mod n), multiplication by a mod n induces a symmetry of the graph
which interchanges the two jumpsets.
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 7
On the other hand, in (2), C2m(1,m+1) is isomorphic to the unworthy graph W(m, 2),
with i and i+m playing the roles ofAi andBi. Thus, the sufficiency of (1) or (2) for edge-
transitivity is clear.
The necessity can be deduced either from a complete classification of dart-transitive
circulants of arbitrary valence proved in [19] and [23] or by a careful examination of short
cycles in dart-transitive circulants.
6 Toroidal graphs
The tessellation of the plane into squares is known by its Schläfli symbol, {4, 4}. Let T be
the group of translations of the plane that preserve the tessellation. Then T is isomorphic
to Z × Z and acts regularly on the vertices of the tessellation. If U is a subgroup of finite
index in T , let M = {4, 4}/U be the quotient space formed from {4, 4} by identifying
points if they are in the same orbit under U . The result is a finite map of type {4, 4} on the
torus, and the paper [17] shows that, even in a more general setting, every such map arises
in this way. We will call U the kernel ofM. A symmetry α of {4, 4} acts as a symmetry
ofM if and only if α normalizes U . Thus every suchM has its symmetry group Aut(M)
transitive on vertices, on horizontal edges, on vertical edges; further for each edge e of
M, there is a symmetry reversing the edge (and acting as a 180◦ rotation about its center).
Thus, Aut(M) is transitive on the edges ofM (and so must be dart-transitive) if and only
if U is normalized by some symmetry interchanging the horizontal and vertical parallel
classes. This must be a 90◦ rotation or a reflection about some axis at a 45◦ angle to the
axes.
We will use the symbols {4, 4}b,c, {4, 4}[b,c], {4, 4}<b,c>, intoduced below, to stand
for certain maps on the torus as well as their skeletons. As shown in [50], this can happen
in three different ways:
(1) {4, 4}b,c: For this graph and map, defined for b ≥ c ≥ 0, U is the group generated by
the translations (b, c) and (−c, b). These are the well-known rotary maps. Because
this U is normalized by 90◦ rotations, the map admits these rotations as symmetries.
{4, 4}b,c has D = b2 + c2 vertices, D faces and 2D edges. Figure 3 shows the case
when b = 3, c = 2.
1
1 2
2
3 4
4 5 6
5
87
7 8
9
9 10 11 12 13
13
1 2 3
4 5 6 7 8
9 10 11 12 13=
Figure 3: The map {4, 4}3,2
(2) {4, 4}<b,c>: This graph and map, defined for b − 1 > c ≥ 0, uses for U the group
generated by the translations (b, c) and (c, b). Because this U is normalized by re-
8 Art Discrete Appl. Math. 3 (2020) #P1.08
flections whose axes are at 45◦ to the axes, the map admits these reflections as sym-
metries. It has E = b2− c2 vertices, E faces and 2E edges. Figure 4 shows the map
{4, 4}<3,1>.
1
1
8
2
2
6
3
3
3
7
4 65
=
1
1 2 3
87
4 65
Figure 4: The map {4, 4}<3,1>
Notice that we exclude the case b = c + 1. The map {4, 4}<c+1,c> exists, but its
skeleton has parallel edges.
(3) {4, 4}[b,c]: For this graph and map, defined for b ≥ c ≥ 0, U is the group generated
by the translations (b, b) and (−c, c). Because this U is normalized by reflections
whose axes are at 45◦ to the axes, the map admits these reflections as symmetries. It
is defined only for b ≥ c > 1. It has F = 2bc vertices, F faces and 2F edges.
1
1 2 3 4 5
5 6
6 7 8 9
9 10 11 12
12
1 2 3 4 6 7
8 129 10 11
5
Figure 5: The map {4, 4}[3,2]
If c = 1, then the map {4, 4}[b,c] exists, but, again, its skeleton has multiple edges
and so is not a simple graph.
It is interesting to note that {4, 4}b+c,b−c is a double cover of {4, 4}b,c, while {4, 4}[b+c,b−c]
is a double cover of {4, 4}<b,c> and {4, 4}<b+c,b−c> is a double cover of {4, 4}[b,c]. In
each case, the covering is 2-fold because the kernel of the covering map has index 2 in the
kernel of the covered map.
Because {4, 4}b,0 is isomorphic to {4, 4}<b,0>, this map is reflexible. Because {4, 4}b,b
is isomorphic to {4, 4}[b,b], this map is also reflexible. All other {4, 4}b,c are chiral: i.e.,
rotary but not reflexible.
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 9
Now, every U of finite index in Z2 can be expressed in the form U = 〈(d, e), (f, g)〉,
where (d, e) and (f, g) are linearly independent. In particular, we claim that U can also
be expressed in the form U = 〈(r, 0), (s, t)〉, where t = GCD(e, g). To see that, let
e = e′t, g = g′t, and let m and n be Bezout multipliers, so that me′ + ng′ = 1. Now let
s = md+ nf and r = g′d− e′f . Then 〈(r, 0), (s, t)〉 has a fundamental region which is a
rectangle r squares wide, t squares high, with the left and right edges identified directly, and
the bottom edges identified with the top after a shift s squares to the right, as in Figure 6.
t
s
r
Figure 6: A standard form for maps of type {4, 4}
In the special case in which b and c are relatively prime, we have t = 1, and this forces
the graph to be circulant; in fact, the circulant graph Cr(1, s). Here, s2 ≡ −1 for {4, 4}b,c,
and s2 ≡ 1 for both {4, 4}<b,c> and {4, 4}[b,c]. On the other hand, every tetravalent
circulant graph is toroidal or has an embedding on the Klein bottle. More precisely, if
a2 ≡ −1(mod n), then Cn(1, a) ∼= {4, 4}b,c for some b, c. If a2 ≡ 1(mod n), then
Cn(1, a) ∼= {4, 4}<b,c> or {4, 4}[b,c] for some b, c. Of the graphs C2m(1,m + 1) ∼=
W(m, 2), if m is even then it is {4, 4}[m2 ,2]. On the other hand, if m is odd, it has an
embedding on the Klein bottle, though that embedding is not edge-transitive [55].
7 Depleted wreaths
The general Depleted Wreath graph DW(n, k) is formed from W(n, k) by removing the
edges of k disjoint n-cycles, each of these cycles containing one vertex from each of the k
bunches. More precisely, its vertex set is Zn × Zk. Its edge set is the set of all pairs of the
form {(i, r), (i+1, s)} for i ∈ Zn and r, s ∈ Zk, r 6= s. Its vertices are of degree 2(k−1).
It is tetravalent when k = 3. Figure 7 shows part of DW(n, 3).
It is not hard to see that if n > 4, then the group of symmetries of this graph acts
imprimmitively in two different ways. One system of blocks is the collection of sets of the
form Ri = {(i, r)|r ∈ Z3}, defined for each i ∈ Zn. Another system is the collection of
sets of the form Qr = {(i, r)|i ∈ Zn}, defined for each r ∈ Z3. Then for n > 4, the group
of symmetries of DW(n, 3) is isomorphic to S3 ×Dn.
From this, we can see that the symmetry group has an element of order 3n exactly when
3 does not divide n. More precisely, if n ≡ 1 (mod 3) then DW(n, 3) ∼= C3n(1, n+ 1) and
if n ≡ 2 (mod 3) then DW(n, 3) ∼= C3n(1, n− 1); in the remaining case, n ≡ 0 (mod 3),
DW(n, 3) is not a circulant.
A primary result in [39] is that, with one exception on 14 vertices, any edge-transitive
tetravalent graph in which each edge belongs to at least two 4-cycles is toroidal. Because
every edge of DW(n, 3) belongs to two 4-cycles of the form (i−1, x)−(i, y)−(i+1, x)−
10 Art Discrete Appl. Math. 3 (2020) #P1.08
Figure 7: Part of DW(n, 3)
(i, z)−(i−1, x), where {x, y, z} = {0, 1, 2}, the Depleted Wreaths are also toroidal. If n is
even, then DW(n, 3) ∼= {4, 4}[n2 ,3], while if n is odd, then DW(n, 3)
∼= {4, 4}<n+32 ,n−32 >.
8 Spidergraphs
The Power Spidergraph PS(k, n; r) is defined for k ≥ 3, n ≥ 5, and r such that rk ≡ ±1
(mod n), but r 6≡ ±1 (mod n). Its vertex set is Zk × Zn, and vertex (i, j) is connected
by edges to vertices (i + 1, j ± ri). It may happen that this graph is not connected; if
so, we re-assign the name to the connected component containing (0, 0). Directing each
edge from (i, j) to (i + 1, j ± ri) gives a semitransitive orientation, and so the resulting
graph is always semitransitive. (In this presentation, we wish to not include toroidal graphs
as spidergraphs. This is what moves us to require r 6≡ ±1 (mod n) and the consequent
n ≥ 5.)
Closely related is the Mutant Power Spidergraph MPS(k, n; r). It is defined for k ≥ 3,
n even and n ≥ 8, and r such that rk ≡ ±1 (mod n), but r 6≡ ±1 (mod n). Its vertex set is
Zk ×Zn. For 0 ≤ i < k− 1, vertex (i, j) is connected by edges to vertices (i+ 1, j ± ri);
vertex (k−1, j) is connected to (0, j±rk−1+n/2). Marušič [25] and Šparl [51] have shown
that every tetravalent tightly-attached graph is isomorphic to some PS or MPS graph, and
that the graph is 12 -arc-transitive in all but a few cases: if r
2 ≡ ±1 (mod n), then the graph
is dart-transitive. The very special graph Σ = PS(3, 7; 2) is dart-transitive. If m is an
integer not divisible by 7 and r is the unique solution mod n = 7m to r ≡ 5 (mod 7),
r ≡ 1 (mod m), then PS(6, n; r) (which is a covering of Σ) is dart-transitive.
The paper [51] defines and notates these graphs in ways which differ from this paper,
and the difference is worthy of note. If m,n, r, t are integers satisfying (1) m,n are even
and at least 4, (2) rm ≡ 1 (mod n) and (3) s = 1+r+r2 + . . . rm−1 +2t is equivalent to 0
(mod n), then [51] defines the graph Xe(m,n; r, t) (“e” stands for “even”) to have vertices
[i, j] with i ∈ Zm and j ∈ Zn and edges from [i, j] to [i + 1, j] and [i + 1, j + ri] when
0 ≤ i < m− 1, while [m− 1, j] is connected to [0, j + t] and [0, j + rm−1 + t].
The argument in [54] shows that if (1), (2) and (3) hold, then rm ≡ 1 (mod 2n). Then
it is not hard to see that if the integer s is equivalent to 0 mod 2n, then Xe(m,n; r, t)
is isomorphic to PS(m, 2n; r); if s is equivalent to n mod 2n, then it is isomorphic to
MPS(m, 2n; r).
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 11
9 Attebery graphs
The following quite general construction is due to Casey Attebery [3]. We will first define
the digraph Att[A, T, k; a, b] and then define the graph Att(A, T, k; a, b) to be the under-
lying graph of the digraph. The parameters are: an abelian group A, an automorphism T of
A, an integer k at least 3, and two elements a and b of A. Let c = b− a and define ai, bi, ci
to be aT i, bT i, cT i respectively for i = 0, 1, 2, . . . , k. We require that:
(1) {ak, bk} = {a, b},
(2) A is generated by c0, c1, c2, . . . , ck−1 and Σk−1i=0 ai; and
(3) a+ b is in the kernel of the endomorphism T ∗ = Σk−1i=0 T
i.
Then the vertex set of the digraph Att[A, T, k; a, b] and of the graph Att(A, T, k; a, b) is
defined to be A × Zk. In the digraph, edges lead from each (x, i) to (x + ai, i + 1) and
(x+ bi, i+ 1). Then the digraph is a semitransitive orientation of the graph [3]. The graph
is thus semitransitive, and it is often, but not always, 12 -arc-transitive.
Not all Attebery graphs are implemented in the Census. There are four special cases
which are:
1. If A = Zn and T is multiplication by r, the Attebery graph is just PS(k, n; r), and
thus the Attebery graphs are generalizations of the spidergraphs.
2. The graph called C±1(p; st, s) in [14]. This is an Attebery graph with A = Zsp, k =
st, T : (a1, a2, . . . , as)→ (a2, a3, . . . , as, a1),−b = a = (1, 0, 0, . . . , 0).
3. The graph called C±e(p; 2st, s) in [14] with e2 ≡ −1 (mod p). This is an Attebery
graph with A = Zsp, k = 2st, T : (a1, a2, . . . , as) 7→ (ea2, ea3, . . . , eas, ea1),−b =
a = (1, 0, 0, . . . , 0).
4. Define AMC(k, n,M) to be Att(A, T, k; a, b) where A is Zn × Zn, M is a 2 × 2
matrix over Zn satisfying Mk = ±I , T is multiplication by M , and a = (1, 0), b =
(−1, 0).
The second and third of these are generalized to the graph CPM(n, s, t, r), defined in
section 15 of this paper.
It is intriguing that even though the matrix
M =
[
1 −4
4 1
]
does not satisfy the condition M4 = ±I , the graph AMC(4, 12,M) is nevertheless edge-
transitive, and in fact semisymmetric. Even more striking is that so far we have no other
construction for this graph.
10 The separated box product
Suppose that ∆1 and ∆2 are digraphs in which every vertex has in- and out-valence 2. We
allow ∆1 and ∆2 to be non-simple.
We form the separated box product ∆1#∆2 (first defined in [41]) as the underlying
graph of the orientation whose vertex set is V(∆1) × V(∆2) × Z2, and whose edge set
contains two types of edges: “horizontal” edges join (a, x, 0) → (b, x, 1), and “vertical”
edges (b, x, 1)→ (b, y, 0), where a→ b in ∆1 and x→ y in ∆2.
12 Art Discrete Appl. Math. 3 (2020) #P1.08
An orientation is reversible provided that it is isomorphic to its reversal. As shown in
Theorem 5.1 of [41], there are several useful cases of this construction:
• When ∆1 = ∆2 and ∆1 is reversible, then ∆1#∆2 is dart-transitive.
• When ∆1 = ∆2 and ∆1 is not reversible, ∆1#∆2 has a semitransitive orientation
and so might be dart-transitive or 12 -transitive.
• When ∆1 is not isomorphic to ∆2 or its reverse but both are reversible, then ∆1#∆2
has an LR structure.
• When ∆1 is not isomorphic to ∆2 but is isomorphic to the reverse of ∆2, then
∆1#∆2 is at least bi-transitive and is semisymmetric in all known cases.
In the Census, we use for ∆1 and ∆2 directed graphs from the census of 2-valent dart-
transitive digraphs [38, 33] with notation ATD[n, i] for the ith digraph of order n from that
census. We also allow the “sausage digraph” DCycn: an n-cycle with each edge replaced
by two directed edges, one in each direction. See [41] for more details.
11 Rose windows
The Rose Window graph Rn(a, r) has 2n vertices: Ai, Bi for i ∈ 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 8 shows R12(2, 5).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Figure 8: R12(2, 5)
We will soon mention these graphs as examples of bicirculant graphs, and more gener-
ally later as examples of polycirculant graphs.
The paper [20] shows that every edge-transitive Rn(a, r) is dart-transitive and is iso-
morphic to one of these:
a. Rn(2, 1). (This graph is isomorphic to W(n, 2).)
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 13
b. R2m(m+ 2,m+ 1).
c. R12k(3k ± 2, 3k ∓ 1).
d. R2m(2b, r), where b2 ≡ ±1 (mod m), r is odd and r ≡ 1 (mod m).
12 Bicirculants
A graph Γ is bicirculant provided that it has a symmetry ρ which acts on V as two cycles of
the same length. A rose window graph is bicirculant, as the symmetry sending Ai to Ai+1
and Bi to Bi+1 is the required ρ.
The paper [21] classifies all edge-transitive tetravalent bicirculant graphs. Besides the
Rose Window graphs there is one other class of graphs, called BC4 in that paper, and called
BC here and in the Census. The graph BCn(a, b, c, d) has 2n vertices: Ai, Bi for i ∈ Zn.
The edges are all pairs of the form {Ai, Bi+e} for i ∈ Zn, e ∈ {a, b, c, d}. It is easy to
see that any such graph is isomorphic to one of the form BCn(0, a, b, c) where a divides n.
The edge-transitive graphs in this class consist of three sporadic examples and three infinite
families. The sporadics are:
BC7(0, 1, 2, 4), BC13(0, 1, 3, 9), BC14(0, 1, 4, 6)
Of the three infinite families of graphs BCn(0, a, b, c), there are two in which we can
choose a = 1, and a third, less easy to describe, in which none of the parameters is rela-
tively prime to n:
(I) BCn(0, 1,m+ 1,m2 +m+ 1), where (m+ 1)(m2 + 1) = 0 (mod n)
(II) BCn(0, 1, d, 1− d), where 2d(1− d) = 0 (mod n)
(III) BCkrst(0, r, rs′s+ st, rt′t+ st+ rst), where
(1) r, s, t are all integers greater than 1,
(2) s, t are odd,
(3) r, s, t are relatively prime in pairs,
(4) k ∈ {1, 2},
(5) if k = 2, then r is even,
(6) s′ is an inverse of s mod krt, and t′ is an inverse of t mod krs.
13 Semiregular symmetries and their diagrams
A symmetry σ is semiregular provided that it acts on the |V| = kn vertices as k cycles
of length n. We can visually represent such a graph and symmetry with a diagram. This
is a graph-like object, with labels. Each “node” represents one orbit under σ. If σ =
(u0, u1, . . . , un−1)(v0, v1, . . . , vn−1) . . . (w0, w1, . . . , wn−1) and there is an edge from u0
to va, then there is an edge from each ui to va+i (indices computed modulo n). This
matching between u′is and v
′
is is represented in the diagram by a directed edge from node
u to node v with label a (or one from v to u with label −a). If a = 0, then the label a and
the direction of the edge in the diagram can be omitted.
If there is an edge from u0 to ub (and thus one from each ui to ui+b), we represent this
by a loop at u with label b. In the special case in which n is even and b = n2 , there are only
14 Art Discrete Appl. Math. 3 (2020) #P1.08
n
2 edges in the orbit and we represent them with a semi-edge at u. This convention makes
the valence of u in the diagram the same as the valences of all of the ui’s in the graph.
For example, the graph in Figure 9 has the symmetry
ϕ = (u0u1u2u3u4u5)(v0v1v2v3v4v5)(w0w1w2w3w4w5).
u0
u1
u2
u3
u4
u5
v0
v1
v2
v3
v4
v5
w0
w1
w2
w3
w4
w5
Figure 9: A trivalent graph having a semiregular symmetry
1
u v w2
Mod 6
Figure 10: The diagram of the semiregular symmetry ϕ
The corresponding diagram is shown in Figure 10. The label “Mod 6” in this diagram
informs the reader that all numbers which label edges in the diagram are to be considered
as elements of Z6.
It should be pointed out that what we were describing above is simply the notion of a
quotient of a graph (as defined, for example, in [24]) by the cyclic group generated by the
semiregular element σ, and the diagram which we obtain is the voltage graph describing
the graph Γ.
Further, the graph can be reconstructed from the diagram. This is simply the ordinary
voltage graph construction with voltage group Zn and voltages of the darts as shown with
the integers drawn at the darts in the diagram (if neither the dart nor its inverse dart have
any integers drawn next to them, then the corresponding voltage is assumed to be 0).
In constructions, we often refer to the generic form of the diagram, in which the modu-
lus is unspecified and parameter names are used as labels for some edges, as in Figure 11.
As an example, consider the bicirculant graphs Rn(a, r) and BCn(0, a, b, c), which can
be represented by the diagrams shown in Figure 12.
In the following, we use diagrams to define many families of graphs.
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 15
a
u v wb
Figure 11: A generic diagram
1 r
a
A B
a
A Bb
c
Figure 12: Diagrams of graphs
13.1 Propellors
A B Ca
b
c d
Figure 13: Diagram for the graph Prn(a, b, c, d)
A Propellor Graph is a graph with the diagram shown in Figure 13. This means that
the graph has 3n vertices:Ai, Bi, Ci for i ∈ Zn. There are 6 kinds of edges:
Tip: Ai −Ai+a
Ci − Ci+d
Flat: Ai −Bi
Bi − Ci
Blade: Bi −Ai+b
Bi − Ci+c
Propellor graphs have been investigated by Matthew Sterns. He conjectures in [46] that
the edge-transitive propellor graphs are isomorphic to
I Prn(1, 2d, 2, d), where n is even and d2 ≡ ±1 (mod n)
II Prn(1, b, b+ 4, 2b+ 3), where n is divisible by 4, 8b+ 16 ≡ 0 (mod n), and b ≡ 1
(mod 4).
16 Art Discrete Appl. Math. 3 (2020) #P1.08
III These five sporadic examples:
Pr5(1, 1, 2, 2),Pr10(1, 1, 2, 2), Pr10(1, 4, 3, 2), Pr10(1, 1, 3, 3), Pr10(2, 3, 1, 4).
Notice first that in every case except the last of the sporadic cases, the A-tip edges form
a single cycle. The first of the infinite families consists of the 2-weaving graphs: those
graphs in which some symmetry of the graphs sends this cycle to a cycle of the form AB
AB AB. . . The second class consists of 4-weaving graphs: those in which some symmetry
sends the A-tip cycle to a cycle of the form ABCB ABCB AB. . . There is also a class of
5-weaving graphs in which some image of the tip cycle is of the form AABCB AABCB
AAB. . ., but the requirements for this class force n to divide 10, resulting in the first four
of the sporadic cases. This leaves the last sporadic graph as something of a mystery.
A more recent paper [47] proves that if a or d is relatively prime to n, then the conjec-
ture holds.
13.2 Metacirculants
In [29], Marušič and Šparl considered tetravalent graphs which are properly called weak
metacirculant, though we will simply refer to them as metacirculant in this paper. A graph
is metacirculant provided that it has a symmetry ρ which acts on the mn vertices as m
cycles of length n and another symmetry σ which normalizes 〈ρ〉 and permutes the m ρ-
orbits in a cycle of length m. That paper considers four classes of 12 -transitive tetravalent
metacirculant graphs. The four classes together include all such graphs.
The Type I graphs are the Power Spidergraphs PS(m,n; r) and MPS(m,n; r). Papers
[25, 29, 51, 54] completely determine which of these are 12 -transitive and which are dart-
transitive. The Type II graphs are called Y there and will be called MSY here and in the
census. These also have been classified, in unpublished work [2]. See Section 13.2.1 below.
The graphs of Type III we will call MC3 in this census. They have been studied with
a few results. See Section 13.2.3. While the general Type IV graphs are very unruly,
there are some results known; for instance, the paper [1] classifies Type IV 12 -arc-transitive
metacirculants of girth 4. A subclass of Type IV graphs, called Z in [29] and MSZ in the
Census, have received some concentrated study. See Section 13.2.2 for a description of the
graph.
13.2.1 MSY
The graph MSY(m,n; r, t) has the diagram shown in Figure 14.
More precisely, its vertex set is Zm × Zn, with two kinds of edges:
(1) (i, j)− (i, j + ri) for all i and j, and
(2) (i, j)− (i+ 1, j) for 0 ≤ i < m− 1 and (m− 1, j)− (0, j + t) for all j.
The graph is seen to be metacirculant (with ρ sending (i, j) to (i, j + 1) and σ sending
(i, j) to (i + 1, rj) for i 6= m − 1 and sending (m − 1, j) to (0, rj + t)) if and only if
rm = 1 and rt = t. Here, all equalities are equivalences mod n. The paper [52] proves
that MSY(m,n; r, t) is metacirculant and 12 -transitive if and only if it is isomorphic to one
in which:
(1) n = dm for some integer d at least 3,
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 17
3
210
-1
5
4
1
r-1
r
r2
r3
r4
r5
t
Figure 14: Diagram for the graph MSY(m,n; r, t)
(2) rm = 1,
(3) r2 6= ±1,
(4) m(r − 1) = t(r − 1) = (r − 1)2 = 0,
(5) 〈m〉 = 〈t〉 in Zn,
(6) there is a unique c in Zd satifying cm = t and ct = m,
(7) there is a unique k in Zd satifying kt = −km = r − 1, and
(8) either m 6= 4 or t 6= 2 + 2r.
The paper [2] shows that MSY(m,n; r, t) is metacirculant and edge-transitive if and
only if it is isomorphic to one in which rm = 1, rt = t and one of three things happens:
(1) m = GCD(t, n) (then t = sm, n = n′m and GCD(n′, s) = 1);
(2) r ≡ 1 (mod m) and so r = km+ 1 for some k;
(3) st = m;
(4) kt = −km.
or
(1) m = GCD(t, n) (then t = sm, n = n′m and GCD(n′, s) = 1);
(2) r ≡ 1 (mod m) and so r = km+ 1 for some k;
(3) st = −m;
(4) kt = km.
or [m,n, r, t] is one of these four sporadic examples:
[5, 11, 5, 0], [5, 22, 5, 11], [5, 33, 16, 0], [5, 66, 31, 33].
13.2.2 MSZ
The graph MSZ(m,n; k, r) has a diagram isomorphic to the circulant graph Cm(1, k). It
has vertex set Zm × Zn. The vertex (i, j) is adjacent to (i+ 1, j) and to (i+ k, j + ri).
18 Art Discrete Appl. Math. 3 (2020) #P1.08
13.2.3 MC3
The diagram for this family has an even number of nodes arranged in a circle. With c = 1
or 2, each node is joined by an edge to nodes that are c steps away in the circle. Each node
is joined to the node opposite by two edges.
We call the graph Γ = MC3(m,n, a, b, r, t, c); here, m must be even, c is 1 or 2, and
a, b, r, t are numbers mod n such that rt = t, rm = 1, and {a+t, b+t} = {−arm2 ,−brm2 }.
The vertex set is Zm × Zn. One kind of edge connects each (i, j) to (i + c, j) for i =
0, 1, 2, . . . ,m− c− 1, and (i, j) to (i + c, j + t) for i ∈ {m− c,m− 1}. A second kind
of edge joins each (i, j) to (i+ m2 , j + ar
i) and (i+ m2 , j + br
i).
Because it has been shown that each such graph which is 12 -arc-transitive is also a
PS,MPS,MSY or MSZ, little attention has been given to it. However, many MC3’s are
dart-transitive and many are LR structures (see section 18, where we will refer to the two
kinds of edges as green and red). Each of the following families is such an example:
1. m is divisible by 4, n is divisible by 2, r2 = ±1, a = 1, b = −1, t = 0,
2. m is not divisible by 4, n is divisible by 4, r2 = 1, a = 1, b = −1, t = n2 ,
3. n is divisible by 4, r2 = 1, a = 1, b = n/2− 1, t = n/2.
These were found and proved to be LR strucures (see section 18) by Ben Lantz [22],
and there are LR examples not covered by these families. Further, many of the MC3 graphs
are dart-transitive. There are many open questions about this family.
13.3 Other diagrams
A number of other diagrams have been found to give what appears to be an infinite number
of examples of edge-transitive graphs. The first of these is the Long Propellor, LoPrn(a, b, c, d, e),
shown in Figure 15.
ba
A B
ec
d
C D
Figure 15: Diagram for the graph LoPrn(a, b, c, d, e)
Next is the Woolly Hat, WHn(a, b, c, d), shown in Figure 16. This diagram appears to
give no edge-transitive covers, but it does yield a family of LR structures (see Section 18),
as yet unclassified.
The Kitten Eye, KEn(a, b, c, d, e), shown in Figure 17, has dart-transitive covers.
The Curtain, Curtainn(a, b, c, d, e), shown in Figure 18, has both dart-trasitive and LR
covers.
14 Praeger-Xu constructions
The graph called C(2, n, k) in [44] is also described in [14] in two different ways. In this
Census, we will name the graph PX(n, k). In order to describe the graph, we need some
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 19
A
B C
a
c
d
b
Figure 16: Diagram for the graph WHn(a, b, c, d, e)
A
B
C
a
c
db
D e
Figure 17: Diagram for the graph KEn(a, b, c, d, e)
notation about bit strings. A bit string of length k is the concatenation of k symbols, each
of them a ’0’ or a ’1’. For example x = 0011011110 is a bit string of length 10. If x is
a bit string of length k, then xi is its i-th entry, and xi is the string identical to x in every
place except the i-th. Also 1x is the string of length k + 1 formed from x by placing a ’1’
in front; similar definitions hold for the (k + 1)-strings 0x, x0, x1. Finally, the string x̄ is
the reversal of x.
The vertices of the graph PX(n, k) are ordered pairs of the form (j, x), where j ∈ Zn
and x is a bit string of length k. Edges are all pairs of the form {(i, 0x), (i+1, x0)}, {(i, 0x), (i+
1, x1)}, {(i, 1x), (i+1, x0)}, {(i, 1x), (i+1, x1)}, where x is any bit string of length k−1.
We first wish to consider some symmetries of this graph. First we note ρ and µ given
by (j, x)ρ = (j + 1, x) and (j, x)µ = (−j, x̄) These are clearly symmetries of the graph
and act on it as Dr.
For b ∈ Zn, we define the symmetry τb to be the permutation which interchanges
(b − i, x) with (b − i, xi) for i = 1, 2, 3, . . . , k and leaves all other vertices fixed. If
n > k, then the symmetries τ0, τ1, . . . , τn−1 commute with each other and thus generate
an elementary abelian group of order 2n, while the symmetries ρ, µ and τ0 generate a
semidirect product Zn2 oDn of order n2n+1. Unless n = 4, this is also the full symmetry
group of the graph (see [44]).
The Praeger-Xu graphs generalize two families of graphs: PX(n, 1) = W(n, 2) and
PX(n, 2) = R2n(n+ 2, n+ 1).
15 Gardiner-Praeger constructions
The paper [14] constructs two families of tetravalent graphs whose groups contain large
normal subgroups such that the factor graph is a cycle. The first is C±1(p, st, s), and the
second is C±e(p, 2st, s). In the Census, we use a slight generalization of both, which we
notate CPM(n, s, t, r), where n is any integer at least 3, s is an integer at least 2, t is a
20 Art Discrete Appl. Math. 3 (2020) #P1.08
b
a
A B
ec
d
C D
Figure 18: Diagram for the graph Curtainn(a, b, c, d, e)
positive integer, and r is a unit mod n. We first form the digraph CPM[n, s, t, r]. Its vertex
set is Zsn ×Zst. Directed edges are of the form ((x, i), (x± riej , i+ 1)), where j is i mod
s, and ej is the j-th standard basis vector for Zsn. If rst is ±1 mod n, then CPM[n, s, t, r]
is a semitransitive orientation for its underlying graph CPM(n, s, t, r). When the graph is
not connected, we re-assign the name CPM(n, s, t, r) to the component containing (0, 0).
If n is odd, then the graph has stns vertices. If n is even then it has st(n2 )
s vertices if t is
even and twice that many if t is odd.
Some special cases are known: For r = 1,CPM(n, s, t, 1) ∼= C±1(n, st, s). If r2 = 1,
then CPM(n, s, 2t, r) is C±r(p, 2st, s). When s = 1,CPM(n, 1, t, r) ∼= PS(n, t; r). If
s = 1 and t = 4, then the graph is a Wreath graph. When s = 2 and t is 1 or 2, then the
graph is toroidal. Other special cases are conjectured:
The convention in the following conjectures is that q is a number whose square is one
mod m and p is the parity function:
p(t) =
{
1 if t is odd
2 if t is even (15.1)
With that said, we believe that:
1. If t is not divisible by 3, then CPM(3, 2, t, 1) ∼= PS(6,m; q) where m = 3t.
2. If t is not divisible by 5, then CPM(5, 2, t, 1) ∼= CPM(5, 2, t, 2) ∼= PS(10,m; q)
where m = 5tp(t).
3. If t is not divisible by 3, then CPM(6, 2, t, 1) ∼= PS(6,m; q) where m = 12tp(t) .
4. If t is not divisible by 4, then CPM(8, 2, t, 1) ∼= CPM(8, 2, t, 3) ∼= MPS(8,m; q)
where m = 16tp(t) .
5. For all s, CPM(4, s, t, 1) ∼= PX( 2stp(t) , s).
16 Graphs Γ± of Spiga, Verret and Potočnik
It was proved in [37] that a tetravalent graph Γ whose automorphism group G is dart-
transitive is either 2-arc-transitive (and then |Gv| ≤ 2436), a PX-graph (see Section 14),
one of eighteen exceptional graphs, or it satisfies the inequality
|V (Γ)| ≥ 2|Gv| log2(|Gv|/2). (∗)
This result served as the basis for the construction of a complete list of dart-transitive
tetravalent graphs (see [36] for details).
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 21
Moreover, in [35] it was proved that a graph attaining the bound (∗) has t2t+2 vertices
for some t ≥ 2 and is isomorphic to one of the graphs (t, ), for  ∈ {0, 1}, defined below
as coset graphs of certain groups G0t or G
1
t . Recall that the coset graph Cos(G,H, a) on
a group G relative to a subgroup H ≤ G and an element a ∈ G is defined as the graph
with vertex set the set of right cosets G/H = {Hg | g ∈ G} and with edge set the set
{{Hg,Hag} | g ∈ G}.
For  ∈ {0, 1} and t ≥ 2, let Gt be the group defined as follows:
Gt = 〈x0, . . . , x2t−1, z, a, b | x2i = z2 = b2 = za2t = (ab)2 = 1,
[xi, z] = 1 for 0 ≤ i ≤ 2t− 1,
[xi, xj ] = 1 for |i− j| 6= t,
[xi, xt+i] = z for 0 ≤ i ≤ t− 1,
xai = xi+1 for 0 ≤ i ≤ 2t− 1,
xbi = xt−1−i for 0 ≤ i ≤ 2t− 1〉.
In either group, we let H = 〈x0, . . . , xt−1, b〉, and define graphs
PPM(t, ) = Cos(Gt, H, a),
denoted Γ+t (for  = 0) and Γ
−
t (for  = 1) in [35]. We should point out that a graph
Γ = PPM(t, ) is a 2-cover of the Praeger-Xu graph PX(2t, t). Furthermore, the girth
of PPM(t, ) is generally 8, the only exceptions being that PPM(2, 0) has girth 4, and
PPM(3, 0) has girth 6. Finally, PPM(2, 0) ∼= PX(4, 3), while in all other cases the graph
Γ is not isomorphic to a PX graph.
The 2016 edition of the Census seems, mysteriously, to have missed implementing this
construction. The next edition will include these graphs. Meanwhile, we know that exactly
6 of them fall in the range of sizes addressed in the Census. The resulting entries are:
PPM(2,0) = C4[32,2] = {4, 4}4,4.
PPM(2,1) = C4[32,5] = MSY(4, 8, 5, 4).
PPM(3,0) = C4[96,27] = KE24(1, 22, 8, 3, 7).
PPM(3,1) = C4[96,24] = KE24(1, 13, 4, 21, 5).
PPM(4,0) = C4[256,72] = UG(ATD[256, 128]).
PPM(4,1) = C4[256,78] = UG(ATD[256, 146]).
17 From cubic graphs
In this section, we describe five constructions, each of which constructs a tetravalent graph
from a smaller cubic (i.e., trivalent) graph in such a way that the larger graph inherits many
symmetries from the smaller graph. Throughout this section, assume that Λ is a cubic
graph, and that it is dart-transitive. Our source of these graphs is Marston Conder’s census
of symmetric cubic graphs of up to 10,000 vertices [8].
17.1 Line graphs
The line graph of Λ is a graph Γ = L(Λ) whose vertices are, or correspond to, the edges
of Λ. Two vertices of Γ are joined by an edge exactly when the corresponding edges of Λ
share a vertex. Every symmetry of Λ acts on Γ as a symmetry, though Γ may have other
symmetries as well. Clearly, if Λ is edge-transitive, then Γ is vertex-transitive. If Λ is dart-
transitive, then Γ is edge-transitive, and if Λ is 2-arc-transitive, then Γ is dart-transitive.
22 Art Discrete Appl. Math. 3 (2020) #P1.08
17.2 Dart graphs
The Dart Graph of Λ is a graph Γ = DG(Λ) whose vertices are, or correspond to, the darts
of Λ. Edges join a dart (a, b) to the dart (b, c) whenever a and c are distinct neighbors of b.
Clearly, DG(Λ) is a two-fold cover of L(Λ).
17.3 Hill capping
For every vertex A of Λ, we consider the symbols (A, 0), (A, 1), though we will ususally
write them as A0, A1. Vertices of Γ = HC(Λ) are all unordered pairs {Ai, Bj} of symbols
where {A,B} is an edge of Λ. Edges join each vertex {Ai, Bj} to {Bj , C1−i} where A
and C are distinct neighbors of B.
If Λ is bipartite and 2-arc-transitive then Γ is dart-transitive. If Λ is bipartite and not
2-arc-transitive then Γ is semisymmetric. If Λ is not bipartite and is 2-arc-transitive then Γ
is 12 -arc-transitive.
HC(Λ) is clearly a fourfold cover of L(Λ); it is sometimes but not always a twofold
cover of DG(Λ). The Hill Capping is described more fully in [15].
17.4 3-arc graph
The three-arc graph of Λ, called A3(Λ) in the literature [18] and called TAG(Λ)in the
Census, is a graph whose vertices are the darts of Λ, with (a, b) adjacent to (c, d) exactly
when [b, a, c, d] is a 3-arc in Λ. Thus, a and c are adjacent, b 6= c and a 6= d. This graph is
dart-transitive if Λ is 3-arc-transitive.
18 Cycle decompositions
A cycle decomposition of a tetravalent graph Λ is a partition C of its edges into cycles.
Every edge belongs to exactly one cycle in C and each vertex belongs to exactly two cycles
of C. Aut(C) is the group of all symmetries of Λ which preserve C. One possibility for such
a symmetry is a swapper. If v is a vertex on the cycle C, a C−swapper at v is a symmetry
which reverses C while fixing v and every vertex on the other cycle through v.
If C is a cycle decomposition of Λ, the partial line graph of C, written P(C) and notated
PL(C) in the Census, is a graph Γ whose vertices are (or correspond to) the edges of Λ,
and whose edges are all {e, f} where e and f are edges which share a vertex but belong to
different cycles of C.
Because Aut(C) acts on Γ as a group of its symmetries, the partial line graph is use-
ful for constructing graphs having a large symmetry group. Almost all tetravalent dart-
transitive graphs have cycle decompositions whose symmetry group is transitive on darts.
These are called “cycle structures” in [31].
If Λ is 12 -arc-transitive, then it has a cycle decomposition A into ’alternating cycles’
[25]. If the stabilizer of a vertex has order at least 4, then P(A) has a 12 -arc-transtive action
and may actually be 12 -arc-transitive.
Many graphs in the census are constructed from smaller ones using the partial line
graph. Important here are the Praeger-Xu graphs. Each PX(n, k) has a partition C of
its edges into 4-cycles of the form:(i, 0x), (i + 1, x0), (i, 1x), (i + 1, x1). Then P(C) is
isomorphic to PX(n, k + 1). A special case of this is that family (b) of Rose Window
graphs is P applied to family (a), the wreath graphs.
The toroidal graphs have a cycle decomposition in which each cycle consists entirely
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 23
of vertical edges or entirely of horizontal edges. The partial line graph of this cycle decom-
position is another toroidal graph. For the rotary case, P({4, 4}b,c) = {4, 4}b+c,b−c. The
other two families of toroidal maps need not have edge-transitive partial line graphs.
It may happen that a cycle decomposition C is a ’suitable LR structure’ [42]; this means
that C has a partition intoR and G (the ’red’ and the ’green’ cycles) such that every vertex
belongs to one cycle from each set, that the subgroup of Aut(C) which sends R to itself
is transitive on the vertices of Λ, that Aut(C) has all possible swappers, that no element
of Aut(C) interchanges R and G and, finally, that no 4-cycle alternates between R and
G. With all of that said, if C is a suitable LR structure, then P(C) is a semisymmetric
tetrtavalent graph in which each edge belongs to a 4-cycle. Further, every such graph is
constructed in this way. [42]
19 Some LR structures
The Census uses the partial line graph construction on a number of families of LR struc-
tures, shown here.
19.1 Barrels
The barrels are the most common of the suitable LR structures. The standard barrel is
Br(k, n; r), where k is an even integer at least 4, n is an integer at least 5 and r is a number
mod n such that r2 = ±1 (mod n) but r 6= ±1 (mod n). The vertex set is Zk × Zn. Green
edges join each (i, j) to (i, j + ri). Red edges join each (i, j) to (i+ 1, j).
The mutant barrel is MBr(k, n; r), where k is an even integer at least 2, n is an even
integer≥ 8 and r is a number mod n such that r2 = ±1 (mod n) but r 6= ±1 (mod n). The
vertex set is Zk ×Zn. Green edges join each (i, j) to (i, j+ ri). Red edges join each (i, j)
to {
(i+ 1, j) if i 6= k − 1
(0, j + n2 ) if i = k − 1
.
19.2 Cycle structures
If Λ is a tetravalent graph admiting a cycle structure C, we can form an LR struture from it
in two steps:
1. Replace each vertex v with two vertices, each incident with the two edges of one
of the two cycles in C containing v; think of these as green edges. Join the two vertices
corresponding to v with two parallel red edges. Call this C ′. We can cover C ′ in different
ways.
2a. Double cover C ′. We assign weights or voltages to red edges so that each pair has
one 0 and one 1. Voltages for green edges are assigned in one of two ways: (0) every green
edge gets voltage 0 or (1) one edge in each green cycle gets voltage 1, and the rest get
0. The double covers corresponding to these two assignments are called CS(Λ, C, 0) and
CS(Λ, C, 1), respectively, and they are, in most cases, suitable LR structures, as shown in
[43].
2b. Cover C ′ k-fold for some k at least 3. We assign weights or voltages to red edges
so that each pair has a 1 in each direction. All green edges are assigned voltage 0. The
k-cover corresponding to this assignment is called CSI(Λ, C, k), and [43] shows that each
24 Art Discrete Appl. Math. 3 (2020) #P1.08
such is a suitable LR structure.
19.3 Bicirculants
Consider a bicoloring of the edges of the bicirculant BCn(0, a, b, c) with green edges link-
ing Ai to Bi and Bi+a and red edges linking Ai to Bi+b and Bi+c. We call this coloring
BCn({0, a}, {b, c}). The paper [40] shows several cases in which BCn({0, a}, {b, c}) is a
suitable LR structure:
1. a = 1 − r, b = 1, c = s, where r, s ∈ Z∗n \ {−1, 1}, r2 = s2 = 1, r 6∈
{−s, s}, and (r − 1)(s− 1) = 0.
2. n = 2m, a = m, b = 1, c ∈ Z2m \{1,−1,m+ 1,m−1} such that c2 ∈ {1,m+ 1}.
3. n = 4k, a = 2k, b = 1, c = k + 1, for k ≥ 3
Moreover, it is conjectured in that paper that every suitable BCn({0, a}, {b, c}) is isomor-
phic to at least one of these three.
19.4 MSY’s and MSZ’s
The graph MSY(m,n; r, t) has an LR structure, with edges of the first kind being red and
those of the second kind being green, if and only if 2t = 0 and r2 = ±1. Many examples
of MSZ graphs being suitable LR structures are known, but no general classification has
been attempted.
19.5 Stack of pancakes
The structure is called SoP(4m, 4n). Let r = 2n+ 1. The vertex set is Z4m × Z4n × Z2.
Red edges join (i, j, k) to (i, j±rk, k); for a fixed i and j, green edges join the two vertices
(2i, j, 0) and (2i, j, 1) to the two vertices (2i+ 1, j, 0) and (2i+ 1, j, 1) if j is even, to the
two vertices (2i− 1, j, 0) and (2i− 1, j, 1) if j is odd.
The paper [43] shows that this is a suitable LR structure for all m and n, and that
the symmetry group of it and of its partial line graph, can have arbitrarily large vertex-
stabilizers.
19.6 Rows and columns
The LR structure RC(n, k) has as vertices all ordered pairs (i, (r, j)) and ((i, r), j), where
i and j are in Zn, and r is in Zk, where k and n are integers at least 3. Green edges join
(i, (r, j)) to (i± 1, (r, j)) and ((i, r), j) to ((i, r), j ± 1), while red edges join (i, (r, j)) to
((i, r ± 1), j) and so ((i, r), j) to (i, (r ± 1, j)).
This structure is referred to in both [40] and [43].
19.7 Cayley constructions
Suppose a group A is generated by two sets, R and G, of size two, neither containing the
identity, and each containing the inverse of each of its elements. Then we let Cay(A;R,G)
be the structure whose vertex set is A, whose red edges join each a to sa for s ∈ R and
whose green edges join each a to sa for s ∈ G. The paper [40] shows that if A admits two
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 25
automorphisms, one fixing each element of R but interchanging the two element of G and
the other vice versa, then Cay(A;R,G) is an LR structure. The condition RG 6= GR is
equivalent to the structure not having alternating 4-cycles.
Many examples occur in the case where A is the dihedral group Dn. One family of this
type is the first group of bicirculants BCn({0, 1− r}, {1, s}) shown in subsection 19.3.
The paper [40] shows several other algebraically defined structures. First, there are
examples for the group Dn where the swappers do not arise from group automorphisms.
Second, there is a Cayley construction for the structure RC(n, k) of the previous subsec-
tion.
Further, the body of the paper shows six ’linear’ constructions in which A is an exten-
sion of some Zkn:
Construction 19.1. For n and k both at least 3, let A be a semidirect product of Zkn with
the group generated by the permutation σ = (123 . . . k − 1k) acting on the coordinates.
Let e1 be the standard basis element (100 . . . 0), let R = {e1,−e1} and G = {σ, σ−1}.
We define the LR structure AffLR(n, k) to be Cay(A;R,G).
Construction 19.2. Let ProjLR(k, n) be AffLR(k, n) factored out by the cyclic group
generated by (1, 1, . . . , 1).
Construction 19.3. Let ProjLR◦(2k, n) be AffLR(2k, n) factored out by the group gen-
erated by all di = ei − ei+k, where ei is the standard basis element having a 1 in position
i and zeroes elsewhere.
Construction 19.4. Let A be a semidirect product of Z2k2 with the group generated by
the permutation γ = (1, 2, 3, . . . , k)(k + 1, k + 2, . . . , 2k). acting on the coordinates.
Let R = {e1, ek+1} and G = {γ, γ−1}. We define the LR structure AffLR2(k) to be
Cay(A;R,G).
Let d1 be the 2k-tuple in which the first k entries are 1 and the last k entries are 0; let d2
be the 2k-tuple in which the first k entries are 0 and the last k entries are 1; let d = d1 + d2.
Construction 19.5. Let ProjLR′(k) be AffLR2(k) factored out by the group generated by
d1 and d2.
Construction 19.6. Let ProjLR”(k) be AffLR2(k) factored out by the group generated
by d.
The paper [40] proves that all six of these constructions lead to suitable LR structures
(except for a few cases).
20 Base graph-connection graph constructions
This section deals with a family of constructions called base graph - connection graph
(BGCG) constructions. In these, we construct an edge-transitive bipartite graph Γ from a
set of copies of the subdivision (see section 3.2) of a base graph B, connected according
to a connection graph C and some other information.
For a tetravalent graphB, letB∗ be its subdivision, i.e., the graph resulting by replacing
each edge of B with a path of length 2. We refer to its 4-valent vertices as black and its
valence-2 vertices as white. We will often refer to an edge of B and the white vertex on the
path that replaces it in B∗ as being equivalent or corresponding.
26 Art Discrete Appl. Math. 3 (2020) #P1.08
In the constructions we often define a partition P of the edges of a graph (equivalently,
of the white vertices of its subdivision) into sets of size 2, and refer to such a P as a pairing.
We can regard the partition as a coloring of the edges of the graph. We can also think of
the pairing as an involutory permutation by writing y = xP when {x, y} ∈ P .
Given simple graphs B and C, let X be a disjoint union of copies of B, one copy Br
for each vertex r of C. Refer to this X as BC . A pairing P of X is compatible with C
provided that it satisfies these two conditions:
1. if {x, y} ∈ P with x in Br and y in Bs, r 6= s, then {r, s} is an edge of C, and
2. every edge of C is so represented.
These ingredients are combined in the following construction:
Construction 20.1. Given a tetravalent base graph B, a connection graph C, and a pair-
ing P on X = BC which is compatible with C, form a graph Γ by identifying each pair of
white vertices of X∗ which corresponds to an element of P . We refer to Γ as a BGCG of
B and C with respect to P , and write Γ = BGCG(B,C,P).
Theorem 20.2 ([49]). If B is tetravalent, C is a graph, and P is a pairing of BC which is
compatible with C, then Γ = BGCG(B,C,P) is a bipartite tetravalent graph.
Definition 20.3. If X is a (connected or disconnected) tetravalent graph and P is a pairing
onX , we will call P a dart-transitive pairing provided that the subgroup of Aut(X) which
preserves P is transitive on the darts of X .
Theorem 20.4 ([49]). If B and C are each dart-transitive and if P is a dart-transitive
pairing on X = BC which is compatible with C, and if Γ = BGCG(B,C,P) is defined,
then Γ is a bipartite edge-transitive graph.
Theorem 20.4 is the basis for several BGCG constructions, each depending on the na-
ture of C.
Theorem 20.5 (C = K1). Suppose that Q is a dart-transitive pairing on B. Then
BGCG(B,K1,Q) is an edge-transitive tetravalent graph.
Theorem 20.6 (C = K2). Suppose that Q is a dart-transitive pairing on B, and consider
the vertex set ofK2 to be {1, 2}. If e is an edge ofB, let (e, 1) and (e, 2) be the correspond-
ing edges in X = BK2 . Define P on X by (e, 1)P = (eQ, 2). Then BGCG(B,K2,P) is
an edge-transitive tetravalent graph.
No truly general technique yet exists in the case when C is the n-cycle Cn. We give
here two constructions from [56] and remark that there are many more for C = Cn.
Construction 20.7. Suppose that
1. Q is a dart-transitive pairing of B invariant under a dart-transitive group G,
2. there is a partition {R,G} of the edges ofB into two ‘colors’ (R= ‘red’, G= ‘green’)
which is also invariant under G,
3. each pair in Q meets bothR and G,
4. the vertex set of Cn is Zn.
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 27
Then we can form P1 and P2 on X = BCn as follows: for each pair {e, f} in Q, with
e ∈ R, and for each i ∈ Zn, we let (e, i)P1 = (f, i + 1). If n is even, then for i even, we
let (e, i)P2 = (e, i+ 1), and for i odd, we let (f, i)P2 = (f, i+ 1).
Theorem 20.8 (C = Cn). With P1 and P2 as above, BGCG(B,Cn,P1) and BGCG(B,
Cn,P2) are edge-transitive tetravalent graphs.
In the Census, we have no efficient way to describe the diferent pairs, (Q, {R,G}), and
so we simply number them. If the pair is numbered i, the Census reports BGCG(B,Cn,P1)
as “BGCG(B,Cn, i)” and BGCG(B,Cn,P2) as “BGCG(B,Cn, i′)”.
21 From regular maps
A map is an embedding of a graph or multigraph on a compact connected surface such that
each component of the complement of the graph (these are called faces) is topologically a
disk. A symmetry of a map is a symmetry of the graph which extends to a homeomorphism
of the surface. A map M is rotary provided that for some face and some vertex of that
face, there is a symmetry R which acts as rotation one step about the face and a symmetry
S which acts as rotation one step about the vertex. A mapM is reflexible provided that it
is rotary and has a symmetry X acting as a reflection fixing that face and vertex. IfM is
rotary but not reflexible, we call it chiral. See [15] for more details.
If M is rotary, its symmetry group, Aut(M), is transitive on faces and on vertices.
Thus all faces have the same number p of sides and all vertices have the same degree q. We
then say thatM has type {p, q}.
21.1 Underlying graphs
The underlying graph of a rotary mapM is called UG(M) and is always dart-transitive.
If q = 4, it belongs in this census.
21.2 Medial graphs
The vertices of the medial graph, MG(M), are the edges of M. Two are joined by
an edge if they are consecutive in some face (and so in some vertex). If M is rotary,
MG(M) is always edge-transitive. If M is reflexible or if it is self-dual in such a way
that some orientation-preserving homeomorphism of the surface interchangesM with its
dual, D(M), then MG(M) is dart-transitive. If not, it is quite often, but not quite always,
1
2 -transitive. No one seems to know a good criterion for this distinction.
21.3 Dart graphs
The vertices of the dart graph, DG(M), are the darts ofM. Two are joined by an edge if
they are head-to-tail consecutive in some face. The graph DG(M) is a twofold cover of
MG(M) and is often the medial graph of some larger rotary map. It can be dart-transitive
or 12 -transitive; again, no good criterion is known.
21.4 HC of maps
The Hill Capping of a rotary map M is defined in a way completely analogous to the
capping of a cubic graph Λ: we join {Ai, Bj} to {Bj , C1−i} where A,B and C are ver-
tices which are consecutive around some face. The graph HC(M) is a 4-fold covering
28 Art Discrete Appl. Math. 3 (2020) #P1.08
of MG(M) and can be dart-transitive or semisymmetric or 12 -transitive or even not edge-
transitive.
21.5 XI of maps
Suppose thatM is a rotary map of type {p, q} for some even q = 2n. Then each corner of
the map (formed by two consecutive edges in one face) is opposite at that vertex to another
corner; we will call such a pair of corners an ’X’. As an example, consider Figure 19, which
shows one vertex, of degree 6, in a map. The X’s are pairs a, b, c of opposite corners.
1 2
6 3
5 4
a b c
abc
Figure 19: X’s and I’s in a map
We form the bipartite graph XI(M) in this way: The black vertices are the X’s, the
white vertices are the edges of M, and edges of XI(M) are all pairs {x, e} where x is
an X and e is one of the four edges of x. Continuing our example, the black vertex a is
adjacent to white vertices 1, 3, 4, 6, while b is adjacent to 1, 2, 4, 5 and c to 2, 3, 5, 6.
It is interesting to see the construction introduced here as a special case of two previous
constructions. First it is made from MG(M) using a BGCG construction in which each
edge of MG(M) is paired with the one opposite it at the vertex of M containing the
corresponding corner.
Secondly, it is P of an LR structure called a locally dihedral cycle structure as outlined
at the end of [43].
It is clear that ifM is reflexible, then XI(M) is edge-transitive; it is surprising, though,
that sometimes (criteria still unknown) XI of a chiral map can also be edge-transitive.
22 Sporadic graphs
There are a few graphs in the Census which are given familiar names rather than a para-
metric form. These are: K5 = C5(1, 2), the Octahedron = K2,2,2. Also there is the graph
Odd(4); its vertices are subsets of {1, 2, 3, 4, 5, 6, 7} of size 3. Two are joned by an edge
when the sets are disjoint. Finally, there is the graph denoted Gray(4) due to a construc-
tion by Bouwer [7] which generalizes the Gray graph to make a semisymmetric graph of
valence n on 2nn vertices, in this case, 512. In fact we wanted to extend the Census to 512
vertices in order to include this graph.
Out of more than 7000 graphs in this Census, 400 of them have as their listed names one
of the tags AT[n, i],HT[n, i] or SS[n, i] from the computer-generated censi. These graphs,
then, must have no other known constructions. Each of these might be truly sporadic or,
perhaps, might belong to some interesting family not yet recognized.
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 29
Each of these is a research project in its own right, a single example waiting to be
meaningfully generalized.
23 Open questions
1. In compiling the Census, whenever we wanted to include a parameterized family
(Cn(1, a) (section 5), BCn(a, b, c, d) (section 12), Prn(a, b, c, d) (section 13.1), etc.
), it was very helpful to have some established theorems which either completely
classified which values of the parameters gave edge-transitive graphs or restricted
those parameters in some way. In families for which no such theorems were known,
we were forced into brute-force searches, trying all possible values of the parameters.
In many cases this caused our computers to run out of time or space before finishing
the search. There are many families for which no such results or only partial results
exist. So, our first and most pressing question is :
For which values of parameters are the following graphs edge-transitive (or LR):
AMC(k, n,M) (section 9),
MSZ(m,n; k, r) (section 13.2.2),
MC3(m,n, a, b, r, t, c) (section 13.2.3),
LoPrn(a, b, c, d, e) (section 13.3),
WHn(a, b, c, d) (section 13.3),
KEn(a, b, c, d, e) (section 13.3),
Curtainn(a, b, c, d, e) (section 13.3),
CPM(n, s, t, r) (section 15).
2. The general class IV metacirculants (of which the graphs MSZ are merely a part)
has begun to be explored. It is parameterized in [1], where the authors point out that
not all values of the parameters which make the graph metacirculent make it 12 -arc-
transitive. Then the same questions as above are relevant: When are these graphs
isomorphic? dart-transitive? 12 -arc-transitive? LR structures?
3. Given a and n with a2 ≡ ±1 (mod n), which toroidal graph is isomorphic to
Cn(1, a)? See sections 5 and 6. The toroidal graphs are very common and almost
every family includes some as special cases. In researching a family, we often point
out that certain values of the parameters give toroidal graphs and so will not be stud-
ied with this family. However, it is often difficult to say exactly which toroidal graph
is given by the indicated parameters. This is simply the first of many such questions.
4. Under what conditions on their parameters can two spidergraphs be isomorphic?
This is a question mentioned in [54]. Many examples of isomorphism theorems are
given there as well as examples which show that not all isomorphisms have been
found.
5. The Attebery construction presents many challenges. First, for the general construc-
tion, under what conditions are the graphs Att(A, T, k; a, b) and Att(A, T ′, k; a′, b′)
isomorphic? It is clear that if P is any automorphism of A, then Att(A, T, k; a, b) ∼=
Att(A,P−1TP, k; aP, bP ), but it is almost certain that there are other isomorphisms.
Even in the special AMC construction, we do not know when AMC(k, n,M) can
be isomorphic to AMC(k′, n′,M ′). This question must be answered before we can
make much progress on other aspects of the Attebery graphs.
30 Art Discrete Appl. Math. 3 (2020) #P1.08
6. Some graphs with the same diagrams as the metacirculants PS,MPS,MSY,MSZ,MC3
are not themselves metacirculants but are nevertheless edge-transitive. For example
consider the graph KE12(1, 3, 8, 5, 1) It is isomorphic to the graph whose vertices
are Z4 × Z12, with each (1, i) adjacent to (2, i) and (2, i + 1), each (2, i) to (3, i)
and (3, i + 4), each (3, i) to (4, i + 4) and (4, i + 5), and each (4, i) to (1, i) and
(1, i + 10). This diagram is the same ‘sausage graph’ that characterizes the PS and
MPS graphs and yet the graph is not isomorphic to any PS or MPS graph. This
happens rarely enough that the exceptional cases might be classifiable.
7. The Praeger-Xu graphs, including W(n, 2) and R2m(m + 2,m + 1), present many
problems computationally. Some aspects, such as semitransitive orientations, cycle
structures and regular maps have been addressed in [16]. Can we establish theo-
rems determining their dart-transitive colorings, their BGCG dissections, and other
properties?
8. When do the constructions DG, HC, TAG, applied to some cubic graph Λ or some
rotary mapM, simply result in the line graph or medial graph of some larger graph
or map?
9. The BGCG constructions we have used here are only the beginning of this topic. We
have given some constructions for cases where the connection graph is K1,K2, or
Ck, but for other connection graphs, we have no general techniques at all.
10. How can XI of a chiral map be edge-transitive?
11. The 3-arc graph of a cubic graph (see section 17.4) is the partial line graph of some
cycle decomposition; what decomposition? . . . of what graph?
12. In section 19, we use cycle structures to construct LR structures. What is an efficient
way to find all isomorphism classes of cycle structures for a given dart-transitive
tetravalent graph?
References
[1] I. Antončič and P. Šparl, Classification of quartic half-arc-transitive weak metacirculants of
girth at most 4, Discrete Math. 339 (2016), 931–945, doi:10.1016/j.disc.2015.10.015.
[2] I. Antončič and S. Wilson, Symmetries of the marušič-Šparl y graphs, in preparation.
[3] C. Attebery, Constructing Graded Semi-Transitive Orientations of valency 4(p − 1), Master’s
thesis, Northern Arizona University, 2008, m.Sc. Thesis.
[4] N. L. Biggs, Aspects of symmetry in graphs, in: Algebraic methods in graph theory,
Vol. I, II (Szeged, 1978), North-Holland, Amsterdam-New York, volume 25 of Colloq.
Math. Soc. János Bolyai, pp. 27–35, 1981, https://books.google.com/books?id=
4LgrAAAAYAAJ.
[5] M. Boben, Š. Miklavič and P. Potočnik, Consistent cycles in 1
2
-arc-transitive graphs, Electron.
J. Combin. 16 (2009), Research Paper 5, 10, doi:10.37236/94.
[6] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, vol-
ume 24, pp. 235–265, 1997, doi:10.1006/jsco.1996.0125, computational algebra and number
theory (London, 1993).
[7] I. Bouwer, On edge but not vertex transitive regular graphs, Journal of Combinatorial Theory,
Series B 12 (1972), 32–40, doi:https://doi.org/10.1016/0095-8956(72)90030-5.
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 31
[8] M. Conder, Trivalent (cubic) symmetric graphs on up to 10000 vertices, www.math.
auckland.ac.nz/˜conder/symmcubic10000list.txt.
[9] M. Conder and P. Dobcsányi, Trivalent symmetric graphs on up to 768 vertices, J. Com-
bin. Math. Combin. Comput. 40 (2002), 41–63, http://citeseerx.ist.psu.edu/
viewdoc/summary?doi=10.1.1.42.8190.
[10] M. Conder, A. Malnič, D. Marušič and P. Potočnik, A census of semisymmetric cubic graphs on
up to 768 vertices, J. Algebraic Combin. 23 (2006), 255–294, doi:10.1007/s10801-006-7397-3.
[11] D. Ž. Djoković, A class of finite group-amalgams, Proc. Amer. Math. Soc. 80 (1980), 22–26,
doi:10.2307/2042139.
[12] D. Firth, An algorithm to find normal subgroups of a finitely presented group up to a given
index, Ph.D. thesis, University of Warwick, 2005, http://encore.lib.warwick.ac.
uk/iii/encore/record/C__Rb1782755.
[13] J. Folkman, Regular line-symmetric graphs, J. Combinatorial Theory 3 (1967), 215–232, doi:
10.1016/s0021-9800(67)80069-3.
[14] A. Gardiner and C. E. Praeger, A characterization of certain families of 4-valent symmetric
graphs, European J. Combin. 15 (1994), 383–397, doi:10.1006/eujc.1994.1042.
[15] A. Hill and S. Wilson, Four constructions of highly symmetric tetravalent graphs, J. Graph
Theory 71 (2012), 229–244, doi:10.1002/jgt.20520.
[16] R. Jajcay, P. Potočnik and S. Wilson, The Praeger-Xu graphs: cycle structures, maps, and
semitransitive orientations, Acta Math. Univ. Comenian. (N.S.) 88 (2019), 269–291, http://
www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/980.
[17] G. A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math.
Soc. (3) 37 (1978), 273–307, doi:10.1112/plms/s3-37.2.273.
[18] M. Knor and S. Zhou, Diameter and connectivity of 3-arc graphs, Discrete Math. 310 (2010),
37–42, doi:10.1016/j.disc.2009.07.026.
[19] I. Kovács, Classifying arc-transitive circulants, J. Algebraic Combin. 20 (2004), 353–358, doi:
10.1023/b:jaco.0000048519.27295.3b.
[20] I. Kovács, K. Kutnar and D. Marušič, Classification of edge-transitive rose window graphs, J.
Graph Theory 65 (2010), 216–231, doi:10.1002/jgt.20475.
[21] I. Kovács, B. Kuzman, A. Malnič and S. Wilson, Characterization of edge-transitive 4-valent
bicirculants, J. Graph Theory 66 (2011), 441–463, doi:10.1002/jgt.20594.
[22] B. Lantz, Symmetries of Tetravalent Metacirculant Graphs of type III, Master’s thesis, Northern
Arizona University, 2004, m.Sc. Thesis.
[23] C. H. Li, Permutation groups with a cyclic regular subgroup and arc transitive circulants, J.
Algebraic Combin. 21 (2005), 131–136, doi:10.1007/s10801-005-6903-3.
[24] A. Malnič, R. Nedela and M. Škoviera, Lifting graph automorphisms by voltage assignments,
European J. Combin. 21 (2000), 927–947, doi:10.1006/eujc.2000.0390.
[25] D. Marušič, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser.
B 73 (1998), 41–76, doi:10.1006/jctb.1997.1807.
[26] D. Marušič and R. Nedela, Maps and half-transitive graphs of valency 4, European J. Combin.
19 (1998), 345–354, doi:10.1006/eujc.1998.0187.
[27] D. Marušič and R. Nedela, On the point stabilizers of transitive groups with non-self-paired
suborbits of length 2, J. Group Theory 4 (2001), 19–43, doi:10.1515/jgth.2001.003.
[28] D. Marušič and P. Potočnik, Bridging semisymmetric and half-arc-transitive actions on graphs,
European J. Combin. 23 (2002), 719–732, doi:10.1006/eujc.2002.0588.
32 Art Discrete Appl. Math. 3 (2020) #P1.08
[29] D. Marušič and P. Šparl, On quartic half-arc-transitive metacirculants, J. Algebraic Combin. 28
(2008), 365–395, doi:10.1007/s10801-007-0107-y.
[30] Š. Miklavič, P. Potočnik and S. Wilson, Consistent cycles in graphs and digraphs, Graphs
Combin. 23 (2007), 205–216, doi:10.1007/s00373-007-0695-2.
[31] Š. Miklavič, P. Potočnik and S. Wilson, Arc-transitive cycle decompositions of tetravalent
graphs, J. Combin. Theory Ser. B 98 (2008), 1181–1192, doi:10.1016/j.jctb.2008.01.005.
[32] P. Potočnik, A census of small connected cubic vertex-transitive graphs, http://www.
matapp.unimib.it/˜spiga/census.html.
[33] P. Potočnik, Lists of tetravalent arc-transitive, 1
2
-arcs-transitive and semisymmetric graphs,
http://www.fmf.uni-lj.si/˜potocnik/work.htm.
[34] P. Potočnik, A list of 4-valent 2-arc-transitive graphs and finite faithful amalgams of index
(4, 2), European J. Combin. 30 (2009), 1323–1336, doi:10.1016/j.ejc.2008.10.001.
[35] P. Potočnik, P. Spiga and G. Verret, Tetravalent arc-transitive graphs with unbounded vertex-
stabilizers, Bull. Aust. Math. Soc. 84 (2011), 79–89, doi:10.1017/s0004972710002078.
[36] P. Potočnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, J.
Symbolic Comput. 50 (2013), 465–477, doi:10.1016/j.jsc.2012.09.002.
[37] P. Potočnik, P. Spiga and G. Verret, Bounding the order of the vertex-stabiliser in 3-valent
vertex-transitive and 4-valent arc-transitive graphs, J. Combin. Theory Ser. B 111 (2015), 148–
180, doi:10.1016/j.jctb.2014.10.002.
[38] P. Potočnik, P. Spiga and G. Verret, A census of 4-valent half-arc-transitive graphs and arc-
transitive digraphs of valence two, Ars Math. Contemp. 8 (2015), 133–148, doi:10.26493/
1855-3974.559.c6c.
[39] P. Potočnik and S. Wilson, Tetravalent edge-transitive graphs of girth at most 4, J. Combin.
Theory Ser. B 97 (2007), 217–236, doi:10.1016/j.jctb.2006.03.007.
[40] P. Potočnik and S. Wilson, Linking rings structures and semisymmetric graphs: Cayley con-
structions, European J. Combin. 51 (2016), 84–98, doi:10.1016/j.ejc.2015.05.004.
[41] P. Potočnik and S. Wilson, The separated box product of two digraphs, European J. Combin.
62 (2017), 35–49, doi:10.1016/j.ejc.2016.11.007.
[42] P. Potočnik and S. E. Wilson, Linking rings structures and tetravalent semisymmetric graphs,
Ars Math. Contemp. 7 (2014), 341–352, doi:10.26493/1855-3974.311.4a8.
[43] P. Potočnik and S. E. Wilson, Linking rings structures and semisymmetric graphs: combinato-
rial constructions, Ars Math. Contemp. 15 (2018), 1–17, doi:10.26493/1855-3974.1007.3ec.
[44] C. E. Praeger and M. Y. Xu, A characterization of a class of symmetric graphs of twice prime
valency, European J. Combin. 10 (1989), 91–102, doi:10.1016/s0195-6698(89)80037-x.
[45] P. Spiga and G. Verret, On the order of vertex-stabilisers in vertex-transitive graphs with local
group Cp × Cp or CpwrC2, J. Algebra 448 (2016), 174–209, doi:10.1016/j.jalgebra.2015.09.
033.
[46] M. Sterns, Symmetries of Propellor graphs, Master’s thesis, Northern Arizona University, 2008.
[47] M. C. Sterns, Classification of edge-transitive propeller graphs, 2015, https://arxiv.
org/abs/1510.08491.
[48] W. T. Tutte, Connectivity in graphs, Mathematical Expositions, No. 15, University of Toronto
Press, Toronto, Ont.; Oxford University Press, London, 1966, https://books.google.
com/books?id=lppsAAAAMAAJ.
[49] G. Verret, P. Potočnik and S. Wilson, Base graph – connection graph: Dissection and construc-
tion, 2020, in preparation, https://arxiv.org/abs/2004.02030.
P. Potočnik and S. Wilson: Recipes for edge-transitive tetravalent graphs 33
[50] J. Širáň, T. W. Tucker and M. E. Watkins, Realizing finite edge-transitive orientable maps, J.
Graph Theory 37 (2001), 1–34, doi:10.1002/jgt.1000.abs.
[51] P. Šparl, A classification of tightly attached half-arc-transitive graphs of valency 4, J. Combin.
Theory Ser. B 98 (2008), 1076–1108, doi:10.1016/j.jctb.2008.01.001.
[52] 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.
[53] R. Weiss, Presentations for (G, s)-transitive graphs of small valency, Math. Proc. Cambridge
Philos. Soc. 101 (1987), 7–20, doi:10.1017/s0305004100066378.
[54] S. Wilson, Semi-transitive graphs, J. Graph Theory 45 (2004), 1–27, doi:10.1002/jgt.10152.
[55] S. Wilson, Uniform maps on the Klein bottle, J. Geom. Graph. 10 (2006), 161–171.
[56] S. Wilson, Colorings in BGCG constructions, 2020, in preparation.