Using Schur Rings to Produce GRRs for Dihedral Groups

If Γ is a finite group and G a graph such that Aut(G) ≡ Γ acts regularly on V(G), then we say that G is a graphical regular representation (GRR) of Γ. The question asking which finite groups have at least one GRR was an important question in algebraic graph theory and it was completely solved as a result of work done by several researchers. However, it remains a challenge to discern whether a group known to have GRRs has GRRs with specific properties, such as being trivalent. In this paper, we shall be deriving simple conditions on the parameters of a subset of a dihedral group for easily constructing trivalent graphical regular representations (GRR) of the group. Specifically, we shall prove the following:

Let n be an odd integer greater than 5 and let r, s, and t be integers less than n such that the difference of any two of them is relatively prime to n. If 3r – 2s = t (mod n), then Cay(D_n, {ab^r, ab^s, ab^t}) is a GRR of D_n.

We will also be looking at very convenient corollaries of this result. But another main aim of this paper is to show how a simple use of Schur rings can be used to derive such results. This paper therefore also serves as a review of some basic results about Schur rings which we feel should be among the standard armory of an algebraic graph theorist.