Menu
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(Dn, {abr, abs, abt}) is a GRR of Dn.
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.
Definition 1 (Graphical Regular Representations). Let \(\Gamma\) be a finite group and let \(G\) be a graph. If \(\mbox{Aut}(G) \equiv \Gamma\) acts regularly on \(V(G)\), then we say that \(G\) is a graphical regular representation (GRR) of \(\Gamma\).
The question asking which finite groups have at least one GRR has been completely solved [1-8]. Specifically:
The only abelian groups which have a GRR are \(\mathbb{Z}^n_2\) for \(n\geq5\).
Except for generalised dicyclic groups and a finite number of known groups, all non-abelian groups have a GRR.
However, it remains a challenge to discern whether a group known to have GRRs has GRRs with specific properties, such as being trivalent. It is well-known, by means of Frucht’s Theorem [9], that every group is isomorphic to the automorphism group of some trivalent graph but it is not guaranteed that this graph is a GRR. Furthermore, it is not known how one can easily construct such GRRs when they do exist.
Significant results in this vein are given in [10-12].
Coxeter, Frucht, and Powers had given a thorough treatment of trivalent GRRs in their book Zero-Symmetric Graphs: Trivalent Graphical Representations of Groups [13] which shows how interesting such GRRs can be.
In Section 2 we will be using the foundations laid out in this section to produce infinite families of trivalent GRRs for certain dihedral groups. Our aim is to show that even a simple use of Schur rings can be used to derive results about restricted GRRs. Reference [14] is a very friendly introduction to Schur rings.
Definition 2 (Cayley graphs). The Cayley graph of a group \(\Gamma\) is the graph, denoted by \(\mbox{Cay}(\Gamma, S)\), whose vertex-set is \(\Gamma\) and two vertices \(u\) and \(v\) are adjacent if \(v=us\) where \(s\in S\) and \(S\) is a subset of \(\Gamma\) such that \(1\not\in S\), \(S\) generates \(\Gamma\), and \(S^{-1}=S\). We call the set \(S\) the connecting set of the Cayley graph.
In dealing with Schur rings we might encounter Cayley graphs where the condition \(S^{-1}=S\) is not satisfied. We refer to such graphs as Cayley digraphs.
It is an easy and well-known corollary of Sabidussi’s Theorem [15] that if a graph \(G\) is a GRR of a group \(\Gamma\), then it isomorphic to a Cayley graph \(\mbox{Cay}(\Gamma,S)\) of \(\Gamma\). Therefore, if \(G\) is trivalent then the connecting set must either consist of three elements all of order 2 or else it must consist of one element \(a\) and its inverse \(a^{-1}\not=a\) and one other element \(b\) of order 2.
We now present an introduction to Schur rings which is just sufficient for our purposes.
Definition 3 (Group Rings). Let \(\Gamma\) be a finite group. Then the group ring \(\mathbb{Z}[\Gamma]\) consists of all formal linear combinations \[\sum_{\gamma\in \Gamma} z_\gamma\cdot \gamma\] where each \(z_\gamma\) is in \(\mathbb{Z}\). Addition and multiplication in \(\mathbb{Z}[\Gamma]\) is carried out in the natural way. If \(B=\{b_1,b_2,\ldots,b_p\}\subseteq \Gamma\), then the element \[b_1 + b_2 +\ldots+b_p\] of \(\mathbb{Z}[\Gamma]\) is denoted by \(\overline{B}\) and it is said to be a simple quantity of \(\mathbb{Z}[\Gamma]\).
Definition 4 (Schur Rings). A subring \(\mathcal{S}\) of the group ring \(\mathbb{Z}[\Gamma]\) is called a Schur ring or an \(\mathcal{S}\)-ring over \(\Gamma\), of rank \(r\), if the following conditions hold:
\(\mathcal{S}\) is closed under addition and multiplication including multiplication by elements of \(\mathbb{Z}\) from the left (i.e. \(\mathcal{S}\) is a \(\mathbb{Z}\)-module).
Simple quantities \(\overline{B}_{0},\overline{B}_{1},…,\overline{B}_{r-1}\) exist in \(\mathcal{S}\) such that every element \({C} \in \mathcal{S}\) has a unique representation: \[{C}=\sum_{i=0}^{r-1}\alpha_{i}\overline{B}_{i}\] where the \(\alpha_i\) are integers.
\(\overline{B}_{0}=\overline{\{1\}}\).
\(\displaystyle \sum_{i=0}^{r-1}\overline{B}_{i}=\overline{\Gamma}\), that is, \(\lbrace B_{0},B_{1},…,B_{r-1}\rbrace\) is a partition of \(\Gamma\).
For every \(i\in \lbrace 0,1,2,…,r-1 \rbrace\) there exists a \(j \in \lbrace 0,1,2,…,r-1 \rbrace\) such that \(\overline{B}_{j}=\overline{B}^{-1}_{i} (=\overline{\lbrace b^{-1} : b \in B_{i} \rbrace )}\).
We call the set of simple quantities \(\overline{B}_{0},\overline{B}_{1},\ldots,\overline{B}_{r-1}\)the basis of the Schur ring and we denote it by \({\mathcal B}[{\mathcal S}]\). Each simple quantity \(\overline{B}_i\) of the basis is referred to as a basis element of the Schur ring. Sometimes we need to refer to the set \(B_i\) which we call a basic set. If \(\gamma \in \Gamma\) and \(\overline{\{\gamma\}}\) is a basis element of \(\mathcal{S}\), then we say the \(\gamma\) is isolated or a singleton in \({\mathcal B}[{\mathcal S}]\). If the basis of a Schur ring is completely made up of singletons then we say that the Schur ring is trivial.
We say a Schur ring is larger than another if its basic sets form a partition which is finer than the partition formed by the other’s basic sets. The “largest” Schur ring of a group \(\Gamma\) is therefore the Schur ring whose basic sets form the finest possible partition of \(\Gamma\), that is, the basic sets are all singletons. Similarly, we say a Schur ring is smaller than another if its basic sets form a partition which is coarser than the partition formed by the other’s basic sets. The “smallest” Schur ring is therefore the one which gives the coarsest partition, with basic sets \(\{1\}\) and \(\Gamma – \{1\}\).
The example below deals with a special kind of Schur ring known as a \(\textit{cyclotomic}\) Schur ring [16,17].
Example 1. Let \(\Delta\) be a group of automorphisms of the group \(\Gamma\). Then the orbits of \(\Gamma\) under the action of \(\Delta\) form the basic sets of a Schur ring over \(\Gamma\).
In particular, the conjugacy classes of \(\Gamma\) form the basic sets of a Schur ring over \(\Gamma\). The basis elements in this case would here be the well-known “class sums” which are very important in linear representations of groups.
Because of closure under multiplication, the product of two linear combinations of \(\overline{B}_{0},\overline{B}_{1},…,\overline{B}_{r-1}\) must also be a linear combination of these simple quantities. Therefore we can make the following definition:
Definition 5 (Structure Constants). Let \(\overline{B}_i\) and \(\overline{B}_j\) be two basis elements of an r-rank Schur ring \(\mathcal{S}\). For all values \(i, j, k \in [r]\) there exist non-negative integers \(\beta_{i,j}^{k}\) called structure constants, such that \[\overline{B}_{i}\cdot\overline{B}_{j}=\sum_{k=1}^{r} \beta_{i,j}^{k}\overline{B}_{k}.\]
We shall soon see that the structure constants have a very nice graph theoretic interpretation.
Example 2. Let \(\Gamma\) be the cyclic group \(\langle \gamma: \gamma^8=1\rangle\). The following simple quantities are the basic sets of a Schur ring of \(\Gamma\): \[\{\{1\}, \{\gamma^1,\gamma^5 \}, \{\gamma^3, \gamma^7\}, \{\gamma^2,\gamma^6 \}, \{\gamma^4\} \}.\]
One can verify that, if we let \(B_0=\{1\}, B_1=\{\gamma^1,\gamma^5\}, B_2=\{\gamma^3,\gamma^7\}, B_3=\{\gamma^2,\gamma^6\}\), and \(B_4=\{\gamma^4\}\), then, \(\overline{B_2}\cdot\overline{B_4} = \overline{B_2}\), therefore \(\beta_{2,4}^2=1\) while all the other \(\beta^k_{2,4}=0\).
Definition 6 (Basic Cayley Graphs). Let \(\mathcal{S}\) be a Schur ring of a group \(\Gamma\). We can construct a Cayley (di)graph \(\mbox{Cay}(\Gamma,B_i)\) for each of the basic sets \(B_i\) of \(\mathcal{S}\). These are called the basic Cayley graphs associated with the Schur ring.
The basic Cayley graphs associated with the Schur ring in the previous example are as shown in Figure 1.
We can now give an interpretation to the structure constants \(\beta^k_{i,j}\): pick any edge (or arc in the case of a Cayley digraph) \(ab\) in \(\mbox{Cay}(\Gamma,B_k)\) and count how many walks there are from \(a\) to \(b\) by first passing through an edge/arc in \(\mbox{Cay}(\Gamma,B_i)\) followed by an edge/arc in \(\mbox{Cay}(\Gamma, B_j)\). This is the value of \(\beta^k_{i,j}\).
One can verify here that \(\beta^1_{2,3}=2\) and \(\beta^4_{2,1}=2\), for example.
Basic Cayley graphs such as the ones in Figure 1 can be superimposed on the vertex-set consisting of the elements of \(\Gamma\) with each one having its edges/arcs coloured a different colour. This gives a colouring of the arc-set of the complete graph where the convention is to represent two arcs \((u,v), (v,u)\) which happen to have the same colour represented as an edge of that colour. Figure 2 shows the previous set of basic Cayley graphs without the loops.
As we did above, we can verify here from the colour graph that \(\beta^{red}_{blue,green}=2=\beta^{black}_{blue,red}\), for example.
The adjacency matrices of the basic Cayley (di)graphs form what is called a coherent configuration.
Definition 7 (Automorphisms of Schur Rings). The automorphism group of a Schur ring is defined to be the intersection of all automorphism groups of the basic Cayley graphs of the Schur ring. For any Schur ring \(\mathcal{S}\) we will denote its automorphism group as \(Aut(\mathcal{S})\).
The smallest (coarsest) Schur ring has the largest automorphism group, that is, the symmetric group \(S_n\), where \(n\) is the order of the group. The largest Schur ring has the smallest automorphism group, that is, the regular action of the group on itself.
Let \(C\) be a subset of the group \(\Gamma\). Then \(\langle\langle C \rangle\rangle\) is the smallest (coarsest) Schur ring of \(\Gamma\) containing \(\overline{C}\).
Theorem 1[18] and Theorem 2 [19] will be very important going forward.
Theorem 1. \(\mbox{Aut}(\mbox{Cay}(\Gamma,C))=\mbox{Aut}(\langle\langle C \rangle\rangle )\).
Theorem 2. If \(\langle \langle C \rangle \rangle\) is trivial then \(Cay(\Gamma,C)\) is a GRR of \(\Gamma\).
Our recipe for finding GRRs for a group \(\Gamma\) is simple. Find \(C\) (with \(C \equiv C^{-1}\)) such that \(\langle\langle C \rangle\rangle\) is trivial. Theorem 2 then gives us that since \(\langle \langle C \rangle\rangle\) is trivial then \(\mbox{Cay}(\Gamma,C)\) is a GRR of \(\Gamma\).
Our work in Section 2 is focused on identifying properties of a connecting set of a dihedral group which imply that the Cayley graph of that set must be a GRR. By selecting a connecting set consisting of three elements of order 2, we will also be producing trivalent graphs. One last result about Schur rings will be our main computational tool going forward. A proof is given in [14].
Theorem 3 (Schur-Wielandt Principle). Let \(r=\sum z_\gamma \gamma\) be an element of a Schur ring \(\mathcal{S}\) of a group \(\Gamma\). Then, for any integer \(k\), the sum \(\sum_{z_\gamma=k} \gamma\) is also in \(\mathcal{S}\).
So, this result is saying, for example, that if \(a+2b +c + 3d + 2f\) is in \(\mathcal{S}\), then so are \(a+c\), \(b+f\), and \(d\).
We finish off this section with a concrete example of how we use
these results to show that a particular Cayley graph is a GRR using some
simple GAP [20] code to carry out the algebraic
calculations.
Example 3. Let \(D_7\) be the dihedral group \[\langle a, b: a^2=b^7=abab=1\rangle.\]
We show that \(\mbox{Cay}(D_7, C)\) where \(C = \{a, ab, ab^3, b, b^6\}\) is a GRR of \(G\).
We first define in GAP the group ring \(\mathbb{Z}[D_7]\) of the dihedral group \(D_7\), with \(a, b\) the generators of \(D_7\) defined as elements of the group ring.
gap> d7:=DihedralGroup(14);;
gap> Zd7:=GroupRing(Integers, d7);;
gap> a:=Zd7.1;
(1)*f1
gap> b:=Zd7.2;
(1)*f2We then expand the expression \((a + ab+ ab^3+ +b + b^6)^2\) in \(\mathbb{Z}[D_7]\).
gap> (a+a*b+a*b^3+b+b^6)^2;
(5)*<identity> of ...+
(4)*f1*f2^2+
(2)*f1+(2)*f1*f2+(2)*f2^2+(2)*f1*f2^4+(2)*f2^5+(2)*f1*f2^6+
(1)*f2^3++(1)*f2+(1)*f2^4+(1)*f2^6+By computing \(\overline{C}^2\) in \(\mathbb{Z}[\Gamma]\) and using the Schur-Wielandt Principle, we obtain that \(x= ab^2\) and \(y= a + ab +b^2+ ab^4+ b^5 +ab^6\) are in \(\langle\langle C\rangle\rangle\). Therefore, \(xy =a+b^2+b^4+ab^4+b^5+b^6\) is also in \(\langle\langle C\rangle\rangle\).
But \((xy)^{-1} = a+b^5+b^3+ab^4+ b^2+ b\). Since both \(xy\) and \((xy)^{-1}\) must both be sums of basis elements and basis elements are disjoint, it follow that either \(b\) or \(b+b^3\) is a basis element of \(\langle\langle C \rangle\rangle\). This is because all the other summands in \((xy)^{-1}\) also appear in \(xy\). In the case of the former, it is clear that this implies that every power of \(b^i\) is an isolated element in the basis of the Schur ring. But by squaring the latter, we see that \(b^4\) is a isolated basis element of the Schur ring and since the order of \(b\) is prime, \(b^4\) is a generating element meaning every power of \(b^i\) is an isolated basis element. Therefore we definitely have that all the powers of \(b^i\) are isolated elements in the basis of the Schur ring. Multiplying \(x\) by \(b\) repeatedly it follows that so is \(a\). Therefore \(\mathcal{S}\) is the finest Schur ring on \(D_7\) with all singleton sets as basic sets.
Therefore \(\mbox{Aut}(\mbox{Cay}(D_7,C)) = \mbox{Aut}(\langle\langle C \rangle\rangle) = D_7\).
We finish this section with the following simple observation.
Observation 4. Let \(\overline{A}\) be an element of the Schur ring \(\mathcal{S}\). Then some partition of \(A\) (which could be \(A\) itself) gives a set of basis elements in \(\mathcal{B}[\mathcal{S}]\).
At its core, our work in Section 2 is conceptually identical to the final example in the previous section, but rather than using specific values for the powers of group elements, we generalise the example by using parametric variables.
This will be our main result:
Theorem 5. 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 \bmod n\), then \(\mbox{Cay}(D_n, \{ab^r, ab^s, ab^t\})\) is a GRR of \(D_n\).
Which gives us the tidy corollary:
Corollary 1. Let \(n\) be an odd integer with its smallest prime factor being \(p\) greater than 5 and let \(r\), \(s\), and \(t\) be distinct integers less than \(p\). If \(3r-2s=t \bmod n\) then \(\mbox{Cay}(D_n, \{ab^r, ab^s, ab^t\})\) is a GRR of \(D_n\).
This will allow us to easily make trivalent GRRs for several dihedral groups just by selecting appropriate values for \(r\), \(s\) and \(t\). It will be especially useful for those dihedral groups of order equal to twice a prime greater than 5 (dihedral groups \(D_p\)), where all we would need would be \(r\), \(s\), and \(t\) such that \(3r – 2s = t \bmod p\).
To prove Theorem 5 however, we will need the help of the following two lemmas:
Lemma 1. Let \(\gamma\) be an element of \(\Gamma\) such that \(\gamma\) has odd order \(n\) and let \(r\) and \(t\) be two integers such that \(r-t\) is relatively prime to \(n\). If \(\gamma^r + \gamma^t\) is an element of some \(\mathcal{B}[\mathcal{S}_\Gamma]\) then \(\gamma^s + \gamma^{-s}\) is also an element of that same \(\mathcal{B}[\mathcal{S}_\Gamma]\) for all integers \(s\) relatively prime to \(n\).
Proof. Since \(\mathcal{S}_\Gamma\) is closed then if \((\gamma^r + \gamma^t)\) is in \(\mathcal{S}_{\Gamma}\) so is \((\gamma^r + \gamma^t)^n\). We can use binomial expansion to expand the latter:
\[(\gamma^r+\gamma^ t)^n = \displaystyle\sum_{i=0}^{n}\left[\binom{n}{i}\gamma^{ri}\gamma^{ t(n-i)}\right].\]
This can be re-written as \(\displaystyle\sum_{i=0}^{n}\left[\binom{n}{i}\gamma^{(r- t)i}\right]\gamma^{tn}\). However, \(\gamma\) is of order \(n\) and so \(\gamma^{tn} \equiv 1\). Therefore, the sum can once more be rewritten as \(\displaystyle\sum_{i=0}^{n}\left[\binom{n}{i}\gamma^{(r- t)i}\right]\).
It is well known that if, and only if, \(\gamma\) is the generator of a cyclic group then \(\gamma^k\) where \(k\) is coprime to the order of \(\gamma\) is a generator for the same group and therefore has the same order. Since \(r- t\) is relatively prime to the order of \(\gamma\) then the summation \(\displaystyle\sum_{i=0}^{n}\left[\binom{n}{i}\gamma^{(r- t)i)}\right]\) must include exactly \(n\) distinct terms. In other words every power of \(\gamma^{r-t}\) appears in that sum once and only once. Therefore, the coefficient of every \(\gamma^{(r-t)i}\) is exactly \(\binom{n}{i}\). Moreover, we observe that \(\binom{n}{i} = \binom{n}{n-i}\) and so we can re-write this summation as \(\displaystyle\sum_{i = 0}^{\frac{n-1}{2}}\left[\binom{n}{i}(\gamma^{(r- t)i}+\gamma^{(t-r)i})\right]\).
Since every value of \(\binom{n}{i}\) is unique for \(i \in [0, \frac{n-1}{2}]\) then either \(\gamma^{(r-t)i}\) occurs as a singleton in \(\mathcal{B}[\mathcal{S}_\Gamma]\) or \(\gamma^{(r-t)i}+\gamma^{(t-r)i}\) occurs in \(\mathcal{B}[\mathcal{S}_\Gamma]\) due to the Schur-Wielandt principle.
However, in the cases where \(i\) is relatively prime to \(n\), \((r-t)i\) would also be relatively prime to \(n\), and so \(\gamma^{(r-t)i}\) can generate every power of \(\gamma\). This would mean that, should \(\gamma^{(r-t)i}\) be a singleton element of the basis, then every power of \(\gamma\) would also be a singleton element of the basis. However, \(\gamma^r + \gamma^t\) is an element of \(\mathcal{B}[\mathcal{S}_\Gamma]\), and so this would imply a contradiction. Therefore for every \(i \in [0, \frac{n-1}{2}]\) which is relatively prime to \(n\), we have \(\gamma^{(r-t)i}+\gamma^{(t-r)i} \in \mathcal{B}[\mathcal{S}_\Gamma]\).
Let us recapitulate that at this point we have shown that if \(n\) is the order of some \(\gamma \in \Gamma\), and \(r\) and \(t\) are two integers such that \((r-t)\) is relatively prime to \(n\) and \((\gamma^r + \gamma^t)\) is in \(\mathcal{B}[\mathcal{S}_\Gamma]\) then \(\displaystyle\sum_{i = 0}^{ \frac{n-1}{2} } \left[\binom{n}{i}(\gamma^{(r- t)i}+\gamma^{(t-r)i})\right]\) is in \(\mathcal{S}_{\Gamma}\) and that those pairs of summands of the form \(\gamma^{(r- t)i}+\gamma^{(t-r)i}\) appear as a basis element in \(\mathcal{B}[\mathcal{S}_\Gamma]\) when \(i\) is relatively prime to \(n\). All that is left to show is that every number less than \(n\) which is also relatively prime to it appears in the expression \(\displaystyle\sum_{i = 0;\ i\nmid n}^{\frac{n-1}{2}} \left[\binom{n}{i}(\gamma^{(r- t)i}+\gamma^{(t-r)i})\right]\) as a power of \(\gamma\) (or, equivalently, a value of \((r-t)i\)) and this will complete the proof.
We re-write \(\displaystyle\sum_{i = 0 \ i\nmid n}^{\frac{n-1}{2}}\left[\binom{n}{i}(\gamma^{(r- t)i}+\gamma^{(t-r)i})\right]\) as \(\displaystyle\sum_{j \in S}\left[\binom{n}{j} \gamma^{j}\right]\) where \(S\) is the set \(\{(r-t)i\) mod \(n : i \in [n];\ i \nmid n\}\).
However, we now note that the set \(S\) is in fact equivalent to the set of integers less than \(n\) which also divide \(n\). This is because the modulo multiplication of \([n]\) by any number relatively prime to \(n\) can be represented as a permutation of a set unto itself, which is a bijection. Moreover the product of two numbers both relatively prime to \(n\) is again relatively prime to \(n\), which means the subset of \([n]\) which consists only of integers relatively prime to \(n\) is fixed under such a bijection.
Therefore:
\[\displaystyle\sum_{j \in S}\left[\binom{n}{j} \gamma^{j}\right] \equiv \displaystyle\sum_{j \in [n];\ j \nmid n}\left[\binom{n}{i} \gamma^j\right].\]
Obviously every number less than \(n\) which is less relatively prime to it appears as a power of \(\gamma\) on the right hand side above, meaning that those powers of \(\gamma\) also appear on the left hand side above.
This means that every \(\gamma^{(r-t)i}\) such that \((r-t)i\) is relatively prime to \(n\) appears in the summation \(\displaystyle\sum_{i = 0}^{\frac{n-1}{2}}\left[\binom{n}{i}(\gamma^{(r- t)i}+\gamma^{(t-r)i})\right]\) and as we stated above, this completes the proof. ◻
Lemma 2. Let \(n\) be an odd integer and let \(a\) and \(b\) be the generators of the group \(D_n\) with orders 2 and \(n\) respectively. Also let \(r\), \(s\) and \(t\) be unique integers less than or equal to \(n\). The Schur ring \(\langle\langle ab^r+ab^s+ab^t\rangle\rangle\) must be trivial if the following are true:
\(ab^r+ab^s+ab^t \not \in \mathcal{B}[\langle\langle ab^r+ab^s+ab^t\rangle\rangle ]\)
The absolute value of the difference between any two of \(r\), \(s\) and \(t\) is relatively prime to \(n\).
The sum of any two of \(r\), \(s\) and \(t\) is not equal to twice the third variable taken modulo \(n\).
Proof. We know from (1) that \(ab^r+ab^s+ab^t \not \in \mathcal{B}[\langle\langle ab^r+ab^s+ab^t\rangle\rangle ]\). But \(ab^r+ab^s+ab^t\) is in \(\mathcal{B}[\langle\langle ab^r+ab^s+ab^t\rangle\rangle ]\). This therefore leaves only two possibilities:
\(ab^{r}, ab^{s}, ab^{t}\) are all isolated in \(\mathcal{B}[\langle\langle ab^r+ab^s+ab^t\rangle\rangle ]\), or,
Without loss of generality, \(ab^{r}+ab^{t}\) is in \(\mathcal{B}[\langle\langle ab^r+ab^s+ab^t\rangle\rangle ]\) while \(ab^{s}\) is isolated.
The first possibility implies that \(\langle\langle ab^r+ab^s+ab^t\rangle\rangle\) is trivial. This is because any three involutions of \(D_n\) generate the whole group, and so three isolated elements in the Schur ring’s basis would imply that the whole basis is made up of singletons. So if the first possibility is true, we are done. Let us turn our attention to the second possibility.
This gives us that \((ab^{r}+ab^{t})ab^s\) is in \(\langle\langle ab^r+ab^s+ab^t\rangle\rangle\). By expanding the brackets we get that \(b^{s-r}+b^{s-t}\) is in \(\langle\langle ab^r+ab^s+ab^t\rangle\rangle\). If \(b^{s-r}\) and \(b^{s-t}\) occur as singletons in the basis then it would imply that the whole Schur ring is trivial since \(ab^s\) is already known to be in the basis and \(\{ b^{s-r}, b^{s-t}, ab^s\}\) generates the whole group \(D_n\). Let us assume then that \(b^{s-r}+b^{s-t}\) is in \(\mathcal{B}[\langle\langle ab^r+ab^s+ab^t\rangle\rangle]\), and mark this as Assumption 1.
From the second part of our sufficient condition we also know that \(t-r\) and \(r-s\) are both relatively prime to \(n\). Now \(b^{s-r}+b^{s-t}\) is in \(\mathcal{B}[\langle\langle ab^r+ab^s+ab^t\rangle\rangle ]\) and the difference between the two powers is \(t-r\) which we know is relatively prime to \(n\). Lemma 1 therefore gives us that \(b^{r-s} + b^{s-r}\) must also be in \(\mathcal{B}[\langle\langle ab^r+ab^s+ab^t\rangle\rangle ]\) since \(r-s\) is also relatively prime to \(n\). Both the elements \(b^{s-r}+b^{s-t}\) and \(b^{r-s} + b^{s-r}\) have \(b^{s-r}\) within them, however, and under Assumption 1 these should be basis elements. This is only possible if \(b^{s-t} \equiv b^{r-s}\) and that implies that \(r+t \equiv 2s\) mod \(n\), which contradicts the third part of our sufficient condition.
Hence it must be the case that our Assumption 1 is false and so \(\langle\langle ab^r+ab^s+ab^t\rangle\rangle\) must be trivial. ◻
We can now focus on proving Theorem 5:
Proof of Theorem 5. We will prove Theorem 5 by showing that \(ab^r+ab^s+ab^t\) cannot be an element of \(\mathcal{B}[\langle \langle ab^r+ab^s+ab^t\rangle \rangle]\) and then use Lemma 2 to meet the sufficient conditions of Theorem 2 and so bring about the result.
We substitute \(t\) for \(3r -2s\) at this point for simplicity’s sake. We will begin by assuming that \(ab^r+ab^s+ab^{3r-2s}\) is in \(\mathcal{B}[\langle \langle ab^r+ab^s+ab^{3r-2s}\rangle \rangle]\) and then show how this must imply a contradiction. We label this as (Assumption 2) for further reference.
So let us begin by considering the following statement, which we label as (i) for further reference:
\[(ab^r+ab^s+ab^{3r-2s})^2 = 3(1)+ b^{r-s}+b^{2(r-s)}+b^{3(r-s)}+b^{-(r-s)}+b^{-2(r-s)}+b^{-3(r-s)}.\]
Assuming that (Assumption 2) is true then by Observation 1 it must be possible to express (i) as the sum of elements of \(\mathcal{B}[\langle \langle ab^r+ab^s+ab^{3r-2s}\rangle \rangle]\). However, we shall show that doing so implies a contradiction which means that (Assumption 2) must be false.
We begin by noting that the group elements on the right hand side of (i) must either be isolated in the basis of the Schur ring or be grouped with other elements also on the right hand side of (i).
For the sake of brevity let us denote the sum of the elements on the right hand side as \(B_6\). We note now that \((B_6)^2\) is equal to
\[\begin{aligned} 6(1) + 2B_6 + b^{2(r-s)}+b^{-2(r-s)}+b^{6(r-s)}+b^{-6(r-s)} + \\ 2(b^{r-s}+b^{s-r}+b^{5(r-s)}+b^{-5(r-s)})+3(b^{4(r-s)}+b^{-4(r-s)}). \end{aligned}\]
We notice that the total coefficient of \(b^{r-s}\) on the right hand side is 4 (remember it also occurs in \(B_6\)), and so, by the Schur Wielandt principle the only elements which \(b^{r-s}\) can be grouped with in the Schur ring’s basis must also have a coefficient of 4 in the expansion of \(B_6^2\). However, with the exception of \(b^{s-r}\), achieving this requires that \(\pm 4(r-s), \pm 5(r-s)\) or \(\pm 6(r-s)\) is equal to the power of some element in \(B_6\). This implies \(x(r-s)\) = \(y(r-s)\) for \(x= \pm 1, \pm 2\) or \(\pm 3\) and \(y = \pm 4, \pm 5\) or \(\pm 6\). Regardless of the values of \(x\) and \(y\) we get \(r-s =0\) implies \(r =s\) since we are working in modulo \(n\) where \(n\) is definitely larger than 6. Therefore \(b^{r-s}\) can only possibly be grouped with \(b^{s-r}\) or be an isolated element in the basis.
Let us first consider the possibility that \(b^{r-s}\) is an isolated element. If so, then \(b^{3(s-r)}\) must also be an isolated element in the basis by simply cubing \(b^{r-s}\) . Since our assumption is that \(ab^r+ab^s+ab^{3r-2s}\) is in \(\mathcal{B}[\langle \langle ab^r+ab^s+ab^{3r-2s}\rangle \rangle]\) we can consider the product of \(ab^r+ab^s+ab^{3r-2s}\) and \(b^{3(r-s)}\), which must be in \(\langle \langle ab^r+ab^s+ab^{3r-2s}\rangle \rangle\).
\[(ab^r+ab^s+ab^{3r-2s})b^{3(r-s)} \equiv ab^{4r-3s}+ab^{3r-2s}+ab^{6r-5s}.\]
Note how the term \(ab^{3r-2s}\) appears on the right hand side above. Since we are assuming that \(ab^r+ab^s+ab^{3r-2s}\) is in \(\mathcal{B}[\langle \langle ab^r+ab^s+ab^{3r-2s}\rangle \rangle]\), \(ab^r\) and \(ab^s\) must appear too. There are only two ways this is possible:
\(4r-3s = s\) and \(6r-5s = r\), or,
\(4r-3s = r\) and \(6r-5s = s\).
All the equations above, however, imply that \(r=s\) which is a contradiction. And so \(b^{r-s}\) cannot be an isolated element in the basis without contradicting (Assumption 2). Therefore, the only way to avoid contradicting (Assumption 2) is for \(b^{r-s}+b^{s-r}\) to be an element in the basis.
This gives us that \((ab^r + ab^s + ab^{3r-2s})(b^{r-s}+b^{s-r})\) is in the Schur ring. This expression expands to \(2ab^{2r-s}+ab^{2s-r}+ab^{4r-3s}+ ab^s +ab^r\). Notably the terms \(ab^s, ab^r\) appear here and due to (Assumption 2) this means that \(ab^{3r-2s}\) must appear also. There are three ways this could happen:
\(2r-s=3r-2s\) gives us \(r = s\), or,
\(4r-3s=3r-2s\) gives us \(r = s\), or,
\(2s-r=3r-2s\) gives us \(r = s\).
But all these ways imply \(r=s\) which is again a contradiction. This rules out the possibility that \(b^{r-s}+b^{s-r}\) is an element in the basis.
Therefore, (Assumption 2) must be false and \(ab^r+ab^s+ab^{3r-2s}\) is not in \(\mathcal{B}[\langle \langle ab^r+ab^s+ab^{3r-2s}\rangle \rangle]\) for if it were, then it would be a basis element which cannot be expressed as a linear sum of basis elements when squared, which contradicts the definition of a Schur ring.
Since the relationship \(3r-2s = t\) mod \(n\) excludes the possibility that the sum of any two of \(\{r,s,t\}\) is equal to twice the third, Lemma 2.2 gives us that \(\langle\langle ab^r+ab^s+ab^t\rangle\rangle\) is trivial and so \(\mbox{Aut}(\langle \langle ab^r+ab^s+ab^t \rangle \rangle) \equiv D_n\) meaning that \(\mbox{Cay}(D_n, \{ ab^r,ab^s,ab^t \})\) is a GRR of \(D_n\) by Theorem 2. ◻
Corollary 1 follows immediately by observing that \(r\), \(s\) and \(t\), being less than \(p\), immediately implies that both they and their differences are relatively prime to \(n\). We also note the following theorem, although we invite the reader to read its proof and that of its corollary in a companion paper to this one which is available on arXiv [21] as that proof is very similar to the proof given above.
Theorem 6. 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+s=4t\) mod \(n\), then \(\mbox{Cay}(D_n, \{ab^r, ab^s, ab^t\})\) is a GRR of \(D_n\).
Just as with the prior theorem, Theorem 2.2 has a tidy corollary for prime numbers:
Corollary 2. Let \(n\) be an odd integer with its smallest prime factor being \(p\) greater than 5 and let \(r\), \(s\), and \(t\) be distinct integers less than \(p\). If \(3r+s=4t\) mod \(n\), then \(\mbox{Cay}(D_n, \{ab^r, ab^s, ab^t\})\) is a GRR of \(D_n\).
In the next section we shall give a few examples in which the above results are applied.
We will be focusing on applying Corollary 1 to when \(n\) itself is prime, giving us GRRs of \(D_p\), as this will provide clear and concise examples.
First let us start with \(p =11\). To satisfy the equation \(3r-2s=t\) we will take \(r=3\), \(s=4\) and \(t=1\). Therefore \(Cay(D_{11}, \{ab^3, ab^4, ab\})\) is a GRR of \(D_{11}\). We present the Cayley colour graph for this connecting set in Figure 3 so that the reader can see which element of the connecting set gave rise to which edge: \(ab\) is red, \(ab^3\) is blue and \(ab^4\) is green. These edge-colourings hold true irrespective of which vertex is the identity element of \(D_{11}\) since every automorphism of a GRR only maps edges of the same colour to each other [22].
In the previous example we used the values \(\{ 3, 4, 1 \}\) for the parameters \(\{r, s, t\}\) respectively to construct a GRR for \(D_{11}\). However, with a very simple theorem we can show that these values for \(\{ r, s ,t \}\) can be used to construct GRRs for an infinite number of dihedral groups \(D_p\) where \(p\) is prime.
To do this, we prove the following theorem. Note that all arithmetic in the proof is only modular arithmetic if it is explicitly said to be so, and all order relations are to be understood as an ordering on the positive integers:
Theorem 7. Let \(p_2 > p_1\) be prime. Suppose that, for a given \(\alpha, \beta , \gamma\) there exist integers \(r,s,t\) such that \(\alpha r – \beta s \equiv \gamma t \ mod \ p_1.\) Then, if \(\alpha r – \beta s \in [0, p_1]\) then \(\alpha r – \beta s \equiv \gamma t \ mod \ p_2\) also holds.
Proof. Consider integers \(m,k,x\) such that \(m \equiv k + xp_1\) such that \(k\) is as small an integer as possible. Clearly this statement is equivalent to \(m \equiv k\) mod \(p_1\). If \(x = 0\) then it follows that \(m \equiv k\) mod \(p_2\) also holds.
Now consider \(\alpha r – \beta s \equiv \gamma t\) mod \(p_1\). We can take \(\alpha r – \beta s\) and \(\gamma t\) as \(m\) and \(k\) above (respectively) so that \(\alpha r – \beta s \equiv \gamma t +xp_1\) . If \(\alpha r – \beta s \in [0, p_1]\) then it follows that \(x = 0\) and so \(\alpha r – \beta s \equiv \gamma t\) mod \(p_2\) must hold. ◻
This theorem has a useful corollary:
Corollary 3. Let \(p_2 > p_1\) be prime. Let \(D_{p_1}\) be a dihedral group such that \(D_{p_1} \equiv \langle a,b : a_1^2 \equiv b_1^{p_1} \equiv a_1b_1a_1b_1 \equiv 1 \rangle\). Let \(r,s,t\) be integers which satisfy \(3r – 2s \equiv t \ mod \ p_1\) and therefore let us construct a connecting \(C_1\) set for a GRR of \(D_{p_1}\) where \(C_1 \equiv \{a_1b_1^r, a_1b_1^s, a_1b_1^t\}\). If \(3r-2s \in [0,p_1]\) then those same integers \(r,s,t\) can be used to construct a connecting set \(C_2\) which admits a GRR for \(D_{p_2}\) where \(D_{p_2} \equiv \langle a,b : a_2^2 \equiv b_2^{p_2} \equiv a_2b_2a_2b_2 \equiv 1 \rangle\) and \(C_2 \equiv \{a_2b_2^r, a_2b_2^s, a_2b_2^t\}\).
With this, any solutions for \(r,s,t\) which we find when trying to form a GRR for some dihedral group \(D_{p_1}\) with \(p_1\) prime can be re-used to construct connecting sets for an infinite number of other dihedral groups, specifically those dihedral groups \(D_{p_2}\) where \(p_2 > p_1\) and prime.
Figure 4 is a GRR of \(D_{13}\) which we construct using the same values we found when constructing a GRR for \(D_{11}\) in the previous example.
Below is a table of connecting sets for \(D_p\) for a few prime values of \(p\), found using the equation \(3r-2s = t\) mod \(p\) (see Corollary 1). While constructing these connecting sets, the condition \(3 r – 2 s \in [0, p]\) was respected and so we know from Corollary 3 that all the sets in the table below are in fact connecting sets for GRRs of \(D_p\) not just for the prime number given in its row but for all prime numbers larger than it too.
For brevity we present only the prime numbers up to 100.
| \(p\) | \(r\) | \(s\) | \(t\) | Connecting Set(\( \{ab^r, ab^s, ab^t\}\)) |
| 7 | 2 | 3 | 0 | \( \{ab^2, ab^3, a\}\) |
| 11 | 3 | 4 | 1 | \( \{ab^3, ab^4, ab\}\) |
| 13 | 4 | 6 | 0 | \( \{ab^4, ab^6, a\}\) |
| 17 | 5 | 7 | 1 | \( \{ab^5, ab^7, ab\}\) |
| 19 | 6 | 9 | 0 | \( \{ab^6, ab^9, a\}\) |
| 23 | 7 | 10 | 1 | \( \{ab^7, ab^10, ab\}\) |
| 29 | 9 | 13 | 1 | \( \{ab^9, ab^13, ab\}\) |
| 31 | 10 | 15 | 0 | \(\{ab^10, ab^15, a\}\) |
| 37 | 12 | 18 | 0 | \(\{ab^12, ab^18, a\}\) |
| 41 | 13 | 19 | 1 | \(\{ab^13, ab^19, ab\}\) |
| 43 | 14 | 21 | 0 | \(\{ab^14, ab^21, a\}\) |
| 47 | 15 | 22 | 1 | \(\{ab^15, ab^22, ab\}\) |
| 53 | 17 | 25 | 1 | \(\{ab^17, ab^25, ab\}\) |
| 59 | 19 | 28 | 1 | \(\{ab^19, ab^28, ab\}\) |
| 61 | 20 | 30 | 0 | \(\{ab^20, ab^30, a\}\) |
| 67 | 22 | 33 | 0 | \(\{ab^22, ab^38, a\}\) |
| 71 | 23 | 34 | 1 | \(\{ab^23, ab^34, ab\}\) |
| 73 | 24 | 36 | 0 | \(\{ab^24, ab^36, a\}\) |
| 79 | 26 | 39 | 0 | \(\{ab^26, ab^39, a\}\) |
| 83 | 27 | 40 | 1 | \(\{ab^27, ab^40, ab\}\) |
| 89 | 29 | 43 | 1 | \(\{ab^29, ab^43, ab\}\) |
| 97 | 32 | 48 | 0 | \(\{ab^32, ab^48, a\}\) |
By making use of a few theorems and lemmas about Schur rings we have shown easy ways to construct trivalent GRRs for dihedral groups \(D_n\) where \(n\) is an odd number. It is the opinion of the authors that these results are evidence that even a basic study of Schur rings can be fruitful not only in the search for GRRs but also in other areas of algebraic graph theory.
We are now in a position where we can produce two GRRs for each member of an infinite family of dihedral groups within moments. For example, \(\{a, ab^2, ab^3 \}\) and \(\{a, ab^3, ab^4 \}\) are connecting sets for GRRs of all \(D_n\) where \(n\) is prime and larger than 11, by using Corollaries 1, 2 and 3.
This can be the groundwork for several further lines of inquiry. For example, are the methods we have outlined sufficient to find all possible trivalent GRRs for the relevant dihedral groups? If no, can we perhaps find a similar approach to account for the remaining ones? If yes, can these methods be used as groundwork for enumeration theorems?
Moreover, the methods we have described here can be expanded to find GRRs for dihedral groups with a valency greater than 3 and we can also slightly relax the conditions on the parameter \(n\). This is all to be discussed another time, however.
These lines of inquiry we have outlined may yet yield further useful results.
The authors declare no conflict of interest.