Two-fold orbital graphs: I

Josef Lauri (University of Malta, Malta)

The idea of orbital graphs is perhaps the most fruitful way of associating a graph to a permutation. In this paper I shall describe 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 we shall give exact definitions and a few results with the idea of showing that two fold-orbital graphs and digraphs are interesting objects worthy of investigation. In the second paper, Scapellato 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 student Russell Mizzi.