Directed strongly regular graphs were introduced by Duval in 1998 as one of the possible generalization of classical strongly regular graphs to the directed case. Duval also provided several construction methods for directed strongly regular graphs. In this paper, an infinite family of directed strongly regular graphs is constructed, as generalized Cayley graphs.
All graphs considered in this paper will be finite simple directed graphs; so the graphs will have no loops or multiple edges. Let \(\Gamma\) be a directed graph with vertex set \(V(\Gamma)\) and edge set \(E(\Gamma)\). For any \(x,y\in V(\Gamma)\), we say that \(x\) is adjacent to \(y\), denoted by , if there is an edge directed from \(x\) to \(y\), while \(x\nrightarrow y\) means that \(x\) is not adjacent to \(y\). Sometimes, we say that \(x\) is a in-neighbor of \(y\) and \(y\) is a out-neighbor of \(x\) if \(x\rightarrow y\). Let \(\Gamma\) be a graph with \(V(\Gamma)=\{x_1, x_2,…, x_n\}\). The adjacency matrix \(A=A(\Gamma)\) of \(\Gamma\) is the \(n\times n\) matrix whose rows and columns are indexed by the vertices such that \(A_{ij}=1\) if \(x_i\) is adjacent to \(x_j\) and \(A_{ij}=0\) otherwise.
A directed graph is called a directed strongly regular graph with parameters \((n,k,t,\lambda,\mu)\), denoted simply by DSRG\((n,k,t,\lambda,\mu)\), if its adjacency matrix \(A\) satisfies \[AJ=JA=kJ,\] and \[\begin{aligned} \label{0} A^2=tI+\lambda A+\mu(J-I-A), \end{aligned} \tag{1}\] where \(I\) is the identity matrix of order \(n\), and \(J\) is the \(n\times n\) matrix of all \(1\)’s. Thus, each vertex of DSRG\((n,k,t,\lambda,\mu)\) has \(k\) out-neighbors and \(k\) in-neighbors, including \(t\) neighbors counted as both in- and out-neighbors of the vertex. For vertices \(x\neq y\), the number of paths of length two from \(x\) to \(y\) is \(\lambda\) if \(x\rightarrow y\) and \(\mu\) otherwise.
A DSRG with \(t=k\) is an undirected strongly regular graph. A DSRG with \(t=0\) is a graph known as doubly-regular tournament [1]. Thus we will only consider DSRGs with \(0<t<k\) in this paper. Duval proved the following conditions for the existence of a DSRG\((n,k,t,\lambda,\mu)\) with \(0<t<k\). \[\begin{aligned} \label{1} k(k+(\mu-\lambda))=t+(n-1)\mu, \end{aligned} \tag{2}\] \[\begin{aligned} \label{111} (\mu-\lambda)^2+4(t-\mu)=d^2,\ \ d\mid 2k-(\mu-\lambda)(n-1), \end{aligned} \tag{3}\] \[\frac{2k-(\mu-\lambda)(n-1)}{d}\equiv n-1 ({\rm mod} \ 2),\] \[\left|\frac{2k-(\mu-\lambda)(n-1)}{d} \right|\leq n-1,\] where \(d\) is a positive integer, and \[\begin{aligned} \label{2} 0\leq \lambda < t< k, 0<\mu \leq t< k, -2(k-t-1)\leq \mu-\lambda \leq 2(k-t). \end{aligned} \tag{4}\]
The eigenvalues of a DSRG\((n,k,t,\lambda,\mu)\) are \[\begin{aligned} \label{2'} k>\rho=\frac{1}{2}(\lambda-\mu+d)>\sigma=\frac{1}{2}(\lambda-\mu-d), \end{aligned} \tag{5}\] with the multiplicities \[1, \quad -\frac{k+\sigma(n-1)}{\rho-\sigma}, \;\;\mbox{and}\;\;\frac{k+\rho(n-1)}{\rho-\sigma}\] respectively.
Parameter sets satisfying these conditions from Duval’s paper are called feasible. Since there are so many limitations on the possible sets of parameters, directed strongly regular graphs are quite rare. Duval provided an initial list of feasible parameter sets in his paper, but a more complete list is available in [2].
There are numerous construction methods for DSRG. In [1], Duval described some methods including constructions using quadratic residue, block construction of permutation matrices and the Kronecker product. In addition, some of known constructions use combinatorial block designs [9], coherent algebras [9, 17], finite geometries [8, 9, 10, 16], matrices [1, 6, 10], regular tournaments [6, 12], finite incidence structures [3, 19], \(1 \frac{1}{2}\)-designs [4, 7] and Cayley graphs [5, 11, 12, 17].
In addition, non-existence of some directed strongly regular graphs were investigated [8, 12, 13, 14, 15]. From (5), an eigenvalue of a DSRG is \(0\) if and only if \(d\) is \(\mu-\lambda\) or \(\lambda-\mu\), which means that \(t=\mu\) by (3). If \(0\) is an eigenvalue of the adjacency matrix, then the rank of the adjacency matrix is the sum of multiplicities of non-zero eigenvalues, i.e., \(rank=1+\frac{k}{d}\). Thus we define the rank of a feasible parameter set with \(t=\mu\) to be \(1+\frac{k}{d}\) (even if no directed strongly regular graph exists with these parameters). In [13, 15], Jorgensen gave the sufficient and necessary conditions on existence of a directed strongly regular graph with parameters \((n,k,t,\lambda,\mu)\) and with adjacency matrix of rank \(r\leq 5\) based on an enumeration of \(r\times r\) matrices with entries in \(\{0,1\}\). Therefore, some feasible parameters are excluded.
In this paper, we construct an infinite family of DSRGs as generalized Cayley graph. The organization of the paper is as follows. In Section 2, we give the definition of generalized Cayley graphs and a necessary and sufficient condition that makes it easy to check whether a generalized Cayley graph is a DSRG. Section 3 contains some necessary conditions on the existence of DSRGs as generalized Cayley graphs of abelian groups. In Section 4, we construct an infinite family of DSRGs as generalized Cayley graph of dihedral groups.
Hereafter, we will denote the identity element of a group \(G\) by \(e\).
Definition 2.1. Let \(G\) be a finite group and \(A\subseteq G\setminus{e}.\) The Cayley graph of \(G\) generated by \(A\), denoted by \(C(G,A)\), is the digraph \(\Gamma\) such that \(V(\Gamma)=G\) and \(x\rightarrow y\) if and only if \(x^{-1}y\in A\).
Definition 2.2. For any finite group \(G\), the group ring \(\mathbb{Z}[G]\) is defined as the set of all formal sums of elements of \(G\), with coefficients from \(\mathbb{Z}\). The operations \(+\) and \(\cdot\) on \(\mathbb{Z}[G]\) are given by \[\sum_{g\in G}a_gg+\sum_{g\in G}b_gg=\sum_{g\in G}(a_g+b_g)g,\] and \[\left(\sum_{g\in G}a_gg\right)\cdot\left(\sum_{h\in G}b_hh\right)=\sum_{g,h\in G}(a_g\cdot b_h)gh.\]
The group ring \(\mathbb{Z}[G]\) is a ring with multiplicative identity \(e\). For any subset \(X\) of \(G\), we use the same letter \(X\) to denote the element of the group ring \(\mathbb{Z}[G]\) that is the sum of all elements of \(X\), namely \(X=\sum_{x\in X}x.\) The lemma below allows us to express a necessary and sufficient condition for a Cayley graph to be directed strongly regular in terms of the group ring.
Lemma 2.3. [5] The Cayley graph \(C(G,A)\) of \(G\) with respect to \(A\) is a directed strongly regular graph with parameters \((n,k,t,\lambda,\mu)\) if and only if \(|G|=n\), \(|A|=k\), and \[\begin{aligned} \label{4} A^2=te+\lambda A+\mu(G-e-A). \end{aligned} \tag{6}\]
Lemma 2.4. [12] A DSRG\((n,k,t,\lambda,\mu)\) with \(0<t<k\) cannot be a Cayley graph of an abelian group.
Generalized Cayley graphs were introduced by Maru\(\check{\mbox{s}}\)i\(\check{\mbox{c}}\) et al. [18]. The definition is given below.
Definition 2.5. Let \(G\) be a group, \(A\) be a subset of \(G\) and \(\alpha\) be an automorphism of \(G\) such that \(\alpha^2=\epsilon\), the identity automorphism of \(G\). The generalized Cayley graph \(GC(G,A,\alpha)\) of \(G\) with respect to the ordered pair \((A, \alpha)\) is the directed graph with elements of \(G\) as its vertices, and \(x\rightarrow y\) if and only if \(\alpha(x^{-1})y\in A\).
A generalized Cayley graph has the following properties:
Proposition 2.6. [18] Let \(GC(G,A,\alpha)\) be the generalized Cayley graph of \(G\) with respect to the ordered pair \((A, \alpha)\), then
(i) \(GC(G,A,\alpha)\) has no loops if and only if \(\alpha(x^{-1})x \notin A\) for each \(x\in G\),
(ii) \(GC(G,A,\alpha)\) is undirected if and only if \(\alpha(A)=A^{-1}\),
(iii) \(GC(G,A,\alpha)\) is the Cayley graph \(C(G,A)\) by choosing \(\alpha=\epsilon\),
(iv) If \(\alpha\) has order \(2\), then \(GC(G,A,\alpha)\) is connected if and only if \(A\) is a left generating set for \((G, *)\), where \(x*y=\alpha(x)y\) for all \(x,y\in G\).
In (i) of above proposition, \(“\alpha(x^{-1})x \notin A\) for each \(x\in G"\) ensures that \(GC(G,A,\alpha)\) is a simple digraph. Next, we give a necessary and sufficient condition for a generalized Cayley graph to be directed strongly regular in terms of the group ring.
Theorem 2.7. Let \(G\) be a group of order \(n\), \(A\subseteq G\setminus \{\alpha(x^{-1})x \mid x\in G\}\), \(|A|=k\) and \(\alpha\) be an automorphism of \(G\) such that \(\alpha^2=\epsilon\). Then
(i) The generalized Cayley graph \(GC(G,A,\alpha)\) is a DSRG with parameters \((n,k,t,\lambda,\mu)\) and \(\lambda=\mu\) if and only if \[\begin{aligned} \label{3} \alpha(A)\cdot A=(t-\mu)e+\mu G. \end{aligned} \tag{7}\]
(ii) The generalized Cayley graph \(GC(G,A,\alpha)\) is a DSRG with parameters \((n,k,t,\lambda,\mu)\) and \(\lambda\neq \mu\) if and only if \(x^{-1}\alpha(x)A=\{x^{-1}\alpha(x)a| a\in A\}=A\) for every \(x\in G\) and \[\begin{aligned} \label{3'} \alpha(A)\cdot A=(t-\mu)e+(\lambda-\mu) A+\mu G. \end{aligned} \tag{8}\]
Proof. For any vertex \(z\), it is clear that the sets of out-neighbors and in-neighbors of \(z\) are \[\alpha(z)A=\{\alpha(z)a\mid a\in A\}, \ \ \mbox{and}\ \ \alpha(z A^{-1})=\{\alpha(z a^{-1})\mid a\in A\},\] respectively by the definition of the generalized Cayley graph. Let \(x,y \in G\), the number of paths of length \(2\) from \(x\) to \(y\) in \(GC(G,A,\alpha)\) is \(|\alpha(x)A \cap \alpha(y A^{-1})|\). That is the number of ordered pairs \((a_1, a_2)\in A \times A\) such that \(\alpha(x)a_1=\alpha(ya_2^{-1})\), i.e., \(x^{-1}y=\alpha(a_1)a_2\). In other words, it is the coefficient of \(x^{-1}y\) in \(\alpha(A)\cdot A\).
If \(x=y\), then \(x^{-1}y=e\). If \(x\rightarrow y\), then \(y=\alpha(x)a\) and then \(x^{-1}y=x^{-1}\alpha(x)a\) for some \(a\in A\). If \(x\neq y\) and \(x\nrightarrow y\), then \(y\in G \setminus \{\alpha(x)A, x\}\) and thus \(x^{-1}y\in G \setminus \{x^{-1}\alpha(x)A, e\}\). Then by the definition of directed strongly regular graphs, \(GC(G,A,\alpha)\) is a DSRG with parameters \((n,k,t,\lambda,\mu)\) if and only if \(|G|=n\), \(| A|=k,\) and for every \(x\in G\), \[\begin{aligned} \alpha(A)\cdot A &=&te+\lambda x^{-1}\alpha(x)A+\mu(G-e-x^{-1}\alpha(x)A)\\ &=&(t-\mu)e+(\lambda-\mu)x^{-1}\alpha(x)A+\mu G, \end{aligned}\] where \(x^{-1}\alpha(x)A=\{x^{-1}\alpha(x)a| a\in A\}\). This means \(x^{-1}\alpha(x)A=e^{-1}\alpha(e)A=A\) for every \(x\in G\), when \(\lambda\neq\mu\). The result now follows. ◻
Note that Theorem 2.7 is in accordance with Lemma 2.3 when \(\alpha=\epsilon\). In other words, the generalized Cayley graph \(GC(G,A,\alpha)\) is a Cayley graph when \(\alpha=\epsilon\). We only consider the generalized Cayley graph \(GC(G,A,\alpha)\) where the order of \(\alpha\) is \(2\) in the following sections.
Let \(G\) be an abelian group of order \(n\) and \(A\subseteq G\setminus \{\alpha(x^{-1})x \mid x\in G\}\) with \(|A|=k\). It is clear that \(H=\{x^{-1}\alpha(x)\mid x\in G\}\) is a subgroup of \(G\).
Theorem 3.1. Let \(G\) be an abelian group, \(A\subseteq G\setminus \{\alpha(x^{-1})x \mid x\in G\}\) and \(\alpha\) be an automorphism of order \(2\) of \(G\). If the generalized Cayley graph \(GC(G,A,\alpha)\) is a DSRG\((n,k,t,\lambda,\mu)\) with \(0<t<k\), then \(\lambda=\mu\).
Proof. Let \(GC(G,A,\alpha)\) be a DSRG\((n,k,t,\lambda,\mu)\) with \(0<t<k\) and \(\lambda\neq \mu\), then \(x^{-1}\alpha(x)A=A\) for every \(x\in G\) and the equation (7) is satisfied by Theorem 2.7. Let \(Hx\) be the coset containing \(x\) of \(H\) in \(G\). Then \(Ha=H\alpha(a)\subseteq A\) for every \(a\in A\). Thus \(\alpha(A)\subseteq A\). Since \(|A|=|\alpha(A)|=k\), \(\alpha(A)=A\) and the equation (7) becomes (6). This means that the Cayley graph \(C(G,A)\) is a DSRG\((n,k,t,\lambda,\mu)\). It contradicts to Lemma 2.4. Therefore, \(\lambda=\mu\). ◻
Similar to Lemma 2.4, we could rewrite above theorem as follows.
Corollary 3.2. A DSRG\((n,k,t,\lambda,\mu)\) with \(0<t<k\) and \(\mu\ne \lambda\) cannot be a generalized Cayley graph of an abelian group.
Example 3.3 [12] Let \(k, n\) and \(\mu\) be positive integers such that \(k^2-1=n\mu\) and \(\mu\mid (k-1)\), then the automorphism \(\alpha: g \longmapsto g^{-k}\) of \(G\) has order \(2\). Set \(A=\{g,g^2,g^3,\dots,g^k\}\). Then the generalized Cayley graph \(GC(G,A,\alpha)\) is a DSRG\((n,k,\mu+1,\mu,\mu)\).
Let \(D_{2n}=\langle a,b\mid a^n=b^2=1,ab=ba^{-1}\rangle\) be the dihedral group of order \(2n\) generated by \(a\) and \(b\). The every automorphism \(\alpha\) of \(D_{2n}\) has the following format: \(\alpha: a\mapsto a^s,\; b\mapsto a^tb,\) where \((s,n)=1\) and \(1\le t\le n\). Assume that \(n\) is even, \(s=1\) and \(t=\frac{n}{2}\), then \(\alpha\) has order 2.
Theorem 4.1. Let \(G=D_{2n}\) with even \(n\), \(K\subset \mathbb{Z}_n\), \(A=\{a^k,a^kb\mid k\in K\}\), and \(\alpha\) be given by \(s=1\) and \(t=\frac{n}{2}\). Set \(B=(K+K)\cup (K-K+\frac{n}{2})\). Then \(GC(G,A,\alpha)\) is a \((2n,2|K|,t,\lambda,\mu)\)-DSRG, where \(\lambda\neq \mu\), if and only if \(0,\frac{n}{2}\notin K\), \(K\ne -K\), \(K=K+\frac{n}{2}\) and \(B=t\cdot 0+\lambda K+\mu(\mathbb{Z}_n-0-K)\).
Proof. Obviously, for any element \(x=a^ib^j\) in \(G\) we have \[\alpha(x^{-1})x= \begin{cases} e,& \mbox{ if } j=0,\\ a^{\frac{n}{2}},& \mbox{ if } j=1. \end{cases}\]
Therefore, \(GC(G,A,\alpha)\) is a simple graph if and only if \(0,\frac{n}{2}\notin K\). By Theorem 2.7, we need ensure that \(x^{-1}\alpha(x)A=A\) for every \(x\in G\). This means \(K=K+\frac{n}{2}\). Direct calculation gives \(\alpha(A)=\{a^k,a^{k+\frac{n}{2}}b\mid k\in K\}\) and \[\alpha(a^ib^j)a^pb^q= \begin{cases} a^{i+p},& \mbox{ if } j=q=0,\\ a^{i+\frac{n}{2}-p},& \mbox{ if } j=q=1,\\ a^{i+p}b,& \mbox{ if } j=0,\ q=1,\\ a^{i+\frac{n}{2}-p}b,& \mbox{ if } j=1,\ q=0.\\ \end{cases}\]
Thus \(\alpha(A)\cdot A=(t-\mu)e+(\lambda-\mu) A+\mu G\) if and only if \(B=t\cdot 0+\lambda K+\mu(\mathbb{Z}_n-0-K)\). In the end, \(K\ne -K\) ensure that \(GC(G,A,\alpha)\) is a directed graph. ◻
Example 4.2. Let \(n\) be a multiple of \(4\). Set \(K=\{1,2,\cdots,\frac{n}{4},\frac{n}{2}+1,\frac{n}{2}+2,\cdots,\frac{3n}{4}\}\). Then \(GC(G,A,\alpha)\) is a \((2n,n,\frac{n}{2}+2,\frac{n}{2}-2,\frac{n}{2}+2)\)-DSRG.
Exapmle 4.3. Let \(n=2m(2\ell+1)\) with positive integers \(m\) and \(\ell\). Set \(J=\{2\ell+1,2(2\ell+1),\cdots 2m(2\ell+1)=n\}\) and \(K=\cup_{j=1}^\ell(J+j)\). Then \(GC(G,A,\alpha)\) is a \((2n,4m\ell,2m\ell,2m(\ell-1),2m\ell)\)-DSRG.
In future, we will continue the work on the construction of directed strongly regular graphs as generalized Cayley graph, and expect to construct some with new parameters.