A new class of directed strongly regular Cayley graphs over dicyclic groups

1.   Introduction

The directed strongly regular graph (or DSRG for short) is a potential generalization of the well-established strongly regular graphs. It was introduced by Duval in ^[4] in 1988. Although it has received less attention compared to its undirected counterparts, DSRGs have gained popularity in recent years.

A DSRG can be interpreted in the framework of adjacency matrices. The adjacency matrix of a directed graph $X$ of order $n$ is denoted by $A = A(X) = (a_{ij})_{n \times n}$. We employ the notation $I = I_n$ and $J = J_n$ to represent the identity matrix and all-one matrix of size $n$, respectively. A directed graph $X$ is a DSRG with parameters $(n, k, \mu, \lambda, t)$ if and only if it satisfies:

(ⅰ) $JA = AJ = kJ$,

(ⅱ) $A^2 = tI+\lambda A+\mu(J-I-A).$

When $t = k$, $X$ becomes undirected strongly regular graph. Duval ^[4] demonstrated that DSRGs with $t = 0$ correspond to the doubly regular tournaments. Consequently, it is customary to assume that $0 < t < k$.

From history, many infinite families of DSRGs were constructed in light of several parameters of DSRGs as well as some sporadic examples. Despite the extensive literature on the existence, structure, and construction of DSRGs for various parameter values ^[8,10], a significant number of DSRGs remain shrouded in mystery, with their existence yet to be determined. In fact, it is a challenging problem for the complete characterization of DSRGs. By using representation theory as a powerful tool, He and Zhang ^[6] obtained a large family of DSRGs on dihedral groups, which extended certain findings presented in ^[10]. S. Hayat, J. H. Koolen and M. Riaz gave a similar conclusion for undirected strongly regular graphs in ^[5]. For more results, one may refer to ^[1,9].

Our objective is to derive novel infinite families of DSRGs. Inspired by the methodology outlined in ^[6], we explore directed strongly regular Cayley graphs derived from $\operatorname{Dic}_{4n}$, where $n$ is odd. As previously noted in^[3], the dicyclic group exhibits a distinct nature compared to the dihedral group. Consequently, it would be intriguing to investigate the potential applications of this group.

This paper is structured as follows. Initially, we introduce several classes of directed strongly regular Cayley graphs (or DSRCGs for short) over dicyclic groups. Subsequently, we provide a criterion for the Cayley graph $\mathcal{C}(\operatorname{Dic}_{4n}, M\cup Mb\cup Mb^2\cup Mb^3)$ with $M\cap M^{(-1)} = \emptyset$ to be directed strongly regular.

2.   Preliminaries

For comprehensive insights into representation theory and associated concepts, we follow ^[7].

Let $G$ be a finite group. We denote by ${\rm IRR}(G)$ (resp. ${\rm Irr}(G)$) the set of all non-equivalent irreducible representations (resp. irreducible characters) of $G$. Our subsequent discussion needs the characters associated with cyclic groups.

Lemma 2.1 (^[7]). For a cyclic group $C_n = \langle \nu\rangle$ of order $n$, ${\rm IRR}(C_n) = \{\ell_s\; |\; 0\leq s\leq n-1\}$, with $\ell_s(\nu^k) = \omega_n^{sk}$ $(0\leq s, k\leq n-1)$, where $\omega_n = e^{\frac{2\pi i}{n}}$ represents the $n$-th primitive root of unity.

We denote the group algebra of a group $G$ over the complex field $\mathbb{C}$ as $\mathbb{C}G$. It contains all formal sums of the form $\sum_{g\in G}m_gg$, where $m_g\in\mathbb{C}$. The multiplication is defined as:

Lemma 2.2. ^[7] For an element $\mathcal A = \sum_{g\in G}m_gg\in\mathbb{C}G$ with $G$ being abelian group, we have

We now introduce some notations regarding multisets. Let $\mathcal A$ represent a multiset characterized by a multiplicity function, denoted as $\delta_{\mathcal A}:S\rightarrow \mathbb{N}$. Here, $\delta_{\mathcal A}(x)$ denotes the frequency of occurrence of $x$ in ${\mathcal A}$. We define $x$ is an element of $\mathcal A$ (i.e., $x\in {\mathcal A}$) if and only if the multiplicity of $x$, as determined by $\delta_{\mathcal A}(x)$, is greater than zero. For two multisets ${\mathcal A}$ and ${\mathcal B}$, with multiplicity functions $\delta_{\mathcal A}$ and $\delta_{\mathcal B}$, respectively, their union, represented as $\mathcal A\uplus \mathcal B$, is determined by the function $\delta_{\mathcal A\uplus \mathcal B} = \delta_{\mathcal A}+\delta_{\mathcal B}.$ For instance, consider $\mathcal A = \{1, 1, 2, 3\}$, and $\mathcal B = \{1, 2, 3, 3, 4, \}$, then the union $\mathcal A\uplus \mathcal B = \{1, 1, 1, 2, 2, 3, 3, 3, 4\}$.

Let $\overline{\mathcal X}$ be an element in $\mathbb{C}G$ corresponding to any multisubset $\mathcal X$ of the group $G$. $\overline{\mathcal X}$ may be expressed as

Let $\mathcal S$ be a non-empty subset of a finite group $G.$ We denote the set $\{s^{-1}\mid s\in \mathcal S\}$ as $\mathcal S^{(-1)}$. If $\mathcal S\cap \mathcal S^{(-1)} = \emptyset$, then it is called antisymmetric. Let us assume that the identity element $e\notin \mathcal S$. In this case, the graph $\Gamma = \mathcal{C}(G, \mathcal S)$ is a directed Cayley graph, its vertex set is $V(\Gamma) = G$, and there is an arc from $x$ to $y$, represented by $x\rightarrow y$, if $yx^{-1}\in \mathcal S$.

Utilizing the group algebra, the lemma presented below establishes a criterion for a Cayley graph to be DSRG.

Lemma 2.3. ^[4] $\mathcal{C}(G, \mathcal S)$ is a DSRG with parameters $(n, k, \mu, \lambda, t)$ if and only if $|G| = n,$ $|\mathcal S| = k$, and

Our primary focus is on a non-abelian group–the dicyclic group. It is denoted as $\operatorname{Dic}_{4n}$, and is typically presented with the following group presentation:

For $n$ odd, let $x^2 = \alpha$ and $y = \beta$. Then, we have

The following relationships will be commonly referenced within the context of our discussion.

Lemma 2.4. Given that $n$ is odd, for the dicyclic group $\operatorname{Dic}_{4n},$ we can observe the following properties:

(ⅰ) $\alpha^{k}\beta = \beta\alpha^{-k};$ $\alpha^{k}\beta^2 = \beta^2\alpha^{k};$ $\alpha^{k}\beta^3 = \beta^3\alpha^{-k};$

(ⅱ) $(\alpha^k\beta)^{-1} = \alpha^{k}\beta^3;$ $(\alpha^k\beta^2)^{-1} = \alpha^{-k}\beta^2.$

Proof: Using (2.1), the conclusions are immediate.

3.   DSRCGs over $\operatorname{Dic}_{4n}$

We aim to present various constructions of DSRCGs derived over $\operatorname{Dic}_{4n}$, with $n$ being an odd integer.

Any subset $S$ of $\operatorname{Dic}_{4n}$ can be expressed as $S = S_0\cup S_1b\cup S_2b^2\cup S_3b^3$ with $S_0, S_1, S_2, S_3\subseteq C_n$. Our first main result is:

Theorem 3.1. $\Gamma = \mathcal{C}(\operatorname{Dic}_{4n}, S_0\cup S_1b\cup S_2b^2\cup S_3b^3)$ is a DSRG with parameters $(4n, |S_0|+|S_1|+|S_2|+|S_3|), \mu, \lambda, t)$ if and only if the following four statements hold:

(ⅰ) $\overline{S_0}^2+\overline{S_1}\; \overline{S_3^{(-1)}}+\overline{S_2}^2+\overline{S_3}\; \overline{S_1^{(-1)}} = (t-\mu)e+(\lambda-\mu)\overline{S_0}+\mu\overline{C_n};$

(ⅱ) $\overline{S_0}\; \overline{S_1}+\overline{S_1}\; \overline{S_0^{(-1)}}+\overline{S_2}\; \overline{S_3}+\overline{S_3}\; \overline{S_2^{(-1)}} = (\lambda-\mu)\overline{S_1}+\mu\overline{C_n};$

(ⅲ) $2\overline{S_0}\; \overline{S_2}+\overline{S_1}\; \overline{S_1^{(-1)}}+\overline{S_3}\; \overline{S_3^{(-1)}} = (\lambda-\mu)\overline{S_2}+\mu\overline{C_n};$

(ⅳ) $\overline{S_0}\; \overline{S_3}+\overline{S_1}\; \overline{S_2^{(-1)}}+\overline{S_2}\; \overline{S_1}+\overline{S_3}\; \overline{S_0^{(-1)}} = (\lambda-\mu)\overline{S_3}+\mu\overline{C_n}.$

Proof: According to Lemma 2.4, the following holds:

From Lemma 2.3, the Cayley graph $\Gamma = \mathcal{C}(\operatorname{Dic}_{4n}, S_0\cup S_1b\cup S_2b^2\cup S_3b^3)$ is recognized as a DSRG with parameters $(4n, |S_0|+|S_1|+|S_2|+|S_3|), \mu, \lambda, t)$ if and only if

From the above two equations, we complete the proof.

Let $S_0 = S_2 = M$ and $S_1 = S_3 = N$ in Theorem 3.1, then we have:

Theorem 3.2. $\Gamma = \mathcal{C}(\operatorname{Dic}_{4n}, M\cup Nb\cup Mb^2\cup Nb^3)$ is a DSRG with parameters $(4n, 2(|M|+|N|), \mu, \lambda, t)$ if and only if the following two conditions hold for $t = \mu$ and $M$, $N$:

(ⅰ) $2\left (\overline{M}^2+\overline{N} \; \overline{N^{(-1)}} \right) = (\lambda-\mu)\overline{M}+\mu\overline{C_n}$;

(ⅱ) $2\overline{N}\left (\overline{M}+\overline{M^{(-1)}} \right) = (\lambda-\mu)\overline{N}+\mu\overline{C_n}.$

Proof: As $S_0 = S_2 = M$ and $S_1 = S_3 = N$, from (i), (iii) of Theorem 3.1, we derive

and

Therefore, comparing the above two equations, we have $t = \mu$ and $2\left(\overline{M}^2+\overline{N}\overline{N^{(-1)}} \right) = (\lambda-\mu)\overline{M}+\mu\overline{C_n}.$

Similarly, as $S_0 = S_2 = M$ and $S_1 = S_3 = N$, from (ⅱ), (ⅳ) of Theorem 3.1, we have $2\overline{N}\left (\overline{M}+\overline{M^{(-1)}}\right) = (\lambda-\mu)\overline{N}+\mu\overline{C_n}.$

This completes the proof.

Setting $N = M$ in Theorem 3.2, we have:

Theorem 3.3. $\mathcal{C}(\operatorname{Dic}_{4n}, M\cup Mb\cup Mb^2\cup Mb^3)$ is a DSRG with parameters $(4n, 4|M|, \mu, \lambda, t)$ if and only if the following two conditions hold for $t, \mu$ and $M$:

(ⅰ) $t = \mu;$

(ⅱ) $2\overline{M} \left (\overline{M}+\overline{M^{(-1)}} \right) = (\lambda-\mu)\overline{M}+\mu\overline{C_n}.$

Remark 3.1. Theorem 3.3 (ii) also implied that

Thus, by Theorem 3.3 (ⅱ) and Remark 3.1, we derive

Next, we can get several classes of DSRGs from the above results.

Corollary 3.1. For an odd number $n$, suppose that the two conditions hold for $M, N\subseteq C_n$:

(ⅰ) $\overline{M}+\overline{M^{(-1)}} = \overline{C_n}-e;$

(ⅱ) $\overline{N}\; \overline{N^{(-1)}}-\overline{M}\; \overline{M^{(-1)}} = \varepsilon\overline{C_n}, \quad \varepsilon = 0$ or 1.

Then, $\Gamma = \mathcal{C}(\operatorname{Dic}_{4n}, M\cup Nb\cup Mb^2\cup Nb^3)$ is a DSRG with parameters $(4n, 2n-2+2\varepsilon, n-1+2\varepsilon, n-3+2\varepsilon, n-1+2\varepsilon)$.

Furthermore, if $M$ satisfies ($i$), and $N = Mh$ or $N = M^{(-1)}h$ for $h\in C_n$, then $\Gamma$ is a DSRG with parameters $(4n, 2n-2, n-1, n-3, n-1).$

Proof: By (i), we have $|M| = \frac{n-1}{2}$. By (ii), we have $|N|^2 = |M|^2+\varepsilon n = (|M|+\varepsilon)^2$, because $\varepsilon = 0$ or 1, and $|M| = \frac{n-1}{2}$. Thus, we obtain $|N| = |M|+\varepsilon = \frac{n-1}{2}+\varepsilon.$ By (ⅰ) and (ⅱ), we obtain:

and

Therefore, the desired result is obtained through Theorem 3.2.

In the following, we denote $l = \frac{n}{v}$ where $v \; |\; n$. Given that $\langle a^v\rangle$ is a subgroup of $C_n$, a corresponding transversal within $C_n$ consists of the elements $\{e, a, a^2, \cdots, a^{v-1}\}$. Let $T\subseteq \{e, a, a^2, \cdots, a^{v-1}\}$ as a subset. We define:

where $a^t\langle a^v\rangle$ are coset of $\langle a\rangle$ in $C_n$, for $a^t\in T.$ Then we have:

Corollary 3.2. Let $T\subseteq \{e, a, a^2, \cdots, a^{v-1}\}$ as a subset, with $v \mid n$, and the following two conditions hold for $M, N\subseteq C_n$:

(ⅰ) $N = T\langle a^v\rangle = M\cup\langle a^v\rangle;$

(ⅱ) $N\biguplus N^{(-1)} = C_n\biguplus\langle a^v\rangle.$

Then, $\Gamma = \mathcal{C}(\operatorname{Dic}_{4n}, M\cup Nb\cup Mb^2\cup Nb^3)$ is a DSRG with parameters $(4n, 2n, n+l, n-l, n+l)$.

Proof: According to (i) and (ii), we derive $|N| = |M|+l = \frac{n+l}{2}$, and $\overline{M}+\overline{M^{(-1)}} = \overline{C_n}-\overline{\langle a^v\rangle}.$ Therefore,

and

Therefore, the result is obtained through Theorem 3.2.

Corollary 3.3. Let $T\subseteq \{e, a, a^2, \cdots, a^{v-1}\}$ be a subset, with $v \mid n$. Assume that the following conditions hold for $M\subseteq C_n$:

(ⅰ) $M = T\langle a^v\rangle;$

(ⅱ) $M\cup M^{(-1)} = C_n\setminus\langle a^v\rangle.$

Then, $\Gamma = \mathcal{C}(\operatorname{Dic}_{4n}, M\cup Mb\cup Mb^2\cup Mb^3)$ is a DSRG with parameters $(4n, 4|M|, n-l, n-3l, n-l)$.

Proof: According to (i) and (ii), we derive

By Theorem 3.3, we obtain the result.

Remark 3.2. If $\Gamma = \mathcal{C}(\operatorname{Dic}_{4n}, M\cup Mb\cup Mb^2\cup Mb^3)$ is a DSRG in Corollary 3.3, then we derive $M\cap M^{(-1)} = \emptyset.$

Now, we give an example to illustrate our results, whose parameters are listed in ^[2].

Example 3.1. Let $\operatorname{Dic}_{36} = \langle a, b\; |\; a^{9} = b^4 = 1, b^{-1}ab = a^{-1}\rangle$ be the dicyclic group of order 36 and $\upsilon = 3$, then $l = \frac{9}{3} = 3$ and $\langle a^3\rangle = \{e, a^3, a^6\}$. Let $T = \{a^2\}\subseteq \{e, a, a^2\}$. Then, we have $M = \{a^2\}\langle a^3\rangle = \{a, a^4, a^7\}$ and $M^{(-1)} = \{a^2, a^5, a^8\}$. Thus, $M\cup M^{(-1)} = \{a, a^2, a^4, a^5, a^7, a^8\} = C_9\setminus\langle a^3\rangle$ satisfies the condition of Corollary 3.3. By direct computation, we have

where $\overline{\mathcal S} = \overline{M}\cup \overline{Mb}\cup \overline{Mb^2}\cup\overline{ Mb^3}.$ Therefore, by Lemma 2.3, we have $\Gamma = \mathcal{C}(\operatorname{Dic}_{36}, M\cup Mb\cup Mb^2\cup Mb^3)$ is a DSRG with parameters $(36, 12, 6, 0, 6)$.

Suppose that $M\cap M^{(-1)} = \emptyset,$ i.e., $M$ is an antisymmetric subset of $C_n$. We end this paper with a criterion for certain Cayley graph to be a DSRG.

Theorem 3.4. $\Gamma = \mathcal{C}(\operatorname{Dic}_{4n}, M\cup Mb\cup Mb^2\cup Mb^3)$ with $M\cap M^{(-1)} = \emptyset$ is a DSRG with parameters $(4n, 4|M|, \mu, \lambda, t)$ if and only if the following conditions hold for a subset $T$ of $\{a, a^2, \cdots, a^{v-1}\}$:

(ⅰ) $M = T\langle a^v\rangle;$

(ⅱ) $M\cup M^{(-1)} = C_n\setminus\langle a^v\rangle,$ where $v = \frac{2n}{\mu-\lambda}$ is an odd positive integer.

Proof: Let $W = M\cup M^{(-1)} \subseteq C_n$. Then, $\delta_W(h) = 0$ or $1$ for any $h\in W$. Hence, $\overline{W} = \overline{M}+\overline{M^{(-1)}}$. By Corollary 3.3, if $\Gamma = \mathcal{C}(\operatorname{Dic}_{4n}, M\cup Mb\cup Mb^2\cup Mb^3)$ satisfying (i) and (ii) is a DSRG, then $M\cap M^{(-1)} = \emptyset.$

Now, we consider the converse part. Suppose that $\Gamma = \mathcal{C}(\operatorname{Dic}_{4n}, M\cup Mb\cup Mb^2\cup Mb^3)$ is a DSRG with parameters $(4n, 4|M|, \mu, \lambda, t),$ where $n$ is odd. By Theorem 3.3 and Remark 3.1, we have

Therefore, we have $\chi(W)\in\{0, \frac{\lambda-\mu}{2}\}$ for any non-principal characters $\chi(W)$ of $C_n$. Now, we define

By Lemma 2.2, we have that

As $e\notin W,$ hence, we obtain $\delta_W(e) = 0$, and therefore,

Then, we have $4|M| = (\mu-\lambda)|\mathcal{W}|.$ Thus, the expression (3.2) becomes

By Eq (3.3), we have $|\mathcal{W}|-\sum_{j\in\mathcal{W}}\overline{\chi_j(h)}\in \mathbb{Q}.$ Note that $|\mathcal{W}|-\sum_{j\in\mathcal{W}}\overline{\chi_j(h)}\in \mathbb{Z}[\omega_n]$. Therefore,

By Eq (3.3), we also have

where $j\in\mathcal{W})$. Let $R\overset{\text{def}}{ = }\bigcap_{j\in\mathcal{W}}\mathcal{K}_{\chi_j}$ is some subgroup of $C_n$. Thus, $|R|\big| |C_n|$. Since $|C_n| = n$ is odd, $|R|$ is odd too. Thus, we have $\overline{W} = \overline{C_n}-\overline{R}.$ Moreover,

then, we have $|R| = \frac{\mu-\lambda}{2},$ $n-|R| = \mu$, and $|M| = \frac{n-|R|}{2} = \frac{\mu}{2}.$ Therfore, $R = \langle a^{\frac{2n}{\mu-\lambda}}\rangle = \langle a^v\rangle$. Since $|C_n| = n$ and $|R| = \frac{\mu-\lambda}{2}$ are all odds, we have $\mu = \frac{2n}{\mu-\lambda}$ is odd too. Thus, we proved (ii). In this case, by Theorem 3.3, we have

i.e., $\frac{\mu-\lambda}{2}\overline{M} = \overline{M}\; \overline{\langle a^v\rangle}.$ Thus, we have $M = T\langle a^v\rangle$ for some subset $T$ of $\{a, a^2, \cdots, a^{v-1}\}$; therefore, we proved (ⅰ).

Author contributions

Tao Cheng: conceptualization, writing review and editing, data curation, writing original draft preparation, supervision; Junchao Mao: conceptualization, writing review and editing, investigation, project administration.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors would like to express their gratitude to the referee for his or her careful reading and valuable suggestions. This work was supported by National Natural Science Foundation of China (Grant No. 12271311).

Conflict of interest

The authors declare no conflict of interest.