2. Ribbon graphs and arrow presentations

There are multiple representations of graphs cellularly embedded in surfaces, and each has its expository and computational advantages. We will use several of these different representations for different purposes in the following sections. Thus, we provide here a very brief reminder of some of the various ways to represent a graph embedded in a surface. A more detailed treatment may be found in [Reference Ellis-Monaghan and Moffatt8].

We begin with ribbon graphs as we will mainly use this representation in the figures.

A ribbon graph $G = (V(G),E(G))$ is a surface with boundary presented as the union of two sets of discs, a set V(G) of vertices and a set E(G) of edges, satisfying the following conditions:

1. 1. The vertices and edges intersect in disjoint line segments.

2. 2. Each such line segment lies on the boundary of precisely one vertex and precisely one edge.

3. 3. Every edge contains exactly two such line segments.

A cellular embedding of a graph G on a closed compact surface $\Sigma$ is a drawing of G on $\Sigma$ such that edges intersect only at their endpoints and each component of $\Sigma - G$ is homeomorphic to a disc. Two cellularly embedded graphs in the same surface are considered equivalent if there is a homeomorphism of the surface taking one to the other, and two cellularly embedded graphs are isomorphic if there is a homeomorphism of the surfaces that induces a graph isomorphism when restricted to the graphs embedded in the surfaces.

A cellularly embedded graph can be obtained from a ribbon graph by gluing discs into the boundary components of the ribbon graph and and then retracting the ribbon graph in the resulting surface to get the embedding of the graph in the surface. See Figure 1. Two ribbon graphs are isomorphic if they are isomorphic when represented as cellularly embedded graphs.

Figure 1.

Three ways of representing $K_4$ on the projective plane.

Arrow presentations, due to Chmutov [Reference Chmutov2], are a concise way of representing a ribbon graph. We simply draw the vertices of the ribbon graph as circles and make small directed arcs where the edges intersect the vertices (we do not draw the edges). The two arcs for a given edge are both directed clockwise (or equivalently both directed counterclockwise) if the edge has no twist, and directed as one clockwise and one counterclockwise if the edge is twisted. See Figure 1.

Arrow presentations are clearly equivalent to signed rotation systems, which encode cellularly embedded graphs by specifying, for each vertex, a cyclic rotation of its incident edges, and for each edge, a sign of $+$ or $-$ . Two signed rotation systems (and hence two arrow presentations) are equivalent up to vertex flips, which are the result of reversing the cyclic order at a vertex and toggling the sign of each of its incident edges. This corresponds to ‘flipping over’ a vertex disc in an arrow presentation. See e.g. [Reference Mohar and Thomassen18] for a good exposition of rotation systems.

Two embedded graphs G and H given by arrow presentations are isomorphic if there is a map from the vertex discs of G (including the arrow markings) to any one of the arrow presentations equivalent to the given arrow presentation of H that preserves edge incidences and agreement of arrow directions (i.e. arrows corresponding to an edge in the arrow presentation given for G are consistently oriented if and only if they are consistently oriented in the arrow presentation chosen for H). We can thus also say that two ribbon graphs are isomorphic if they are isomorphic as arrow presentations.

Because we allow loops and multiple edges and will use edge ordering to encode graph isomorphisms in the following sections, we will need the following formal definition of graph and graph isomorphism. An abstract graph consists of a set V of vertices and a set E of edges, together with an incidence map $\psi$ taking E to unordered pairs of elements of V (elements may be repeated in the pair in the case of loops). Two abstract graphs $G = (V_G, E_G)$ and $H=(V_H, E_H)$ are isomorphic if there are bijections $f\colon V_G \rightarrow V_H$ and $g\colon E_G \rightarrow E_H$ such that $\psi_G(e) = (u,v) \iff \psi_H(g(e)) = (f(u), f(v))$ .

Since ribbon graphs are the relevant objects in the remainder of the paper, we simply use the word graph to indicate a ribbon graph, with the adjective ‘ribbon’ or ‘embedded’ only for occasional emphasis. We will use the term abstract graph for the usual definition of a graph given only in terms of its vertices and edges and their incidences.

3. Dualities and the Wilson group action

Two operations on an embedded graph, forming its geometric dual and forming its Petrie dual, are the foundation of the ribbon group action central to this paper.

The geometric dual of a cellularly embedded graph is formed by placing a vertex in the center of each face, and drawing an edge in the surface between two of these vertices whenever there is an edge shared by the faces that contain them. The geometric dual is contained in the same surface as the original graph. The Petrie dual of a graph has the same vertices and edges as the original graph, but the faces are given by ‘left-right’ paths, achieved by choosing an edge, following it to one of its endpoints, and then turning either left or right to follow one of its incident faces in the original embedding, and continuing in this way, alternating the choice of turning left or right until the path closes. This process of building faces is repeated until every edge has been traversed exactly twice. The Petrie dual is generally not embedded in the same surface as the original graph.

Since we will be working primarily in the setting of ribbon graphs, we recall the formation of geometric and Petrie duals in that setting. To form the geometric dual of a ribbon graph, we sew discs into the boundary components and remove the original vertex discs. The new discs become the vertices of the dual, and the edges remain the same, although the intervals along which they coincide with the new vertices are the complements of those that coincided with the vertices of the original graph. The Petrie dual is formed for a ribbon graph by detaching one end of each edge from one of its incident vertex discs, giving the edge a half-twist, and reattaching it to the vertex disc.

Chmutov’s partial duality, and the partial Petrie duality given in [Reference Ellis-Monaghan and Moffatt7], apply these notions of duality to one edge at a time. If G is an embedded graph given by an arrow presentation and e is an edge of G, then the partial dual with respect to e changes the arrow presentation as follows. Suppose A and B are the two arrows labelled e in an arrow presentation of G. Draw a line segment with an arrow on it directed from the the head of A to the tail of B, and a line segment with an arrow on it directed from the head of B to the tail of A. Label both of these arrows e, then delete A and B and the arcs containing them to complete taking the partial dual with respect to e. To take the partial petrial with respect to e, simply reverse the direction of the arrow on exactly one of the arrows labeled e. See Figure 2. A full orbit on a single edge is shown in Figure 3. Note that taking the partial dual of an edge with distinct endpoints always reduces the number of vertices, while taking the partial dual of a loop may or may not increase the number of vertices. Also note that applying the partial dual operation to all edges gives the geometric dual, and applying the partial petrial operation to all edges gives the Petrie dual.

Figure 2.

The twist operation $\tau$ and partial dual operation $\delta$ given as arrow presentations.

Figure 3.

The full action of $\delta$ and $\tau$ on a single edge (marked with a ^* on the left). Note that the four graphs with loop edges each have three vertices, shown in yellow.

Wilson noticed that taking the geometric dual and taking the Petrie dual could be thought as operators on embedded graphs (although his attention was mainly on regular maps), and that, although each are of order two, together they generate a group isomorphic to $S_3$ , now known as the Wilson group [Reference Wilson26]. The ribbon group and restricted ribbon group action from [Reference Ellis-Monaghan and Moffatt7, Reference Ellis-Monaghan and Moffatt8] extend the Wilson group and the Wilson group action to account for partial dualities. Here, we take the further step of incorporating ribbon-graph isomorphism.

We use the lexicon from [Reference Ellis-Monaghan and Moffatt7, Reference Ellis-Monaghan and Moffatt8] given in Table 1.

Table 1

Operators on embedded graphs or subsets of their edges

4. A new algebraic framework for the ribbon group action

The ribbon group and ribbon group action were defined in [Reference Ellis-Monaghan and Moffatt7, Reference Ellis-Monaghan and Moffatt8]. These constructs fully generalise surface duality and the Wilson group, and thus provide new tools for understanding ribbon graphs. For example, [Reference Ellis-Monaghan and Moffatt7] shows that if G and H are graphs, then their medial graphs, $G_m$ and $H_m$ , are isomorphic as abstract graphs if and only if G and H are twisted duals, while [Reference Chmutov2, Reference Ellis-Monaghan and Moffatt7–Reference Ellis-Monaghan and Moffatt10] give numerous results for topological graph polynomials arising from twisted duality and the ribbon group action, and several authors have explored genus ranges of partial duals in various settings [Reference Ellingham and Zha6, Reference Moffatt19]. However, the ribbon group action of [Reference Ellis-Monaghan and Moffatt7, Reference Ellis-Monaghan and Moffatt8] is limited in that self twuality properties under it are restricted to only the case of canonical self-twuality, in which the canonical identification of the edges of the graph and its twual yields an isomorphism. Here, we develop a new algebraic framework incorporating the role of graph isomorphism in graph twualities, and thereby facilitate moving beyond canonical self-twuality to exposes also the more commonly occurring natural self-twuality.

Since in the broader setting here the six twisted duality operations apply to individual edges, the edge ordering formalism below keeps track of which operation applies to which edge. More importantly however, the edge ordering enables recording of graph isomorphism following a duality operation. For example, in Figure 4, after a partial dual operation is applied to each edge, so that the net result is the classical dual of the whole graph, the graph and its dual are isomorphic under the map that takes e to e and f to f. However, in Figure 5, the isomorphism between the graph and its dual maps e to f and f to e. We will distinguish between these two kinds of self-duality as canonical and natural, respectively, formalising this in Definitions 4.2 and 4.3 below.

A vertex flip is accomplished by switching the twistedness/non-twistedness of all edges at a single vertex. Because ribbon graphs are equivalence classes under vertex flips, twists on non-loop edges may propagate through a ribbon graph. Note, therefore, that the graph in Figure 4 is also canonically self-petrial, since in this case propagation of twists results in cancellation. Likewise, if one edge of the digon is twisted, the resulting graph is canonically self-petrial under the map that takes e to e and f to f, The graph in Figure 5 is self-dual, but not canonically self-dual, since the isomorphism between the graph and its dual is not the canonical identification of edges. The graph in Figure 5 is not self-petrial. Also, the join of two loops, one twisted and one not, as in Figure 6, is self-petrial, but not canonically self-petrial, as a twist cannot move from one loop to another.

Figure 4.

A graph that is canonically self-petrial and also canonically self-dual.

Figure 5.

A self-dual graph.

Figure 6.

A self-petrial graph.

Because of this distinction between canonical and natural self-duality, we will begin by working with graphs with a linear ordering of the edges. Let ${\mathcal{G}}_{(n)}$ denote the set of equivalence classes under isomorphism of ribbon graphs with exactly n edges, and let

\begin{equation*}{\mathcal{G}}_{or (n)} := \left\{ (G,\ell) \mid G \in {\mathcal{G}}_{(n)} \text{ and } \ell \text{ is a linear ordering of the edges} \right\}\end{equation*}

be the set of equivalence classes of ribbon graphs with exactly n ordered edges.

In particular, we think of $\ell$ explicitly as a bijection $\ell\colon [n] \mapsto E(G)$ , whose input is a position in the ordering, and whose output is the edge in that position. Two elements $(G, \ell_G)$ and $(H, \ell_H)$ of ${\mathcal{G}}_{or (n)}$ are isomorphic if there is an isomorphism of G and H as ribbon graphs so that the bijection $g\colon E_G \rightarrow E_H$ agrees with the linear orderings in that $\ell_G(i)= e \iff \ell_H(i) = g(e)$ .

The two operations, the twist $\tau$ and partial-dual $\delta$ , act on a specified edge $e_i$ of an embedded graph as shown in Figures 2 and 3.

In [Reference Ellis-Monaghan and Moffatt7] it was shown that, for each edge e, in $(G,\ell)$ , applying $\tau^2$ , $\delta^2$ , or $(\tau \delta)^3$ acts as the identity. Thus, the group

\begin{equation*} {\mathfrak{S}} := \langle \delta, \tau \; |\; \delta^2, \tau^2, (\tau \delta)^3 \rangle ,\end{equation*}

which is isomorphic to the symmetric group of order six, acts on any fixed edge of a graph $(G,\ell) \in {\mathcal{G}}_{or(n)}$ .

This action readily extends to a group action of ${\mathfrak{S}}^n$ on ${\mathcal{G}}_{or (n)}$ by allowing the various group elements to act on any subset of the edges independently and simultaneously, not just on a single distinguished edge.

If ${\hat{\gamma}} = ( g_1, g_2,g_3, \ldots , g_n ) \in {\mathfrak{S}}^n$ , then, for any $(G,\ell) \in {\mathcal{G}}_{or(n)}$ , the action of ${\hat{\gamma}}$ on $(G,\ell)$ applies $g_i$ to the edge $e_i$ in the ordering given by $\ell$ . We will view the indexing as a map, i.e. think of ${\hat{\gamma}}$ as ${\hat{\gamma}}\colon [n] \rightarrow {\mathfrak{S}}$ , so that the action applies the element ${\hat{\gamma}} (i)=g_i$ to the edge $ \ell (i)$ of G.

Twisted dualities, in particular partial duals, can be specified for graphs without ordered edges by partitioning the edges into six subsets according to which element of ${\mathfrak{S}}$ is applied. In particular, Proposition 3.7 of [Reference Ellis-Monaghan and Moffatt7] shows that every twisted dual of G admits a unique expression of the form

(1) \begin{equation}G^{\prod^6_{i=1}{{\xi}_i(A_i)}},\end{equation}

where the $A_i$ partition E(G), and where ${\xi}_1=1,\ {\xi}_2=\tau,\ {\xi}_3=\delta,\ {\xi}_4=\tau \delta,\ {\xi}_5= \delta \tau$ , and ${\xi}_6 = \tau \delta \tau \in {\mathfrak{S}}$ . This may also be written in the expanded form

(2) \begin{equation}G^{\prod_{e \in E(G)}{{\xi}_{s(e)}(e)}},\end{equation}

where if $e \in A_i$ , then $s(e) =i$ . Often, if only one element of ${\mathfrak{S}}$ is applied to some subset $A \subseteq E(G)$ , then the notation is simplified to $G^{{\xi}(A)}$ for ${\xi} \in {\mathfrak{S}}-\{1\}$ , e.g. writing $G^{\delta (A)}$ for the partial dual with respect to A.

With the preceding, we can write the action of ${\hat{\gamma}}$ on $(G,\ell)$ as

(3) \begin{equation}{\hat{\gamma}}(G,\ell) = \left(G^{\Gamma({\hat{\gamma}},\ell)}, \ell\right),\end{equation}

where $\Gamma({\hat{\gamma}},\ell) = \prod^6_{i=1}{{\xi}_i(\ell {\hat{\gamma}}^{-1}({\xi}_i))}=\prod_{e \in E(G)}{\left[ {\hat{\gamma}} \ell^{-1}(e) \right] (e)}$ . Here, $\Gamma({\hat{\gamma}},\ell)$ just sorts the edges of E(G) into a 6-partition according to the operation applied to them by ${\hat{\gamma}}$ , and then applies the appropriate operation to each partition. Although the edge order $\ell$ is used to determine $\Gamma({\hat{\gamma}},\ell)$ , note that $\ell {\hat{\gamma}}^{-1}({\xi}_i)$ is a set, so the result may be applied to G, which is unordered, without reference to edge order.

We make the following observations that will be used to prove the compatibility condition in Proposition 4.1 below. We first note that permuting the order of the edges translates simply to permuting which element of ${\mathfrak{S}}$ applies to which edge.

(4) \begin{equation}\Gamma({\hat{\gamma}},\ell \pi^{-1}) =\prod_{e \in E(G)}{\left[ {\hat{\gamma}} (\ell \pi^{-1})^{-1}(e) \right] (e)} = \prod_{e \in E(G)}{\left[ ({\hat{\gamma}}\pi) \ell^{-1}(e) \right] (e)}=\Gamma({\hat{\gamma}} \pi,\ell).\end{equation}

Furthermore, note that composition of a group element with an edge permutation distributes over the group operation $\circ$ in ${\mathfrak{S}}^n$ , so that

(5) \begin{equation}{\hat{\gamma}}_1 \pi \circ {\hat{\gamma}}_2 \pi = ({\hat{\gamma}}_1 \circ {\hat{\gamma}}_2) \pi,\end{equation}

(6) \begin{equation} {\hat{\gamma}}_1 \circ ({\hat{\gamma}}_2 \pi) = ({\hat{\gamma}}_1 \pi^{-1} \circ {\hat{\gamma}}_2 ) \pi,\end{equation}

and

(7) \begin{equation} ({\hat{\gamma}}_1 \pi) \circ {\hat{\gamma}}_2 = ({\hat{\gamma}}_1 \circ {\hat{\gamma}}_2 \pi^{-1}) \pi;\end{equation}

also,

(8) \begin{equation} ({\hat{\gamma}} \pi) ^{-1} = {\hat{\gamma}} ^{-1} \pi, \text{ since } \left({\hat{\gamma}}\pi \circ {\hat{\gamma}}^{-1}\pi \right) = \textbf{1} \pi = \textbf{1}.\end{equation}

Lastly, iterated applications of $\Gamma$ are captured by the group operation $\circ$ , in that

(9) \begin{equation}(G^{\Gamma({\hat{\gamma}}_2,\ell)})^{\Gamma({\hat{\gamma}}_1,\ell)} = G^{\Gamma({\hat{\gamma}}_1{\hat{\gamma}}_2,\ell)}.\end{equation}

Caution: Note that with this notation, $(G^{\times})^* = G^{(* \times)}$ .

There is also a second group action on ${\mathcal{G}}_{or(n)}$ . The symmetric group on n elements, $S_n$ , acts on ${\mathcal{G}}_{or(n)}$ by permuting the edge order, so $\pi (G,\ell) = (G,\ell \pi^{-1})$ , where $\ell {\pi}^{-1}$ is just composition of the functions $\ell$ and $\pi^{-1}$ . Thus, applying $\pi$ to $(G,\ell)$ permutes the ordered list of edges. We write $ \iota $ for the identity in $S_n$ .

We turn to a semidirect product of ${\mathfrak{S}}^n$ and $S_n$ for an action on ${\mathcal{G}}_{or(n)}$ that combines these two actions in a compatible way. This will be the primary algebraic tool for manipulating ribbon graphs, as its function is to apply specific elements of the ribbon group to specific edges, and furthermore to keep track of isomorphisms between graphs via the edge orderings.

Proof. Showing that $\phi$ is a homomorphism is routine since $\phi_{\pi_1\pi_2}({\hat{\gamma}}) = {\hat{\gamma}} (\pi_1 \pi_2)^{-1} = \phi_{\pi_1} \phi _{\pi_2} ({\hat{\gamma}})$ . Thus, we have a well-defined semidirect product ${\mathfrak{S}}^n \rtimes_{\phi} S_n$ with multiplication given by $({\hat{\gamma}}_1, \pi_1) ({\hat{\gamma}}_2, \pi_2) = ({\hat{\gamma}}_1 \phi_{\pi_1}({\hat{\gamma}}_2), \pi_1 \pi_2)$ .

It remains to verify the compatibility condition that $({\hat{\gamma}}_1,\pi_1)\cdot\left[({\hat{\gamma}}_2,\pi_2)\cdot(G,\ell)\right] = \left[ ({\hat{\gamma}}_1,\pi_1)({\hat{\gamma}}_2,\pi_2)\right] \cdot (G,\ell)$ .

We give two proofs of the compatibility condition for the action of ${\mathfrak{S}}^n \rtimes_{\phi} S_n$ on ${\mathcal{G}}_{or(n)}$ , as the first aligns more readily with topological intuition and the second is more fundamentally an application of algebraic machinery. However, at the heart of both proofs is the observation that first applying $({\hat{\gamma}}_2,\pi_2)$ and then applying $({\hat{\gamma}}_1,\pi_1)$ , requires ‘undoing’ the edge ordering given by $\pi_1$ so that the operations in ${\hat{\gamma}}_2$ apply to the correct edges. This exactly corresponds to the $\pi_1^{-1}$ that appears when first multiplying $({\hat{\gamma}}_1,\pi_1)({\hat{\gamma}}_2,\pi_2)$ and only then applying the result to $(G,\ell)$ , rather than applying the multiplicands iteratively to $(G,\ell)$ .

Proof 1. The first proof leverages the identities in equations (4) through (7). We compute as follows:

\begin{equation*}\begin{array}{rcl}({\hat{\gamma}}_1,\pi_1)\cdot\left[({\hat{\gamma}}_2,\pi_2)\cdot(G,\ell)\right]&=&({\hat{\gamma}}_1,\pi_1)\cdot\left(G^{\Gamma({\hat{\gamma}}_2 \pi_2,\ell)}, \ell \pi_2^{-1}\right) \\ \\[-9pt]&=&\left((G^{\Gamma({\hat{\gamma}}_2 \pi_2,\ell)})^{\Gamma({\hat{\gamma}}_1 \pi_1 ,\ell\pi_2^{-1})}, \ell \pi_2^{-1}\pi_1^{-1}\right) \\ \\[-9pt]&=&\left((G^{\Gamma({\hat{\gamma}}_2 \pi_2,\ell)})^{\Gamma({\hat{\gamma}}_1 \pi_1 \pi_2 ,\ell)}, \ell \pi_2^{-1}\pi_1^{-1}\right) \\ \\[-9pt]&=& \left(G^{\Gamma({\hat{\gamma}}_1\pi_1\pi_2\circ{\hat{\gamma}}_2 \pi_2,\ell)}, \ell \pi_2^{-1}\pi_1^{-1}\right) \\ \\[-9pt]&=& \left(G^{\Gamma(({\hat{\gamma}}_1\circ{\hat{\gamma}}_2 \pi_1^{-1})\pi_1\pi_2,\ell)}, \ell \pi_2^{-1}\pi_1^{-1}\right) \\ \\[-9pt]& = & \left({\hat{\gamma}}_1 \circ {\hat{\gamma}}_2\pi_1^{-1}, \pi_1\pi_2\right)\cdot(G,\ell)\\ \\[-9pt]& = & \left[ ({\hat{\gamma}}_1,\pi_1)({\hat{\gamma}}_2,\pi_2)\right] \cdot (G,\ell).\end{array}\end{equation*}

Here the third equality follows from equation (4), the fourth from equation (7), and the fifth from equation (5).

Proof 2. The second proof uses the following observations, which are reductions of operations within the action of the semidirect product:

(10) \begin{equation}\begin{array}{rcl} ({\hat{\gamma}}, \iota) \cdot\left[ (\textbf{1},\pi)\cdot(G,\ell)\right] & = & \left( [ G^{\Gamma(\textbf{1},\ell\pi^{-1})} ]^{\Gamma({\hat{\gamma}},\ell\pi^{-1})},\ell\pi^{-1} \right)\\[3pt] & = & \left(G^{\Gamma({\hat{\gamma}},\ell\pi^{-1})}, \ell\pi^{-1} \right) \\ & = & ({\hat{\gamma}},\pi)\cdot(G,\ell), \end{array} \end{equation}

(11) \begin{equation} \begin{array}{rcl}(\textbf{1},\pi)\cdot\left[ ({\hat{\gamma}}\pi, \iota) \cdot (G,\ell)\right]& = & \left( [ G^{\Gamma({\hat{\gamma}}\pi,\ell)} ]^{\Gamma(\textbf{1},\ell\pi^{-1})},\ell\pi^{-1} \right)\\& = & ({\hat{\gamma}},\pi)\cdot(G,\ell),\end{array}\end{equation}

(12) \begin{equation}(\textbf{1},\pi_1\pi_2)\cdot(G,\ell) = \left(G^{\Gamma(\textbf{1},\ell\pi_2^{-1}\pi_1^{-1})}, \ell\pi_2^{-1}\pi_1^{-1} \right) = (\textbf{1},\pi_1)\cdot\left[(\textbf{1},\pi_2)\cdot(G,\ell)\right], \text{and}\end{equation}

(13) \begin{equation}({\hat{\gamma}}_1{\hat{\gamma}}_2,\iota)\cdot(G,\ell) = ({\hat{\gamma}}_1,\iota)\cdot\left[({\hat{\gamma}}_2,\iota)\cdot(G,\ell)\right].\end{equation}

In fact, each of these is a particular instance when the compatibility condition of the action holds, although we don’t need that observation per se.

Now we have in general that

\begin{align*}({\hat{\gamma}}_1,\pi_1)\cdot\left[({\hat{\gamma}}_2,\pi_2)\cdot(G,\ell)\right]& = ({\hat{\gamma}}_1,\pi_1)\cdot\left[ (\textbf{1},\pi_2)\cdot\left[ ({\hat{\gamma}}_2\pi_2, \iota) \cdot (G,\ell)\right] \right]\\[3pt]& = (\textbf{1},\pi_1)\cdot\left[ ({\hat{\gamma}}_1\pi_1, \iota) \cdot\left[ (\textbf{1},\pi_2)\cdot\left[ ({\hat{\gamma}}_2\pi_2, \iota) \cdot (G,\ell)\right]\right] \right]\\[3pt]& = (\textbf{1},\pi_1)\cdot\left[ (\textbf{1},\pi_2) \cdot\left[ ({\hat{\gamma}}_1\pi_1\pi_2, \iota) \cdot\left[ ({\hat{\gamma}}_2\pi_2, \iota) \cdot (G,\ell)\right]\right] \right]\\[3pt]& = (\textbf{1},\pi_1\pi_2) \cdot \left[ ({\hat{\gamma}}_1\pi_1\pi_2 \circ {\hat{\gamma}}_2\pi_2, \iota) \cdot (G,\ell)\right]\\[3pt]& = ({\hat{\gamma}}_1 \circ {\hat{\gamma}}_2\pi_1^{-1}, \pi_1\pi_2)\cdot(G,\ell)\\[3pt]& = \left[ ({\hat{\gamma}}_1,\pi_1)({\hat{\gamma}}_2,\pi_2)\right] \cdot (G,\ell). \\[-35pt]\end{align*}

Recall that applying a permutation to an indexed set applies the inverse permutation to the indices, so that $\phi_{\pi}$ acts by permuting the indices of ${\hat{\gamma}}$ , where if ${\hat{\gamma}} = ( g_1, g_2,g_3, \ldots , g_n )$ , then $\phi_{\pi}({\hat{\gamma}})= ( g_{\pi^{-1}(1)}, g_{\pi^{-1}(2)},g_{\pi^{-1}(3)}, \ldots , g_{\pi^{-1}(n)} )$ .

Also note that $({\hat{\gamma}}, \pi)^{-1}=({\hat{\gamma}}^{-1} \pi, \pi^{-1})$ , applying equation (5) as needed.

We close this section by establishing some notation that will facilitate our exploration of the orbits and stabilisers of the ribbon group action.

As usual $Orb((G,\ell_G)) = \{(H, \ell_H) \mid ({\hat{\gamma}}, \pi)(G, \ell_G) =(H, \ell_H) \text{ for some } ({\hat{\gamma}}, \pi) \in {\mathfrak{S}}^n \rtimes_{\phi} S_n \}$ , although we will usually write $Orb(G,\ell_G)$ for $Orb((G,\ell_G))$ . In addition, we will often focus particularly on the action of the subgroup ${\mathfrak{S}}^n \rtimes_{\phi} \iota$ and will denote its orbit as $Orb_{\iota}(G,\ell_G) = \{(H, \ell_H) \mid ({\hat{\gamma}}, \iota)(G, \ell_G) =(H, \ell_H) \text{ for some } {\hat{\gamma}} \in {\mathfrak{S}}^n \}$ .

We will see that the various twualities a graph may exhibit may be revealed by examining appropriate kinds of stabilisers.

In particular, $(G,\ell)$ is self- ${\hat{\gamma}}$ for some ${\hat{\gamma}}$ different from the identity if it has a non-trivial stabiliser in ${\mathfrak{S}}^n \rtimes S_n$ , and canonically self- ${\hat{\gamma}}$ if it has a non-trivial stabiliser in ${\mathfrak{S}}^n \rtimes \iota$ .

We will be most interested in the case that G is self-dual, self-petrial, self-trial, etc. in the traditional sense. This corresponds to ${\hat{\gamma}}$ being uniform, that is, every entry of ${\hat{\gamma}}$ is the same.

Thus, for example, a graph G is canonically self-dual if $(\boldsymbol{\delta}, \iota)(G, \ell) = (G,\ell)$ .

Note that because ${\mathcal{G}}_{or(n)}$ is a set of equivalence classes, $({\hat{\gamma}}, \pi)(G, \ell) = (G,\ell)$ means that there is an isomorphism between $G^{\Gamma ({\hat{\gamma}},\ell\pi^{-1})}$ and G, and the correspondence of edges under this isomorphism is given by the mapping $\ell\pi^{-1}(i) \mapsto \ell(i)$ .

Remark 4.4 A comparison with the ribbon group and ribbon group action on graphs with ordered edges of [8, Definition 2.21] shows that this action is exactly the action of ${\mathfrak{S}}^n \rtimes \iota$ . The permutation group in ${\mathfrak{S}}^n \rtimes S_n$ allows us to define natural self-twuality precisely as $({\hat{\gamma}}, \pi)(G, \ell) = (G,\ell)$ , with $\pi$ specifying the isomorphism. The limitation of the canonical action of [Reference Ellis-Monaghan and Moffatt8] is evident in [8, Theorem 2.25] where the most that can be said is that two graphs have a given self-twuality if they both belong to a particular set, with the isomorphism unspecified.

5. Propagation of twuality

We show here that if a graph H is self- ${\hat{\gamma}}$ for some non-trivial ${\hat{\gamma}}$ , then any graph G in its orbit is also self- ${\hat{\gamma}}'$ for some ${\hat{\gamma}}'$ . Thus, once any graph is found to have some twisted duality property, that property propagates through its whole orbit. Furthermore, as we will see later, it possible to search the orbit efficiently for graphs with desired self-twuality properties.

Recall that in the classical setting, we get new self-twualities by conjugation, so that if G has some self-twuality property and H is an element of the orbit of G under the Wilson group action, then H will have a self-twuality that is conjugate to the self-twuality of G. For example, if G is self-dual, with $G=G^{\delta(E)}$ and $H=G^{\tau(E)}$ , then H is self- $\tau \delta \tau^{-1}$ .

This same principle holds for any pair of elements in the Wilson group. Here we adapt this principle to the more refined setting of the ribbon group action, which then allows us to study twuality systematically in the subsequent sections.

We begin with a short technical lemma to verify the intuitively clear fact that if H is self- ${\hat{\gamma}}$ , then this property is preserved if the edge order and the entries of ${\hat{\gamma}}$ are permuted simultaneously by the same permutation.

Proof. It suffices to verify the commutativity of the following diagram:

By the compatibility condition of the action, this follows from the following calculation in ${\mathfrak{S}}^n \rtimes_{\phi} S_n$ .

\begin{equation*} \begin{array}{rcl} ({\hat{\gamma}} \pi^{-1}, \pi \mu \pi^{-1} ) (\textbf{1}, \pi) &=& ({\hat{\gamma}} \pi^{-1} \cdot \textbf{1}\pi\mu^{-1}\pi^{-1}, \pi \mu )\\ &=& ({\hat{\gamma}}\pi^{-1} \cdot \textbf{1}, \pi\mu) \\ &=& (\textbf{1}\cdot{\hat{\gamma}}\pi^{-1},\pi\mu)\\ & = & (\textbf{1},\pi)({\hat{\gamma}},\mu). \end{array} \end{equation*}

The following proposition gives our main result in the simplest setting, where there are no permutations of the edges to keep track of, and hence the principle of the proof is easier to see.

Proof. The compatibility condition of the action and a simple calculation in ${\mathfrak{S}}^n \rtimes_{\phi} S_n$ verify that the following diagram is commutative, which proves the result.

A consequence of Proposition 5.2, given in the following theorem, is that canonical self-twuality propagates throughout the entire orbit of a graph.

Proof. The proof uses the conjugacies for $S_3$ given in Table 2.

Table 2

Conjugacy Table ( ${\alpha}$ labels the rows, ${\gamma}$ the columns)

To see that Item 5.3.1 implies Item 5.3.2, suppose that $(H, \ell_H)$ is a canonically self-twual graph via uniform ${\hat{\gamma}}$ . Then by Theorem 5.2, every graph $(G, \ell_G)$ in $Orb_{\iota}(H, \ell_H)=Orb_{\iota}(F, \ell_F)$ is canonically self- ${\hat{\alpha}} {\hat{\gamma}} {\hat{\alpha}}^{-1}$ for some ${\hat{\alpha}}$ . However, conjugation preserves order here, so by Table 2, if ${\hat{\gamma}}$ is $\delta$ -, $\tau$ -, or $\tau \delta \tau$ -uniform, then each element in ${\hat{\alpha}} {\hat{\gamma}} {\hat{\alpha}}^{-1}$ is in $\{\tau, \delta, \tau \delta \tau \}$ . Similarly, if $(G, \ell_G)$ is canonically self-trial, then every element of ${\hat{\alpha}} {\hat{\gamma}} {\hat{\alpha}}^{-1}$ must be in $\{ \tau \delta, \delta \tau \}$ . Note that ${\hat{\alpha}}$ may be trivial, in which case ${\hat{\gamma}} ={\hat{\gamma}}'$ and still has every element of order 2 or 3.

That Item 5.3.2 implies Item 5.3.3 is immediate.

To show that Item 5.3.3 implies Item 5.3.1, assume $(G, \ell_G)$ is a graph in $Orb_{\iota}(F, \ell_F)$ that is canonically self- ${\hat{\gamma}}'$ where every entry of ${\hat{\gamma}}'$ is in $\{\tau, \delta, \tau \delta \tau \}$ . We may then use the conjugacy table to select elements of ${\hat{\alpha}}$ so that ${\hat{\alpha}} {\hat{\gamma}}' {\hat{\alpha}}^{-1}$ is $\delta$ -, $\tau$ -, or $\tau \delta \tau$ -uniform. With this, $(H, \ell_H) = ({\hat{\alpha}}, \iota)(G, \ell_G)$ is the canonically self-dual, -petrial, or -wilsonial graph we seek, since if ${\hat{\gamma}}$ is the desired twuality, then $({\hat{\gamma}}, \iota) (H, \ell_H) = ({\hat{\gamma}}, \iota) ({\hat{\alpha}}, \iota)(G, \ell_G) = ({\hat{\alpha}}, \iota)({\hat{\gamma}}', \iota)({\hat{\alpha}}, \iota)^{-1} ({\hat{\alpha}}, \iota)(G, \ell_G)=({\hat{\alpha}}, \iota)({\hat{\gamma}}', \iota)(G, \ell_G)=({\hat{\alpha}}, \iota)(G, \ell_G)=(H, \ell_H)$ . An analogous approach proves the self-trial case.

The general case where $(G, \ell_G)$ is any graph in the orbit of $(H, \ell_H)$ (that is, in $Orb(H, \ell_H)$ , not necessarily $Orb_{\iota} (H, \ell_H)$ ) and where $(H, \ell_H)$ is self- ${\hat{\gamma}}$ but not necessarily canonically so, is essentially the same, but involves keeping track of the permutations. Although the conjugation is somewhat obfuscated by the appearance of the permutations, we are simply reordering to be sure that the conjugation is applied to the correct edges at each step.

Theorem 5.4 Suppose $(H, \ell_H)$ is self- ${\hat{\gamma}}$ via $\mu$ and that $(G, \ell_G) \in Orb(H, \ell_H)$ with $({\hat{\alpha}}, \pi)(H,\ell_H)=(G, \ell_G)$ . Then $(G, \ell_G)$ is self- ${\hat{\gamma}}'$ via $\mu'$ where ${\hat{\gamma}}'$ is a ‘near-conjugate’ of ${\hat{\gamma}}$ by ${\hat{\alpha}}$ , with

\begin{equation*}{\hat{\gamma}}' = {\hat{\alpha}} \cdot {\hat{\gamma}} \pi^{-1} \cdot {\hat{\alpha}}^{-1} \pi \mu^{-1} \pi^{-1},\end{equation*}

and $ \mu'= \pi \mu \pi^{-1}.$

Proof. It suffices to verify the commutativity of the following diagram:

By the compatibility condition of the action, this follows from the following calculation in ${\mathfrak{S}}^n \rtimes_{\phi} S_n$ .

\begin{align*} \left({\hat{\alpha}} \cdot {\hat{\gamma}} \pi^{-1} \cdot {\hat{\alpha}}^{-1} \pi \mu^{-1} \pi^{-1}, \pi \mu \pi^{-1}\right)({\hat{\alpha}},\pi) &= \left({\hat{\alpha}} \cdot {\hat{\gamma}} \pi^{-1} \cdot {\hat{\alpha}}^{-1} \pi \mu^{-1} \pi^{-1} \cdot {\hat{\alpha}}\pi\mu^{-1}\pi^{-1}, \pi \mu \pi^{-1}\right)\\[3pt] &= ({\hat{\alpha}} \cdot {\hat{\gamma}}\pi^{-1},\pi\mu) \\[3pt] &= ({\hat{\alpha}},\pi)({\hat{\gamma}},\mu). \\[-35pt] \end{align*}

Since ${\mathfrak{S}}$ is not commutative, we write $\prod_{i=m}^{1} {{\xi}_{i}} $ in the following theorem statement to indicate the product ${\xi}_m {\xi}_{m-1} \ldots {\xi}_1$ . We also write ord(g) for the order of a group element in ${\mathfrak{S}}$ .

Proof. To see that Item 5.5.1 implies Item 5.5.2, suppose that $(H, \ell_H)$ is a self-twual graph via uniform ${\hat{\gamma}}$ and permutation $\mu$ , and $(G, \ell_G)$ is a graph in $Orb(H, \ell_H)=Orb (F, \ell_F)$ . Then, by Theorem 5.4, $(G, \ell_G)$ is self- ${\hat{\gamma}}' = {\hat{\alpha}} \cdot {\hat{\gamma}} \pi^{-1} \cdot {\hat{\alpha}}^{-1} \pi \mu^{-1} \pi^{-1} $ via $\mu'= \pi \mu \pi^{-1}$ where ${\hat{\alpha}}$ and $\pi$ satisfy $({\hat{\alpha}}, \pi)(H, \ell_H) = (G, \ell_G)$ . In particular, for this ${\hat{\alpha}}$ and $\pi$ , we have that

(14) \begin{equation}({\hat{\gamma}}, \mu) \, = \,({\hat{\alpha}}, \pi)^{-1}({\hat{\gamma}}', \mu')({\hat{\alpha}}, \pi) \, = \,\left(({\hat{\alpha}}^{-1} \cdot {\hat{\gamma}}' \cdot {\hat{\alpha}}\mu'^{-1})\pi,\, \pi^{-1}\mu'\pi\right).\end{equation}

Hence, $({\hat{\alpha}}^{-1} \cdot {\hat{\gamma}}' \cdot {\hat{\alpha}}\mu'^{-1})\pi={\hat{\gamma}}$ , and so $({\hat{\alpha}}^{-1} \cdot {\hat{\gamma}}' \cdot {\hat{\alpha}}\mu'^{-1})={\hat{\gamma}}\pi^{-1}$ . However, ${\hat{\gamma}}$ is uniform, so $ {\hat{\gamma}}\pi^{-1}= \pi$ , and we have that

(15) \begin{equation} ({\hat{\alpha}}^{-1} \cdot {\hat{\gamma}}' \cdot {\hat{\alpha}}\mu'^{-1})={\hat{\gamma}}.\end{equation}

We now write ${\hat{\gamma}}'=({\xi}_1, {\xi}_2, \ldots, {\xi}_n)$ and also write ${\hat{\alpha}}=({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n)$ , recalling that ${\hat{\alpha}}\mu'^{-1}= ({\alpha}_{\mu'^{-1}(1)}, {\alpha}_{\mu'^{-1}(2)}, \ldots, {\alpha}_{\mu'^{-1}(n)})$ . Considering each entry of equation (15) individually, this yields that

(16) \begin{equation}{\alpha}_i^{-1} \cdot {\xi}_i \cdot {\alpha}_{\mu'^{-1}(i)}=g \text{ for all } i.\end{equation}

In particular, if $C=(c_1, c_2, \ldots, c_m)$ is a cycle in the cycle decomposition of $\mu'$ (we use the convention that a cycle begins with its lowest number), then equation (16) becomes

(17) \begin{equation} {\alpha}_{c_i}^{-1} \cdot {\xi}_{c_i} \cdot {\alpha}_{ c_{i-1}} = g \text{ for all } i \in \{1, 2, \ldots,m\}, \text { where we write } c_0= c_m. \end{equation}

Thus, ${\alpha}_{ c_{m-1} }={\xi}^{-1}_{c_m} \cdot {\alpha}_{c_m} \cdot g$ , and ${\alpha}_{c_{m-2}}= {\xi}^{-1}_{c_{m-1}} \cdot {\xi}^{-1}_{c_m} \cdot {\alpha}_{c_m }\cdot g^2$ , and in general

(18) \begin{equation} {\alpha}_{c_{m-i}}= \left ( \prod_{j=m-i+1}^{m}{{\xi}_{c_j}^{-1}} \right ) \cdot {\alpha}_{c_{m}} \cdot g^i.\end{equation}

When $i=m$ , it follows that ${\alpha}_{c_{m}}= \left ( \prod_{j=1}^{m}{{\xi}_{c_j}^{-1}} \right ) \cdot {\alpha}_{c_{m}} \cdot g^m$ and hence $\left ( \prod_{j=m}^{1}{{\xi}_{c_j} }\right ) ={\alpha}_{c_{m}} \cdot g^m \cdot {\alpha}_{c_{m}}^{-1}$ . Since conjugation preserves order in ${\mathfrak{S}}$ , this proves the implication.

That Item 5.5.2 implies Item 5.5.3 is immediate.

To show that Item 5.5.3 implies Item 5.5.1, suppose $(G,\ell_G) \in Orb (F, \ell_F)$ is self- ${\hat{\gamma}}'= ({\xi}_1, {\xi}_2, \ldots, {\xi}_n)$ via $\mu'=\pi \mu \pi^{-1}$ for some $\pi$ , and that ${\hat{\gamma}}'$ has the property that if $C=(c_1, c_2, \ldots, c_m)$ is a cycle in the cycle decomposition of $\mu'$ , then $ord (\prod_{i=m}^{1} {{\xi}_{c_i}} ) = ord(g ^m)$ .

We observe that we can assume $\mu'=\mu$ , i.e. that we can take $\pi = \iota$ . This follows from Lemma 5.1, which says that we can simply re-order the edges of $(G,\ell_G)$ so that G is self- ${\hat{\gamma}}' \pi$ via $\mu=\mu'$ . We then note that since in $\prod_{i=m}^{1} {{\xi}_{c_i}}$ the indices are from a cycle of $\mu'$ , it follows that $ord (\prod_{i=m}^{1} {{\xi}_{\mu'(c_i})} = ord(\prod_{i=m}^{1} {{\xi}_{c_{i+1}}} ) = ord (\prod_{i=m}^{1} {{\xi}_{c_i}} ) = ord(g ^m)$ .

Thus, Item 5.5.3 implies that there is some $(G,\ell_G) \in Orb (F, \ell_F)$ that is self- ${\hat{\gamma}}'= ({\xi}_1, {\xi}_2, \ldots, {\xi}_n)$ via $\mu'=\mu$ , and that ${\hat{\gamma}}'$ has the property that if $C=(c_1, c_2, \ldots, c_m)$ is a cycle in the cycle decomposition of $\mu'$ , then $ord (\prod_{i=m}^{1} {{\xi}_{c_i}} ) = ord(g ^m)$ .

We will construct ${\hat{\alpha}} \in {\mathfrak{S}}^n$ as follows. Given a cycle C of length m in the cycle decomposition of $\mu'$ , since $ord (\prod_{j=m}^{1} {{\xi}_{c_j}} ) = ord(g ^m)$ , we may use the conjugacies in Table 2 to choose ${\alpha}_{c_m}$ such that $ {\alpha}_{c_{m}} \cdot \left( \prod_{j=m}^{1}{{\xi}_{c_j} }\right ) \cdot {\alpha}_{c_{m}}^{-1} = g^m$ . Then, for $1\leq i < m$ , recursively define ${\alpha}_{c_i}=g^{-1} \cdot {\alpha}_{c_{i+1}} \cdot {\xi}_{i+1}$ . Note that we have ${\alpha}_{c_i}=g^{-(m-1)} \cdot {\alpha}_{c_m} \cdot \left( \prod_{j=m}^{i+1}{{\xi}_{c_j} }\right )$ for $1\leq i < m$ , and also that ${\alpha}_{c_1}=g \cdot {\alpha}_{c_{m}} \cdot {\xi}^{-1}_{1}$ .

Then, for all i, and reading indices of the $c_i$ ’s mod m, we find that

(19) \begin{equation} g= {\alpha}_{c_{i+1}} \cdot {\xi}_{i+1} \cdot {\alpha}^{-1}_{\mu'^{-1}(c_{i+1})}.\end{equation}

We repeat this, choosing some suitable ${\alpha}_{c_m}$ for each cycle of length m in $\mu'$ for all lengths m.

Since equation (19) holds for all entries and $\mu = \mu'$ , it follows that $({\hat{\gamma}}, \mu)=({\hat{\alpha}}, \iota)({\hat{\gamma}}', \mu') ({\hat{\alpha}}, \iota)^{-1}.$

With this, $(H, \ell_H) = ({\hat{\alpha}}, \iota)(G, \ell_G)$ is the desired self-dual, -petrial, -wilsonial, or, respectively, self-trial graph, since then $({\hat{\gamma}}, \mu)(H, \ell_H) = ({\hat{\gamma}}, \mu)({\hat{\alpha}}, \iota)(G, \ell_G) = ({\hat{\alpha}}, \iota)({\hat{\gamma}}', \mu') ({\hat{\alpha}}, \iota)^{-1}({\hat{\alpha}}, \iota)(G, \ell_G) = ({\hat{\alpha}}, \iota)({\hat{\gamma}}', \mu')(G, \ell_G)=({\hat{\alpha}}, \iota)(G, \ell_G)=(H, \ell_H)$ .

Observe that ${\hat{\alpha}}$ , as constructed in the proof of Theorem 5.5 is not uniquely determined, as each cycle of $\mu'$ gives rise to several possibilities. Each of the resulting ${\hat{\alpha}}$ ’s can give a different self-twual graph H, although some of them might possibly be isomorphic to one another.

Theorems 5.3 and 5.5 imply that if we find any graph G that is self- ${\hat{\gamma}}$ via a permutation $\mu$ for any ${\hat{\gamma}}$ and $\mu$ , then we can quickly test for the existence of an ${\hat{\alpha}}$ so that ${\hat{\gamma}} $ has the form ${\hat{\alpha}} {\hat{\gamma}}' ({\hat{\alpha}}^{-1} \mu^{-1})$ for some uniform ${\hat{\gamma}}'$ , and thus identify self-twual graphs in the orbit of G. We will see this in action in the following sections, starting in Section 6 by identifying graphs for which it is reasonable to test for being self- ${\hat{\gamma}}$ for some ${\hat{\gamma}}$ , and then in Section 8 giving a polynomial time algorithm to determine the existence of such an ${\hat{\alpha}}$ .

Note that in the special case that $\mu=\iota$ , Theorems 5.4 and 5.5 reduce to Theorems 5.2 and 5.3, respectively. In the case of Theorem 5.2, we have that ${\hat{\gamma}}'$ is trivial if and only if ${\hat{\gamma}}$ is. However, in Theorem 5.4, if ${\hat{\gamma}} = \textbf{1}$ but $\mu \neq \iota$ then H has a non-trivial automorphism group, with $\mu \in \mbox{Aut}\,\!(H)$ . In this case, it is possible that ${\hat{\gamma}}'$ is non-trivial, which leads to the following theorem and a new strategy for generating self-twual graphs.

Proof. This follows from Theorem 5.4 with ${\hat{\gamma}} = \textbf{1}$ and $\pi = \iota$ , and the observation that $({\hat{\alpha}}^{-1} \mu^{-1})^{-1} = {\hat{\alpha}} \mu^{-1} $ .

Thus, if a graph H has a non-trivial automorphism group, as is the case for example with regular maps, then there is potential for finding self-twual graphs in its orbit by seeking solutions to ${\hat{\gamma}}'= {\hat{\alpha}} \cdot {\hat{\alpha}}^{-1} \mu^{-1}$ for uniform ${\hat{\gamma}}'$ . We give a small example applying Theorem 5.6 in Example 5.7, and use Theorem 5.6 to give an infinite family of graphs that are self-trial but neither self-dual nor self-petrial in Subsection 7.2.

Example 5.7 Let H be the bouquet with six edges shown on the left of Figure 7. Let $\mu$ be the automorphism that rotates H by $120^{\circ}$ . We solve ${\hat{\alpha}} \cdot {\hat{\alpha}}^{-1} \mu^{-1}=\{\delta \tau, \delta \tau,\delta \tau,\delta \tau,\delta \tau,\delta \tau \}$ to get ${\hat{\alpha}} = \{1, 1, \delta \tau, \delta \tau, \tau \delta, \tau \delta\}$ . With this, $(G, \ell_G) = ({\hat{\alpha}}, \iota)(H, \ell_H)$ , shown on the right of Figure 7, is self-trial. Since G has a single loop it cannot be self-petrial, and hence it also cannot be self-dual.

Figure 7.

A graph H (left) with non-trivial automorphism group, and a graph G (right) in its orbit that is self-trial but neither self-dual nor self-petrial.

6. Single vertex orientable ribbon graphs

In this section, we show that the search for self-twual graphs may be reduced to studying the self- ${\hat{\gamma}}$ properties of single-vertex orientable graphs, i.e. orientable embedded bouquets (OEBs). Since, by the results of Section 5, any OEB encodes the twisted duality properties of every graph in its orbit, this provides a new approach for searching for self-dual, self-petrial, self-trial, etc. graphs.

Our next step is to show that every graph has an OEB in its orbit. Thus, OEBs provide representatives of the orbits under the ribbon group action that may be more readily analysed than general graphs.

Proof. We induct on the number of vertices of G. Suppose that $(G,\ell_G)$ has more than one vertex. Since G is connected, it has some non-loop edge, say $\ell_G(i)$ . Define ${\hat{\gamma}}_1\in{\mathfrak{S}}_n$ to have ${\hat{\gamma}}_1(i)=\delta$ and ${\hat{\gamma}}_1(j) = 1$ for $j\neq i$ , and define $(G_1,\ell_G) = ({\hat{\gamma}}_1,\iota)\cdot(G,\ell_G)$ . Note that $G_1$ has one fewer vertex than G does. Iterating this process, we obtain a bouquet $(G_k,\ell_G) = ({\hat{\gamma}}_k,\iota)\cdot\ldots \cdot({\hat{\gamma}}_1,\iota)\cdot(G,\ell_G)$ in the orbit of $(G,\ell_G)$ .

If G is orientable then we are done. If not, then because G has only a single vertex we can unambiguously identify a subset $S =\{ \ell(i_1),\ldots, \ell(i_r) \}$ of edges of $(G_k,\ell_G)$ which are twisted. Defining ${\hat{\gamma}}' \in {\mathfrak{S}}_n$ to have ${\hat{\gamma}}'(i) = \tau$ for $\ell(i)\in S$ and ${\hat{\gamma}}'(i) = \iota$ otherwise, we obtain an OEB $({\hat{\gamma}}',\iota)\cdot(G_k,\ell_G)$ in the orbit of $(G,\ell_G)$ .

We now set the stage for searching for self-twual graphs. We again begin with the special case of being canonically self- ${\hat{\gamma}}$ and canonically self-twual, as here results can be found simply by checking a conjugation table.

Proof. This follows immediately from Theorem 5.2 in the special case that H is an OEB.

The following Theorem 6.3 gives a practical application of Theorem 5.3 to generating all canonically self-twual graphs by confirming that determining the canonically self- ${\hat{\gamma}}$ properties of an OEB indeed captures all possible canonically self-twual graphs in its orbit.

Proof. This follows from Theorem 5.3 by taking $G=F$ , recalling that $Orb(G)=Orb(H)$ for any $H \in Orb(G)$ , and from Proposition 6.1 that tells us that there is always an OEB H in Orb(G).

The following two results are the analogs of Proposition 6.2 and Theorem 6.3 where the twuality is not necessarily canonical. The proofs, which use Theorem 5.5 instead of Theorem 5.3, with some attention to technical details since the ‘conjugation’ for the proof of Theorem 6.5 involves a permutation, are left to the reader.

Proposition 6.4 Suppose H is an OEB that is self- ${\hat{\gamma}}$ for some non-trivial ${\hat{\gamma}}$ , via a permutation $\mu$ . Then every graph in Orb(H) is also self- ${\hat{\gamma}}'$ via $\mu'$ , where ${\hat{\gamma}}'$ is the ‘near-conjugate’

\begin{equation*}{\hat{\gamma}}' = {\hat{\alpha}} \cdot {\hat{\gamma}} \pi^{-1} \cdot {\hat{\alpha}}^{-1} \pi \mu^{-1} \pi^{-1} \end{equation*}

of ${\hat{\gamma}}$ , and $\mu'= \pi \mu \pi^{-1}$ .

Thus, to search for self-twual graphs, we can generate OEBs and test for self- ${\hat{\gamma}}$ properties. If we find an OEB H that is self- ${\hat{\gamma}}$ with the elements ${\hat{\gamma}}$ having the required order properties, we can then just look in the conjugacy table to generate the self-twual graphs in its orbit. If we have exhaustively found all ${\hat{\gamma}}$ such that H is self- ${\hat{\gamma}}$ , then we will be able generate all of the self-twual graphs in its orbit. This process and the algorithm for it are discussed further in Sections 7 and 8.

7. New graphs from old

Here we use the results of the previous sections and a computer search to determine all graphs on up to 7 edges that are self-trial, but neither self-dual nor self petrial. We then apply Theorem 5.6 to generate a new infinite family of self-trial graphs that are neither self-dual nor self-petrial.

We represent a graph $(G,\ell_G)$ as a collection of cyclically ordered tuples $[r_1,r_2,\ldots,r_n]$ , each tuple conveying the information for attaching ribbon-ends to one of the vertices of G. The entries $r_i$ are integers whose absolute value $|r_i|$ is the label of a ribbon and such that $r_i<0$ exactly when ribbon $r_i$ has a twist. Such representations are referred to in Section 8.2 as being in ‘end-label form.’ Further details about the computer implementation are discussed in Section 8.

7.1. All small self-trial graphs

Figure 8 lists a few self- ${\hat{\gamma}}$ OEBs. There are in fact many others for the indicated numbers of ribbons, but these are the ones needed for Figure 9. Figure 9 lists all examples, up to isomorphism, of self-trial, non-self-dual (and hence also non-self-petrial, since $\delta\tau$ and $\tau$ generate ${\mathfrak{S}}$ ) graphs G having n ribbons for $3\leq n\leq 7$ . In each case, these examples arose as $(G,\ell_G) = ({\hat{\alpha}},\iota)(H,\ell_H)$ for multiple self- $({\hat{\gamma}},\pi)$ OEBs $(H,\ell_H)$ , for various $({\hat{\gamma}},\pi)$ , but only one such OEB is listed. The graph G itself is self-trial under the action of $(\boldsymbol{\delta}\boldsymbol{\tau},\sigma)$ for the given element $\sigma$ . Computationally, the list in Figure 9 was constructed by exhaustively running through all possible OEBs with the given number of ribbons, recording an example when it represented an isomorphism class not previously encountered. As discussed in Section 8, by using a well-chosen data structure our setup allows for rapid determination of isomorphism.

Figure 8.

Some self- ${\hat{\gamma}}$ OEBs.

7.2. Examples from Theorem 5.6

We now use Theorem 5.6 to generate an infinite family of graphs that are self-trial but neither self-dual nor self-petrial. This family differs from the infinite family of such graphs given in [Reference Jones and Poulton12] which contains very large regular maps in that this family starts with quite small graphs and the members are not generally regular maps.

Motivating the example below is the observation that twuality acts independently on the components of a one-point join of two graphs. Thus, if G is an OEB, then the one-point join of the three graphs G, $G^{(* \times)}$ , and $G^{(\times *)}$ will automatically be self-trial. The example below is more general, as it is not a one-point join of graphs.

We begin with the OEB $(H_k,\ell_{H_k})$ on 3k untwisted edges $e_1, \ldots, e_{3k}$ , where $e_i=\ell_{H_k}(i)$ , which are attached according to the following (cyclic) pattern:

\begin{equation*}e_2, e_1, e_3, e_2, e_4, e_3, e_5, e_4, \ldots, e_i, e_{i-1}, e_{i+1}, e_i, \ldots, e_{3k}, e_{3k-1}, e_1, e_{3k}.\end{equation*}

Defining ${\hat{\alpha}}$ to be the ribbon group element

$$\hat \alpha = ({\mkern 1mu} \overbrace {{\bf{1}},{\bf{1}}, \ldots ,{\bf{1}}}^{k{\rm{ }} \, times},\overbrace {\delta \tau ,\delta \tau , \ldots ,\delta \tau }^{k{\rm{ }} \, times},\overbrace {\tau \delta ,\tau \delta , \ldots ,\tau \delta }^{k{\rm{ }} \, times}{\mkern 1mu} ),$$

we obtain the graph $({\hat{\alpha}}, \iota)(H_k, \ell_{H_k})$ depicted in Figure 10. Note the labelling of the edge-ends; we will make heavy use of this labelling below.

Figure 9.

Up to isomorphism, all self-trial, non-self-dual graphs on n edges with $3\leq n \leq 7$ . In all cases, we have $G = (\boldsymbol{\delta}\boldsymbol{\tau},\sigma)G$ .

Figure 10.

The graph $({\hat{\alpha}}, \iota)(H_k, \ell_{H_k})$ as described in the text, depicted as an arrow presentation, with potentially multiple vertex discs. For each i the ends of edge $e_i$ are labelled $(i)_a$ and $(i)_b$ , respectively.

Proposition 7.1 The graph $({\hat{\alpha}}, \iota)(H_k, \ell_{H_k})$ depicted in Figure 10 is self-trial but not self-dual.

Proof. Fix k and write $(G, \ell_G)$ for $({\hat{\alpha}}, \iota)(H_k, \ell_{H_k})$ Clearly, the permutation $\mu$ given by $\mu(i) = i+k \!\! \mod 3k$ gives an automorphism of $(H_k, \ell_{H_k})$ . With ${\hat{\alpha}}$ defined as above we have

$$\hat \alpha \cdot{{\hat \alpha }^{ - 1}}{\mu ^{ - 1}} = ({\mkern 1mu} \overbrace {\delta \tau ,\delta \tau , \ldots ,\delta \tau }^{3k{\rm{ }} \, times}{\mkern 1mu} ).$$

Corollary 5.6 thus tells us that the graph $(G, \ell_G)$ is self-trial. To show that $(G,\ell_G)$ is not self-dual it suffices to show that it is not self-petrial, since $\delta\tau$ and $\tau$ generate ${\mathfrak{S}}$ .

The graph $(G,\ell_G)$ has one or more vertices, depicted in Figure 10 as one or more cyclic strings of labeled arrows. We cut these at the tails of the arrows $(k)_b$ , $(k+1)_a$ , $(2k)_a$ , $(3k-1)_a$ , $(3k)_a$ and $(3k)_b$ and at the heads of the arrows $(2k-1)_b$ and $(2k)_b$ , to obtain the following linear ‘strands’, where we use $(i)^{-1}_x$ to indicate that the arrow is traversed backwards in the sequence of the strand.

\begin{align*}S_{k+1,a} & := (k+1)_a \ (k+2)_b^{-1} \ (k+4)_a \ (k+5)_b^{-1} \ (k+7)_a \cdots \\[3pt]S_{k+1,b} & := (k+1)_b^{-1} \ (k+3)_a \ (k+4)_b^{-1} \ (k+6)_a \ (k+7)_b^{-1} \cdots \\[3pt]S_{k,b} & := (k)_b \ (k+2)_a \ (k+3)_b^{-1} \ (k+5)_a \ (k+6)_b^{-1} \ (k+8)_a \cdots \\[3pt]S_{2k-1,b} & := (2k-1)_b^{-1} \ (2k+1)_a \ (2k+3)_a \ (2k+5)_a \ (2k+7)_a \cdots \\[3pt]S_{2k,a} & := (2k)_a \ (2k+1)_b \ (2k+2)_b \ (2k+3)_b \ (2k+4)_b \cdots \\[3pt]S_{2k,b} & := (2k)_b^{-1} \ (2k+2)_a \ (2k+4)_a \ (2k+6)_a \ (2k+8)_a \cdots \\[3pt]S_{3k,a} & := (3k)_a \ (2)_a \ (1)_b \ (3)_a \ (2)_b \ (4)_a \cdots (k-1)_b \\[3pt]S_{3k,b} & := (3k)_b \ (1)_a^{-1} \ (3k-1)_a^{-1}\end{align*}

By construction, these strands account for all edge ends, but the particular sequence of strands found in $(G,\ell_G)$ depends on the value of $k \!\! \mod 6$ . In each case, we provide the simplest argument we could find.

$\bullet$ Case $k \equiv 1 \!\! \mod 6$ . There is one vertex, given by the cyclic concatenation

\begin{equation*}S_{3k,a} \ S_{k+1,a} \ S_{2k,a} \ S_{3k,b} \ S_{2k,b}^{-1} \ S_{k+1,b}^{-1} \ S_{k,b} \ S_{2k-1.b}.\end{equation*}

Since there are 3k loops and k is odd, it is not possible for $(G,\ell_G)$ to have the same number of twisted loops as untwisted loops. Thus $(G,\ell_G)$ is not self petrial in this case.

$\bullet$ Case $k \equiv 5 \!\! \mod 6$ . There is one vertex, given by the cyclic concatenation

\begin{equation*}S_{3k,a} \ S_{k+1,a} \ S_{2k,b} \ S_{3k,b}^{-1} \ S_{2k,a}^{-1} \ S_{k,b}^{-1} \ S_{k+1,b} \ S_{2k-1,b}.\end{equation*}

As for the case $k \equiv 1$ , $(G,\ell_G)$ is not self-petrial in this case.

$\bullet$ Case $k \equiv 2 \!\! \mod 6$ . There are two vertices, given by the cyclic concatenations

\begin{equation*}S_{3k,a} \ S_{k+1,a} \S_{2k,b}\end{equation*}

and

\begin{equation*}S_{k+1,b} \ S_{2k-1,b} \ S_{3k,b}^{-1} \ S_{2k,a}^{-1} \ S_{k,b}^{-1}.\end{equation*}

We have $k = 6m+2$ for some $m>0$ . Let v denote the vertex corresponding to the concatenation $S_{3k,a}S_{k+1,a} \ S_{2k,b}$ and let w denote the other vertex. Note that the only loops on v, namely edges $2,3,4, \ldots, k-1$ , have both their ends in $S_{3k,a}$ , and these are all untwisted. This is a total of $k-2 = 6m$ loops on v. In all, there are 3 additional edges (3k, 1, and k) attached in $S_{3k,a}$ , $2(\frac{k+1}{3})$ attached in $S_{k+1,a}$ , and $\frac{k-1}{2}$ attached in $S_{2k,b}$ . Thus, the number of loops on w is

\begin{equation*}3k - \left[ (k-2)+3 + 2\left(\frac{k+1}{3}\right) + \frac{k-1}{2} \right] \ = \ 5m+1.\end{equation*}

Since the petrial of $(G,\ell_G)$ has a vertex with 6m twisted loops whereas $(G,\ell_G)$ itself does not, we see that $(G,\ell_G)$ is not self-petrial for any $k \equiv 2 \!\! \mod 6$ .

$\bullet$ Case $k \equiv 3 \!\! \mod 6$ . There are two vertices, given by the cyclic concatenations

\begin{equation*}S_{3k,a} \ S_{k+1,a} \ S_{2k-1,b}\end{equation*}

and

\begin{equation*}S_{k+1,b} \ S_{2k,a} \ S_{3k,b} \ S_{2k,b}^{-1} S_{k,b}^{-1}.\end{equation*}

Let $k=6m+3$ for some $m\geq 0$ , let v denote the vertex corresponding to the concatenation $S_{3k,a} \ S_{k+1,a} \ S_{2k-1,b}$ and let w denote the other vertex. As in the case $k \equiv 2$ , the vertex v has $k-2$ loops, all untwisted; in the case $k\equiv 3$ this is $6m+1$ untwisted loops. Also attached to v are additional edges as follows: $(k-2)+3$ attached to $S_{3k,a}$ , $2\frac{k}{3}-1$ attached to $S_{k+1,a}$ , and $\frac{k+1}{2}$ attached to $S_{2k-1,b}$ . The number of loops on w is then

\begin{equation*}3k - \left[ (k-1)+3 + 2\frac{k}{3}-1 + \frac{k+1}{2} \right] \ = \ 5m+2.\end{equation*}

As in the case $k\equiv 2$ , we see that $(G,\ell_G)$ is not self-petrial for any $k \equiv 3 \!\! \mod 6$ .

$\bullet$ Case $k \equiv 0 \!\! \mod 6$ . There is one vertex, given by the cyclic concatenation

\begin{equation*}S_{3k,a} \ S_{k+1,a} \ S_{2k-1,b} \ S_{3k,b}^{-1} \ S_{2k,a}^{-1} \ S_{k+1,b}^{-1} \ S_{k,b} \ S_{2k,b}.\end{equation*}

We will show that, along the single vertex, there is a sequence of length $2k-2$ of consecutive untwisted edge-ends, whereas the longest sequence of consecutive twisted edge ends is at most of length $\frac{4}{3}k-1$ . This discrepancy guarantees that $(G,\ell_G)$ is not self-petrial.

To verify the claim, we proceed as follows. First, note that in strand $S_{3k,a}$ , in the sequence from $(2)_a$ to $(k-1)_b$ , we have both ends of the $k-2$ untwisted loops $2, 3, 4, \ldots, k-1$ as well as $(1)_b$ and $(k)_a$ . The other end of loop 1 is in $S_{3k,b}^{-1}$ , and thus $(1)_b$ is an untwisted edge end, and the other end of loop k is at the beginning of $S_{k,b}$ , and thus $(k)_a$ is also an untwisted edge end. In all, then, we have in $S_{3k,a}$ a total of $2(k-2)+2 = 2k-2$ consecutive untwisted edge ends.

We now bound the length of any sequence of consecutive twisted edge ends. From the discussion above we know that edges 1, 2 and $k-1$ are untwisted. It is also true that edge 2k is untwisted since end $(2k)_a^{-1}$ in $S_{2k,a}^{-1}$ is paired with $(2k)_b^{-1}$ in $S_{2k,b}$ . We use the ends of these edges to break up the cyclic sequence of all edge-ends into five subsequences we denote I, II, III, IV, V as follows:

\begin{equation*}(1)_a \ \mbox{I} \ (2k)_a^{-1} \ \mbox{II} \ (2k)_b^{-1} \ \mbox{III} \ (2)_a \ \mbox{IV} \ (k-1)_a \ \mbox{V} \ (1)_a.\end{equation*}

Of course, any sequence of consecutive twisted edge ends must lie entirely within one of the numbered subsequences other than IV, which has only untwisted edge ends. We can thus complete the proof by determining the lengths of I, II, III and V, respectively, and observing that all are less than $2k-2$ .

1. I. The end $(3k)_b^{-1}$ in $S_{3k,b}^{-1}$ together with the $k-1$ edge-ends of $S_{2k,a}^{-1}$ other than $(2k)_a^{-1}$ yield k edge ends in I.

2. II. The $\frac{2}{3}k -1$ edge-ends from $S_{k+1,b}^{-1}$ together with the $\frac{2}{3}k$ edge-ends from $S_{k,b}$ give $\frac{4}{3}k -1$ edge-ends in II.

3. III. There are a total of $\frac{1}{2}k$ edge-ends in III, namely, $\frac{1}{2}k-1$ edge-ends other than $(2k)_b^{-1}$ from $S_{2k,b}$ , together with $(3k)_a$ in $S_{3k,a}$ .

4. IV. In V there are a total of $\frac{2}{3}k + \frac{1}{2}k$ edge-ends. These are the $\frac{2}{3}k-1$ edge-ends in $S_{k+1,a}$ , the $\frac{1}{2}k$ edge-ends in $S_{2k-1,b}$ , and the edge-end $(3k-1)_a$ in $S_{3k,b}^{-1}$ .

This completes the case when $k\equiv 0 \!\! \mod 6$ .

$\bullet$ Case $k \equiv 4 \!\! \mod 6.$ There is one vertex, given by the cyclic concatenation

\begin{equation*}S_{3k,a} \ S_{k+1,a} \ S_{2k,a} \ S_{3k,b} \ S_{2k-1,b}^{-1} S_{k,b}^{-1} \ S_{k+1,b} \ S_{2k,b}.\end{equation*}

In the case that $k=4$ , the single vertex is given by the cyclic sequence

\begin{equation*}\begin{array}{cccccccccccc}(12)_a & (2)_a & (1)_b & (3)_a & (2)_b & (4)_a & (3)_b & (5)_a & (6)_b^{-1} & (8)_a &(9)_b & (10)_b\\+ & + & - & + & + & - & + & - & + & - & - & + \\ (11)_b & (12)_b & (1)_a^{-1} & (11)_a^{-1} & (9)_a^{-1} & (7)_b & (6)_a^{-1} & (4)_b^{-1} & (5)_b^{-1} & (7)_a & (8)_b^{-1} & (10)_a\\- & + & - & - & - & + & + & - & - & + & - & +\end{array}\end{equation*}

Here, we have indicated under each edge-end whether it belongs to an untwisted edge ( $+$ ) or a twisted edge ( $-$ ). Note that there is exactly one all-“ $+$ ” consecutive subsequence of length three (on ends $(10)_a (12)_a (2)_a$ ), and exactly one all-“ $-$ ” subsequence of length three (on ends $(1)_a^{-1} (11)_a)^{-1} (9)_a^{-1}$ ). Thus, any isomorphism of $(G,\ell_G)$ with its petrial necessarily maps either of these length three subsequences to the other. Considering the surrounding edge-ends, however, even allowing for reversing the orientation, we see this is not possible. The subsequence $++-$ needs to map to $--+$ , whereas the subsequence actually present is $-++$ .

We now address the cases where $k\geq 10$ by analysing the lengths of sequences of consecutive twisted, or consecutive untwisted, edge ends.

• • From $(3)_a$ to $(k-2)_a$ in $S_{3k,a}$ is a length $2k-6$ sequence of consecutive untwisted edges ends.

• • From $(k)_a$ in $S_{3k,a}$ to $(2k)_a$ in $S_{2k,a}$ is a sequence of edge ends alternating between twisted and untwisted which both starts and ends with twisted edges.

• • From $(2k+1)_b$ in $S_{2,a}$ to $(3k)_b$ in $S_{3k,b}$ is a sequence of edge ends alternating between twisted and untwisted which starts with a twisted-edge end and ends with an untwisted-edge end.

• • From $(1)_a^{-1}$ in $S_{3k,b}$ to $(2k+1)_a^{-1}$ in $S_{2k-1,b}^{-1}$ is a length $\frac{1}{2}k+2$ sequence of twisted-edge ends.

• • From $(2k-1)_b$ in $S_{2k-1,b}^{-1}$ to $(k+2)_a^{-1}$ is a length $\frac{2}{3}(k-1)$ sequence of untwisted-edge ends.

• • $(k)_b^{-1} $ in $S_{k,b}^{-1}$ is twisted, and then from $(k+1)_b^{-1}$ in $S_{k+1,b}$ to $(2k)_b^{-1}$ in $S_{2k,b}$ is a sequence of edge ends alternating between twisted and untwisted which starts and ends with a twisted-edge end.

• • from $(2k+2)_a$ in $S_{2k,b}$ to $(3k)_a$ in $S_{3k,a}$ is a length $\frac{1}{2}k$ sequence of untwisted-edge ends.

Since there is a length $2k-6$ sequence of consecutive untwisted edges ends but there is no sequence of consecutive twisted edge ends of that length, we see that $(G,\ell_G)$ cannot be isomorphic to its petrial.

8. Code discussion

In this section, we describe some of the more interesting points involved in developing a computational implementation to make use of the theoretical framework discussed above.

8.7. Finding self-twual graphs

Suppose we are given n-ribbon $(H,\ell_H)$ , ribbon-group element ${\hat{\gamma}}$ and permutation $\mu \in S_n$ such that $({\hat{\gamma}},\mu)(H,\ell_H) \cong (H,\ell_H)$ , and ${\hat{\gamma}}' \in {\mathfrak{S}}^n$ . We want a graph $(G,\ell_G)$ of the form $(G,\ell_G) = ({\hat{\alpha}},\iota)(H,\ell_H)$ , for some ${\hat{\alpha}}\in{\mathfrak{S}}^n$ , which is self- ${\hat{\gamma}}'$ by $\mu$ . By Theorem 5.4, ${\hat{\alpha}}$ must satisfy ${\hat{\alpha}}{\hat{\gamma}}\phi_\mu({\hat{\alpha}}^{-1}) = {\hat{\gamma}}'$ . Since $\phi_\mu$ is a homomorphism, this gives $\phi_\mu({\hat{\alpha}}) = ({\hat{\gamma}}')^{-1}{\hat{\alpha}}{\hat{\gamma}}$ which, in coordinates, says

(20) \begin{equation}(\alpha_{\mu^{-1}(1)}, \alpha_{\mu^{-1}(2)}, \ldots, \alpha_{\mu^{-1}(n)}) \ = \ \left((\gamma^{\prime}_1)^{-1}\alpha_1\gamma_1, (\gamma^{\prime}_2)^{-1}\alpha_2\gamma_2, \ldots, (\gamma^{\prime}_n)^{-1}\alpha_n\gamma_n \right)\end{equation}

We use the following algorithm to find all possible ${\hat{\alpha}}$ : Consider each cycle

\begin{equation*}C = \left(i \; \mu^{-1}(i) \; \mu^{-2}(i) \; \ldots \; \mu^{-r}(i)\right)\end{equation*}

in the cycle decomposition of $\mu$ , and for each C consider each element $a \in {\mathfrak{S}}$ . Assign a to $\alpha_i$ and use equation (20) to iteratively determine $\alpha_{\mu^{-1}(i)}, \alpha_{\mu^{-2}(i)}, \ldots, \alpha_{\mu^{-r}(i)}.$ If the determined value of $\alpha_{\mu^{-r}(i)}$ agrees with a, then we record the computed data as an option for the portion of ${\hat{\alpha}}$ corresponding to cycle C. If each cycle of $\mu$ had at least one computation recorded, assemble all possible ${\hat{\alpha}}$ by choosing, in all possible ways, one of the available options for each portion of ${\hat{\alpha}}$ .

9. Further directions

The work outlined here would be greatly facilitated by a systematic way to study OEBs. In particular, a canonical choice of OEB representative for each orbit would streamline not only computer searches, but the theory of twuality in general.

Also, while we found many examples of Class III graphs, none of the examples given here are canonically self-trial. This raises the question of whether or not canonically self-trial graphs exist.

The results of Section 5 have broader implications than just for the OEBs we used in the examples given here. In particular, the results apply to any H, not just an OEB. Thus, it is possible to take any self-twual graph H and use conjugation to generate others. Numerous examples of various kinds of self-twual graphs are known. It is already known and clear that conjugating by the same group element throughout will yield another self-twual graph. However, the conjugacy table shows that at each edge there is a choice of several elements that can be applied. This opens the potential for many more self-twual graphs arising from any known example. It is then a matter of checking whether the result is isomorphic to the known example, which is easy in the canonical case. Given the wealth of existing information in the literature about regular maps and their automorphism groups, Theorem 5.6 should lead to a rich source of new graphs with desirable self-twuality properties of all kinds.

Another natural direction following from this research is generalising the results from ribbon graphs to delta-matroids, which are to embedded graphs as matroids are to abstract graphs. There are recently developed frameworks extending twuality operations of partial duality and partial Petrie duals to delta-matroids, and the ribbon group action lifted to this setting would open investigation into various forms of self-twuality for delta-matroids. See [Reference Chun, Moffatt, Noble and Rueckriemen3, Reference Chun, Moffatt, Noble and Rueckriemen4].