Two-Fold Orbitals

Abstract

Two-fold automorphisms (or “TF-isomorphisms”) of graphs are a generalisation of automorphisms. Suppose $\alpha ,\beta$ are two permutations of $V=V(G)$ such that for any pair $(u,v)$, $u,v\in V$, $(u,v)$ is an arc of $G$ if and only if $(\alpha (u),\beta (v))$ is an arc of $G$. Such a pair of permutations is called a two-fold automorphism of $G$. These pairs form a group that is called the two-fold automorphism group. Clearly, it contains all the pairs $(\alpha ,\alpha )$ where $\alpha$ is an automorphism of $G$. The two-fold automorphism group of $G$ can be larger than $\text{Aut}(G)$ since it may contain pairs $(\alpha ,\beta )$ with $\alpha \ne \beta$. It is known that when this happens, $\text{Aut}(G)\times {\mathbb{Z}}_2$ is strictly contained in $\text{Aut}(G\times K_2)$. In the literature, when this inclusion is strict, the graph $G$ is called unstable.

Now let $\mathrm{\Gamma }\le S_V\times S_V$. A two-fold orbital (or “TF-orbital”) of $F$ is an orbit of the action $(\alpha ,\beta ):(u,v)\mapsto (\alpha (u),\beta (v))$ for $(\alpha ,\beta )\in \mathrm{\Gamma }$ and $u,v\in V$. Clearly, $\mathrm{\Gamma }$ is a subgroup of the TF-automorphism group of any of its TF-orbitals. We give a short proof of a characterization of TF-orbitals which are disconnected graphs and prove that a similar characterization of TF-orbitals which are digraphs might not be possible. We shall also show that the TF-rank of $\mathrm{\Gamma }$, that is the number of its TF-orbitals, can be equal to $1$ and we shall obtain necessary and sufficient conditions on I for this to happen.