Two-fold orbital digraphs and other constructions

Abstract

In this paper we shall present a natural generalisation of orbital graphs. If Γ is a subgroup of Sn×Sn, V and n-set, and (u, v) ∈ V ×V , then the set Γ(u, v) = {(α(u), β(v))|(α, β) ∈ Γ} will be the arc-set of a digraph G with vertex-set V . Such a G will be called a two-fold orbital digraph (TOD). We shall emphasise properties of G which are markedly different from those of orbital graphs, focusing, in particular, on the case when G is disconnected, since this case brings out very sharply differences between orbital graphs and TODs. The close relationship, in this case, between the TOD G and its canonical double covering, is also investigated. The paper contains several examples intended to make these new concepts and results more clear.