Two-fold orbital graphs: II

Raffaele Scapellato (Politecnico di Milano, Italy)

The idea of orbital graphs is perhaps the most fruitful way of associating a graph to a permutation. In the first talk, Lauri has described some of the properties of what we call two-fold orbital graphs/digraphs and which are defined as follows. Let $V=\{1,2,\ldots,n\}$ and let $\alpha,\beta$ be two permutations of $V$. A two-fold orbital graph (TOG) or digraph (TOD) is the orbit of an ordered pair $(i,j)$, $i,j \in V$ under the action which takes $(i,j)$ to $(\alpha(i),\beta(j))$. Extending this idea, given two graphs $G$ and $H$ on $V$ we say that they are two-fold isomorphic if there is a pair $(\alpha,\beta)$ of permutations of $V$ such that $(i,j)$ is an arc of $G$ if and only if $(\alpha(i),\alpha(j))$ is an arc of $H$. Also, the two-fold automorphism group of $G$ is the group of pairs $(\alpha,\beta)$ of permutations of $V$ such that $(i,j)$ is an arc of $G$ if and only if $(\alpha(i),\beta(j))$ is also an arc.

In this talk I will delve more deeply into some of these results. (mainly, the relationship with canonical double covers, about the structure of disconnected TOGs and non-trivial two-fold orbitals of of graphs with trivial automorphism group.

This is joint work with our PhD students Russell Mizzi.