On Generalized Strongly Regular Graphs

Abstract

A generalized strongly regular graph of grade p, as a generalization of strongly regular graphs, is a regular graph such that the number of common neighbours of both any two adjacent vertices and any two non-adjacent vertices takes on p distinct values. In this paper, we study generalized strongly regular graphs of grade 2 and provide some inequalities for the eigenvalues of them. In particular, we investigate a special family of generalized strongly regular graphs of grade 2, i.e., semi-strongly regular graphs. We obtain a relation between the parameters and two inequalities for the eigenvalues of these graphs. We also present some constructions of generalized strongly regular graphs based on Cayley graphs, graph operations and association schemes, respectively.

1 Introduction

Throughout this paper graphs are assumed to be finite and simple.

A k-regular graph on n vertices is called a strongly regular graph with parameters $(n,k,\lambda ,\mu )$, denoted by SRG($n,k,\lambda ,\mu$), if any two adjacent vertices have $\lambda$ common neighbours and any two non-adjacent vertices have $\mu$ common neighbours. We refer the reader to [3, 4] for many beautiful properties of strongly regular graphs.

Erickson et al. [5] and Golightly et al. [8] generalized the concept of strongly regular graphs from distinct perspectives, which are Deza graphs and quasi-strongly regular graphs, respectively. A Deza graph with parameters (n, k, a, b) is a k-regular graph on n vertices and any two distinct vertices have a or b common neighbours. Note that the number of common neighbours of any two distinct vertices does not necessarily depend on the adjacency of the two vertices, which is the only difference between a Deza graph and a strongly regular graph. A quasi-strongly regular graph with parameters $(n,k,a;c_1,c_2,\ldots ,c_p)$ is a k-regular graph on n vertices such that any two adjacent vertices have a common neighbours and any two non-adjacent vertices have $c_i$ common neighbours for some $1\le i\le p$. Thus, a quasi-strongly regular graph with $c_1=c_2=\cdots =c_p$ is strongly regular. In [7], Goldberg studied quasi-strongly regular graphs and explored the properties of those with $p=2$.

In this paper we consider a new generalization of strongly regular graphs, generalized strongly regular graph, which was proposed by Huo and Zhang [10] (one of the authors of this paper). Huo et al. [10] showed that some subconstituents of a family of finite geometric graphs are exactly generalized strongly regular graphs. Here, we will present several families of generalized strongly regular graphs based on other combinatorial objects.

For $1\le i\le p$, let $a_i,c_i$ be non-negative integers, and $a_i\not =a_j$, $c_i\not =c_j$ if $i\not =j$ $(1\le i, j\le p)$. A k-regular graph on n vertices is called a generalized strongly regular graph with parameters (n, k; $a_1,a_2,\ldots ,a_p;c_1,c_2,\ldots ,c_p$), denoted by GSRG(n, k;  $a_1,a_2,\ldots ,a_p;$ $c_1,c_2,\ldots ,c_p$), if

• (i) Any two adjacent vertices have $a_i$ common neighbours and any two non-adjacent vertices have $c_i$ common neighbours for some $1\le i\le p$;

• (ii) For each $1\le i\le p$, there exist two adjacent vertices and two non-adjacent vertices which have exactly $a_i$ and $c_i$ common neighbours, respectively.

A generalized strongly regular graph can be represented in terms of its adjacency matrix. We denote the all-ones matrix by J, the zero matrix by O, and the identity matrix by I. Let G be a k-regular graph on n vertices with adjacency matrix M. Then G is a generalized strongly regular graph if and only if for some distinct integers $a_i$’s and distinct integers $c_i$’s $(i=1,\ldots ,p)$,

$$\begin{aligned} M^2=kI+a_1A_1+a_2A_2+\cdots +a_pA_p+c_1B_1+c_2B_2+\cdots +c_pB_p, \end{aligned}$$

(1)

where $A_i,B_i$ are (0,1)-matrices, $A_i\not =O$, $B_i\not =O$ for all $1\le i \le p$, $A_1+A_2+\cdots +A_p=M$ and $B_1+B_2+\cdots +B_p=J-M-I$.

It is straightforward to show that the complement of a GSRG($n,k;a_1,a_2,$ $\ldots ,$ $a_p;$ $c_1,c_2,\ldots ,c_p$) is also a generalized strongly regular graph with parameters ($n,{\overline{k}};{\overline{a}}_1,{\overline{a}}_2,\ldots ,{\overline{a}}_p;$ ${\overline{c}}_1,{\overline{c}}_2,\ldots ,$ ${\overline{c}}_p$), where

$$\begin{aligned} {\overline{k}}= & {} n-k-1,\\ {\overline{a}}_i= & {} n-2-2k+c_i \,(1\le i\le p),\\ {\overline{c}}_i= & {} n-2k+a_i\,(1\le i\le p). \end{aligned}$$

Therefore, for a GSRG($n,k;a_1,a_2,\ldots ,$ $a_p;$ $c_1,c_2,\ldots ,c_p$), the parameters satisfy $2k-n\le a_i<k$, $2k+2-n\le c_i\le k$.

Note that the number of common neighbours of both two adjacent vertices and two non-adjacent vertices takes on p distinct values in a generalized strongly regular graph. We call p the grade of a generalized strongly regular graph. It is easy to see that a generalized strongly regular graph of grade 1 is strongly regular. In this paper, we specially focus on the generalized strongly regular graphs of grade 2. In particular, we call a GSRG($n,k;a,a+q;c,c+q$) a semi-strongly regular graph with parameters (n, k; a, c; q). Obviously, if a semi-strongly regular graph with parameters (n, k; a, c; q) exists, then q is an integer and satisfies

$$\begin{aligned} \max \,\,\{2k-n-a, 2k+2-n-c,-a,-c\}\le q\le \min \,\,\{k-1-a,k-c\}. \end{aligned}$$

By saying a semi-strongly regular graph with parameters (n, k; a, c; q) we mean that $q\not =0$. In particular, semi-strongly regular graphs with parameters (n, k; a, c;  q) are Deza graphs with parameters $(n,k,a,a+q)$ if $a=c$.

This paper is organized as follows. In Sect. 2, we study the structure of generalized strongly regular graphs of grade 2, and obtain a relation between the parameters of semi-strongly regular graphs. We also obtain some inequalities for the eigenvalues of generalized strongly regular graphs of grade 2. In Sect. 3, generalized strongly regular graphs of arbitrary grade are derived from a Cayley graph. The constructions of generalized strongly regular graphs based on some operations of graphs and association schemes are presented in Sects. 4 and 5, respectively.

2 Generalized Strongly Regular Graphs of Grade 2

In this section, we will restrict our attention to generalized strongly regular graphs of grade 2. Let G be a GSRG$(n,k;a_1,a_2;c_1,c_2)$. Without loss of generality, we assume that $a_1>a_2, c_1> c_2$. Let u be a vertex of G, $s_i(u)$ denote the number of vertices that are adjacent to u and share $a_i$ common neighbours with u, and $t_i(u)$ denote the number of vertices that are non-adjacent to u and share $c_i$ common neighbours with u, for $i=1,2$. Since G is k-regular, the vertex u has k neighbours, and $n-k-1$ non-neighbours.

We will count the total number of edges between the neighbours and non-neighbours of u in two ways. Each of the k neighbours of u is adjacent to u itself, to either $a_1$ or $a_2$ neighbours of u, and thus to either $k-a_1-1$ or $k-a_2-1$ non-neighbours of u. Thus we have a total of $s_1(u)(k-a_1-1)+s_2(u)(k-a_2-1)$ edges. On the other hand, each non-neighbour of u is adjacent to either $c_1$ or $c_2$ neighbours of u. Hence we have a total of $c_1t_1(u)+c_2t_2(u)$ edges. Therefore, we obtain the following linear system of equations.

$$\begin{aligned} \left\{ \begin{array}{l} s_1(u)+s_2(u)=k\\ t_1(u)+t_2(u)=n-k-1\\ s_1(u)(k-a_1-1)+s_2(u)(k-a_2-1)=c_1t_1(u)+c_2t_2(u). \end{array}\right. \end{aligned}$$

(2)

By elementary transformations of (2), we obtain

$$\begin{aligned} \left\{ \begin{array}{l} s_1(u)+s_2(u)=k\\ t_1(u)+t_2(u)=n-k-1\\ (a_2-a_1)s_2(u)+(c_2-c_1) t_2(u)=k(k-a_1-1)-c_1(n-k-1). \end{array}\right. \end{aligned}$$

(3)

From (2) or (3), we can not determine the values of $s_1(u),s_2(u), t_1(u)$ and $t_2(u)$. Indeed, these numbers may depend on the vertex u. For example, the graph $G_0$ shown in Fig. 1 is a GSRG(8,5;3,2;5,4), that is, a semi-strongly regular graph with parameters $(8,5;3,5;-\,1)$. We can easily find that for vertices 1, 2, $s_1(1)=2, s_2(1)=3, t_1(1)=0,t_2(1)=2$, and $s_1(2)=0,s_2(2)=5,t_1(2)=2,t_2(2)=0$, which implies that the numbers $s_1,s_2,t_1$ and $t_2$ are not constant on the vertices of $G_0$. However the numbers $s_1+t_1$ and $s_2+t_2$ in $G_0$ are independent of the choice of the vertex, and satisfy $s_1+t_1=2,$ $s_2+t_2=5$.

Fig. 1

GSRG (8,5;3,2;5,4)

Let $G_s$ be a semi-strongly regular graph with parameters (n, k; a, c; q). Without loss of generality, we suppose that $q<0$. The following theorem shows that both the number $s_1+t_1$ and the number $s_2+t_2$ are constant on the vertices of a semi-strongly regular graph .

Theorem 1

Let $G_s$ be a semi-strongly regular graph with parameters (n, k;  a, c;  q), where $q<0$. Then the numbers

$$\begin{aligned} s_2(u)+t_2(u)=\frac{k(k-a-1)-c(n-k-1)}{q} \end{aligned}$$

and

$$\begin{aligned} s_1(u)+t_1(u)=n-1-(s_2(u)+t_2(u))=\frac{(n-1)(c+q)-k(k-a+c-1)}{q} \end{aligned}$$

do not depend on the choice of u.

The theorem follows immediately from (2) or (3).

Obviously, both $s_1+t_1$ and $s_2+t_2$ must be positive integers. Therefore, Theorem 1 provides some constraints on the parameters of a semi-strongly regular graph. For example, there exist no semi-strongly regular graphs with parameters $(16,8;5,6;-\,3)$. If otherwise, then $s_2+t_2=26/3$, which is impossible.

From Theorem 1, it follows that in a semi-strongly regular graph with parameters (n, k; a, a; q), which is a Deza graph, the numbers

$$\begin{aligned} s_1(u)+t_1(u)=\frac{(n-1)(a+q)-k(k-1)}{q}, \quad s_2(u)+t_2(u)=\frac{k(k-1)-a(n-1)}{q} \end{aligned}$$

are independent of the choice of u. In fact, Erickson et al. [5] show that in a Deza graph with parameters $(n,k,a_1,a_2)$, the number of vertices that share $a_1$ (or $a_2$) common neighbours with a vertex u does not depend on u.

Specially, the numbers $s_1,s_2,t_1$ and $t_2$ in some generalized strongly regular graphs of grade 2 are independent of the choice of the vertex, such as the semi-strongly regular graph with parameters $(9,4;1,3;-\,1)$ shown in Fig. 2, the semi-strongly regular graph with parameters $(24,12;4,12;-\,4)$ derived from Theorem 8 in Sect. 4, the semi-strongly regular graph with parameters $(64,41;30,26;-\,6)$ and the GSRG(64,21;20,2;12,0) derived from Example 1 in Sect. 5.

In the rest of this section we study the eigenvalues of generalized strongly regular graphs of grade 2. Let G be a connected GSRG$(n,k;a_1,a_2;c_1,c_2)$. Let M be the adjacency matrix of G. Then M is real symmetric. Since G is k-regular, it follows that k is a simple eigenvalue of G with eigenvector ${\mathbf {1}}$. Thus any other eigenvectors of G are orthogonal to ${\mathbf {1}}$. Let $\theta$ be an eigenvalue of G and $\theta \not =k$. We obtain two inequalities for $\theta$ in the following theorem.

Theorem 2

Let G be a connected GSRG$(n,k;a_1,a_2;c_2,c_2)$, where $a_1>a_2,$ $c_1>c_2$. Let $\theta \not =k$ be an eigenvalue of G. Then

$$\begin{aligned} \theta ^2&<(a_2-c_2)\theta +k(a_1-a_2+1)+c_1(n-k-1)-c_2(n-k), \end{aligned}$$

(4)

$$\begin{aligned} \theta ^2&>(a_1-c_1)\theta -k(a_1-a_2-1)+c_2(n-k-1)-c_1(n-k). \end{aligned}$$

(5)

Proof

Let M be the adjacency matrix of G. Then from (1), we obtain

$$\begin{aligned} M^2=kI+a_1A_1+a_2A_2+c_1B_1+c_2B_2, \end{aligned}$$

where the (i, j) entry of $A_m(B_m)$ for $m=1,2$ is 1 if the vertices i and j are adjacent (non-adjacent) and share $a_m$ ($c_m$) common neighbours, and 0, otherwise. Hence $A_1+A_2=M$ and $B_1+B_2=J-M-I$.

Therefore, we have

$$\begin{aligned} M^2= & {} kI+a_1A_1+a_2(M-A_1)+c_1B_1+c_2(J-M-I-B_1), \end{aligned}$$

(6)

$$\begin{aligned} M^2= & {} kI+a_1(M-A_2)+a_2A_2+c_1(J-M-I-B_2)+c_2B_2. \end{aligned}$$

(7)

Suppose that a column vector v is a unit eigenvector of M with eigenvalue $\theta \not = k$, and $v^t$ is the transpose of v. From (6) and (7), it follows that

$$\begin{aligned} \theta ^2= & {} k+a_1v^tA_1v+a_2\theta -a_2v^tA_1v+c_1v^tB_1v-c_2\theta -c_2-c_2v^tB_1v \nonumber \\= & {} (a_2-c_2)\theta +k-c_2+(a_1-a_2)v^tA_1v+(c_1-c_2)v^tB_1v \end{aligned}$$

(8)

and

$$\begin{aligned} \theta ^2= & {} k+a_1\theta -a_1v^tA_2v+a_2v^tA_2v-c_1\theta -c_1-c_1v^tB_2v+c_2v^tB_2v \nonumber \\= & {} (a_1-c_1)\theta +k-c_1-(a_1-a_2)v^tA_2v-(c_1-c_2)v^tB_2v. \end{aligned}$$

(9)

Since the Rayleigh–Ritz and the Perron–Frobenius theorems,

$$\begin{aligned} v^tA_mv\le & {} \rho (A_m)<\rho (M)=k, \nonumber \\ v^tB_mv\le & {} \rho (B_m)<\rho (J-M-I)=n-k-1. \end{aligned}$$

(10)

Substituting (10) into (8) and (9), respectively, we have

$$\begin{aligned}&\theta ^2<(a_2-c_2)\theta +k-c_2+(a_1-a_2)k+(c_1-c_2)(n-k-1), \\&\theta ^2>(a_1-c_1)\theta +k-c_1-(a_1-a_2)k-(c_1-c_2)(n-k-1). \end{aligned}$$

The proof is completed. $\square$

Notice that sometimes the inequality (5) is trivial, and provides no new information. For example, let $\lambda$ be an eigenvalue of $G_0$ shown in Fig. 1 and $\lambda \not =5$. It follows from (5) that $\lambda ^2+2\lambda +7>0$. But this holds for every real number $\lambda$. From (4), we have $\lambda ^2+2\lambda -8<0$, so $-\,4<\lambda <2$.

Recall that the numbers $s_1+t_1$ and $s_2+t_2$ do not depend on the choice of the vertex in a semi-strongly regular graph. It is valuable that we consider the eigenvalues of semi-strongly regular graphs.

Theorem 3

Let $G_s$ be a connected semi-strongly regular graph with parameters (n, k; a, c; q), where $q<0$. Let $\theta \not =k$ be an eigenvalue of $G_s$. Then

$$\begin{aligned} \theta ^2\le & {} (a-c)\theta +k(k-a+c)-(c+q)n, \end{aligned}$$

(11)

$$\begin{aligned} \theta ^2\ge & {} (a-c)\theta +k(k-a+c)-cn. \end{aligned}$$

(12)

Proof

We follow the conventions in the proof of Theorem 2. The graph $G_s$ is a GSRG$(n,k;a,a+q;c,c+q)$, where $q<0$. Since $a_1=a$, $a_2=a+q$, $c_1=c$ and $c_2=c+q$, it follows that (8) and (9) can be replaced respectively by

$$\begin{aligned} \theta ^2=(a-c)\theta +k-(c+q)+(-q)v^t(A_1+B_1)v \end{aligned}$$

(13)

and

$$\begin{aligned} \theta ^2=(a-c)\theta +k-c-(-q)v^t(A_2+B_2)v. \end{aligned}$$

(14)

From Theorem 1, the Rayleigh–Ritz and the Perron–Frobenius theorems, we have

$$\begin{aligned} v^t(A_1+B_1)v\le & {} \rho (A_1+B_1)=\frac{(n-1)(c+q)-k(k-a+c-1)}{q}, \end{aligned}$$

(15)

$$\begin{aligned} v^t(A_2+B_2)v\le & {} \rho (A_2+B_2)=\frac{k(k-a-1)-c(n-k-1)}{q}. \end{aligned}$$

(16)

Substituting (15) into (13), and (16) into (14) yields the assertion of the theorem. The proof is completed. $\square$

For an eigenvalue $\lambda$ ($\lambda \not =5$) of $G_0$, according to (11), we have $-\,3\le \lambda \le 1$, which is a better bound than that from (4). In fact, $-\,3$ is the smallest eigenvalue of $G_0$. Likewise, according to the inequality (11), it follows that 4 is an upper bound on the eigenvalues $\theta$ $(\theta \not =12)$ of the semi-strongly regular graph with parameters $(24,12;4,12;-\,4)$ derived from Theorem 8 in Sect. 4. Indeed, the second largest eigenvalue of this graph is 4.

If the numbers $s_1,s_2,t_1$ and $t_2$ in a connected GSRG$(n,k;a_1,a_2;c_1,c_2)$ are independent of the choice of the vertex, then (10) can be replaced by

$$\begin{aligned} v^tA_1v\le & {} \rho (A_1)=s_1,\quad v^tA_2v\le \rho (A_2)=s_2,\\ v^tB_1v\le & {} \rho (B_1)=t_1,\quad v^tB_2v\le \rho (B_2)=t_2. \end{aligned}$$

Thus we have

Theorem 4

Let $G'$ be a connected GSRG$(n,k;a_1,a_2;c_2,c_2)$, where $a_1>a_2,$ $c_1>c_2$, and $\theta \not =k$ be an eigenvalue of $G'$. If the numbers $s_1,s_2,t_1,t_2$ in $G'$ are independent of the choice of the vertex, then

$$\begin{aligned} \theta ^2\le & {} (a_2-c_2)\theta +k-c_2+(a_1-a_2)s_1+(c_1-c_2)t_1, \end{aligned}$$

(17)

$$\begin{aligned} \theta ^2\ge & {} (a_1-c_1)\theta +k-c_1-(a_1-a_2)s_2-(c_1-c_2)t_2. \end{aligned}$$

(18)

There really exist connected generalized strongly regular graphs of grade 2 such that some of their eigenvalues meet the equality in (17). For instance, in the connected GSRG(64,21;20,2;12,0), denoted by $G_0'$, derived from Example 1 in Sect. 5, we have $s_1=1, s_2=20$, $t_1=30$ and $t_2=12$. Thus from (17), the smallest eigenvalue of $G_0'$ is at least $-\,19$. In fact, according to the character table of Hamming scheme [2], it follows that $-\,19$ is the smallest eigenvalue of $G_0'$.

3 Generalized Strongly Regular Graphs from Cayley Graphs

We start this section by providing a brief description of Cayley graphs. Let K be a group and C be a subset of K that is closed under taking inverse and does not contain the identity. The Cayley graph X(K, C) is the graph with vertex set K and two vertices $x,y\in K$ is adjacent if and only if $yx^{-1}\in C$. For a general overview of this subject, we refer the reader to [6].

Let ${\mathbb {Z}}_{4t+1}=\{0,1,2,\ldots , 4t\}$ be the ring of integers modulo $4t+1$, and

$$\begin{aligned} C=\{4h+2,4h+3\,|h=0,1,2,\ldots , t-1\}\subseteq {\mathbb {Z}}_{4t+1}. \end{aligned}$$

Then the Cayley graph $X({\mathbb {Z}}_{4t+1},C)$ is undirect and of degree 2t. The following result shows that $X({\mathbb {Z}}_{4t+1},C)$ is a generalized strongly regular graph of grade t.

Theorem 5

$X({\mathbb {Z}}_{4t+1},C)$ is a generalized strongly regular graph of grade t with parameters $n=4t+1$, $k=2t$, and for $i=1,2,\ldots ,t,$

$$\begin{aligned} a_i=t-i;\quad c_i=2t-i. \end{aligned}$$

Proof

For any two adjacent vertices x, y, without loss of generality, we assume that $y=x+4h_1+2$ for some $h_1\in H=\{0,1,2,\ldots , t-1\}$, because if $y=x+4h_1+3$, then $x=y+4h'+2$ for some $h'\in H$. Now we calculate the number of vertices $z\in {\mathbb {Z}}_{4t+1}$ adjacent to both x and y.

If $z=x+4h_2+2\equiv y+4h_3+2$ (mod $4t+1$) for some $h_2,h_3\in H$, then

$$\begin{aligned} 4(h_3+h_1-h_2)+2\equiv 0\,(\mathrm{mod}\,\,4t+1). \end{aligned}$$

Hence there exists an integer g such that

$$\begin{aligned} 4(h_3+h_1-h_2)+2=g(4t+1). \end{aligned}$$

(19)

Since $h_1,h_2,h_3\in H$, it follows that

$$\begin{aligned} -\,4t+4\le 4(h_3+h_1-h_2)\le 8t-8, \end{aligned}$$

(20)

which implies that $g=0$ if $t=1$ and $g=0$ or 1 if $t>1$. However for both $g=0$ and $g=1$ and for any $h_1\in H$, there exist no integers $h_2, h_3$ satisfying (19).

If $z=x+4h_2+2\equiv y+4h_3+3$ (mod $4t+1$) for some $h_2,h_3\in H$, then

$$\begin{aligned} 4(h_3+h_1-h_2)+3\equiv 0\,(\mathrm{mod}\,\,4t+1). \end{aligned}$$

It follows from (20) that there exist integers g, where $g=0$ if $t=1$ and $g=0$ or 1 if $t>1$, satisfying

$$\begin{aligned} 4(h_3+h_1-h_2)+3=g(4t+1). \end{aligned}$$

(21)

But the Eq. (21) has no integer solutions for $h_2,h_3$ for both $g=0$ and $g=1$.

A similar argument indicates that there exist no vertices $z\in {\mathbb {Z}}_{4t+1}$ such that $z=x+4h_2+3\equiv y+4h_3+3$ (mod $4t+1$) for some $h_2,h_3\in H.$

If $z=x+4h_2+3\equiv y+4h_3+2$ (mod $4t+1$), then

$$\begin{aligned} 4(h_3+h_1-h_2)+1\equiv 0\,(\mathrm{mod}\,\,4t+1). \end{aligned}$$

It follows from (20) that there exist integers g, where $g=0$ if $t=1$ and $g=0$ or 1 if $t>1$, satisfying

$$\begin{aligned} 4(h_3+h_1-h_2)+1=g(4t+1). \end{aligned}$$

(22)

The Eq. (22) has no integer solutions for $h_2,h_3$ if $g=0$. If $g=1$, then $h_3+h_1-h_2=t$. Let $h_1=i$ for $i=0,1,2,\ldots , t-1$. Then the number of pairs $(h_2,h_3)$ satisfying $h_3-h_2=t-i$ is i for $i=0,1,2,\ldots , t-1$. Thus the number of common neighbours of two adjacent vertices is i for some $i\in H$.

For two non-adjacent vertices x, y, we assume that $y=x+4r$ where $r\in \{1,2,\ldots ,t\}$. Let $z\in {\mathbb {Z}}_{4t+1}$ be a common neighbour of x and y.

If $z=x+4h_1+2\equiv y+4h_2+2$ (mod $4t+1$) for some $h_1,h_2\in H$, then

$$\begin{aligned} 4(r+h_2-h_1)\equiv 0\,(\mathrm{mod}\,\,4t+1). \end{aligned}$$

(23)

Since $1\le r\le t, 0\le h_1,h_2\le t-1$, we have

$$\begin{aligned} -\,4t+4\le 4(r+h_2-h_1)\le 8t-4. \end{aligned}$$

(24)

Thus there exist integers g, where $g=0$ if $t=1$ and $g=0$ or 1 if $t>1$, such that

$$\begin{aligned} 4(r+h_2-h_1)=g(4t+1). \end{aligned}$$

(25)

There are no integers $h_1,h_2\in H$ satisfying (25) if $g=1$. For $g=0$, we have $r+h_2-h_1=0$. Let $r=i$, then the number of pairs $(h_1,h_2)$ satisfying $h_1-h_2=i$ is $t-i$ for $i=1,2,\ldots ,t$.

If $z=x+4h_1+2\equiv y+4h_2+3$ (mod $4t+1$) for some $h_1,h_2\in H$, then

$$\begin{aligned} 4(r+h_2-h_1)+1\equiv 0\,(\mathrm{mod}\,\,4t+1). \end{aligned}$$

Since (24), there exist integers $g=0$ or 1 such that

$$\begin{aligned} 4(r+h_2-h_1)+1=g(4t+1). \end{aligned}$$

(26)

If $g=0$, then there are no integers $h_1,h_2\in H$ satisfying (26). If $g=1$, then we have $r+h_2-h_1=t$. Suppose that $r=i$ for $i=1,2,\ldots ,t$. Then the number of pairs $(h_1,h_2)$ satisfying $h_2-h_1=t-i$ is i.

If $z=x+4h_1+3\equiv y+4h_2+2$ (mod $4t+1$) for some $h_1,h_2\in H$, then

$$\begin{aligned} 4(r+h_2-h_1)-1\equiv 0\,(\mathrm{mod}\,\,4t+1). \end{aligned}$$

(27)

The inequality (24) implies that there exist no integers $h_1,h_2\in H$ satisfying (27) for any $r\in \{1,2,\ldots ,t\}$.

If $z=x+4h_1+3\equiv y+4h_2+3$ (mod $4t+1$) for some $h_1,h_2\in H$, then (23) holds. By a similar argument, for $r=i$, the number of pairs $(h_1,h_2)$ satisfying (23) is $t-i$.

Therefore, the number of common neighbours of two non-adjacent vertices is $2t-i$ for some $1\le i\le t$. $\square$

In particular, if $t=1$, then $X({\mathbb {Z}}_5,\{2,3\})$ is strongly regular. For $t=2$, $X({\mathbb {Z}}_9,\{2,3,6,7\})$ is the semi-strongly regular graph with parameters $(9,4;1,3;-\,1)$ shown in Fig. 2.

Fig. 2

A semi-strongly regular graph with parameters $(9,4;1,3;-\,1)$

4 Constructions from Graph Operations

We first introduce some operations of graphs. Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be graphs. The composition $G_1[G_2]$ of $G_1$ and $G_2$ is a graph with vertex set $V_1\times V_2$, and

$$\begin{aligned} (u_1,u_2)\sim (v_1,v_2)\;\;\mathrm{iff}\;\; u_1\sim v_1 \;\;\mathrm{or} \;\;(u_1=v_1 \;\;\mathrm{and}\;\; u_2\sim v_2). \end{aligned}$$

Define the product $G_1\times G_2$ as a graph with vertex set $V_1\times V_2$, and

$$\begin{aligned} (u_1,u_2)\sim (v_1,v_2)\;\;\mathrm{iff}\;\; \mathrm{either}\;\;u_1\sim v_1 \;\;\mathrm{or} \;\; u_2\sim v_2. \end{aligned}$$

The join of $G_1$ and $G_2$ is defined as a graph with vertex set $V_1\cup V_2$ and edge set $E_1\cup E_2\cup \{uv:u\in V_1,\,v\in V_2\}$.

Refer to [9] for the above operations of graphs.

Based on the above operations, we can obtain new generalized strongly regular graphs from old ones.

Theorem 6

Let $G_1$ be a GSRG$(n_1,k_1;\lambda _1,\lambda _2,\ldots ,\lambda _p; \mu _1,\mu _2,\ldots ,\mu _p)$, where $\lambda _i<k_1-1$ and $\mu _i<k_1<n_1-1$ for $1\le i \le p$. Let $G_2$ be a GSRG$(n_2,k_2;\lambda _1',\lambda _2'$, $\ldots ,$ $\lambda _q'; \mu _1',\mu _2',\ldots ,\mu _q')$, where $0<k_2<n_2-1$. Then the composition $G_1[G_2]$ is a generalized strongly regular graph of grade $p+q$ with parameters $n=n_1n_2$, $k=k_1n_2+k_2,$ and

$$\begin{aligned} a_i= & {} \lambda _in_2+2k_2 \,\,\mathrm{for} \,\,1\le i\le p,\quad a_{p+j}=\lambda _j'+k_1n_2 \,\,\mathrm{for}\,\,1\le j\le q;\\ c_j= & {} k_1n_2+\mu _j'\,\,\mathrm{for}\,\,1\le j\le q,\quad c_{q+i}=\mu _in_2 \,\,\mathrm{for} \,\,1\le i\le p. \end{aligned}$$

Proof

Let $u=(u_1,u_2),v=(v_1,v_2)\in V(G_1[G_2])$. Let $N_u$ denote the set of neighbours of u, and $N_{uv}$ denote the set of common neighbours of u and v. Since the adjacency of $G_1[G_2]$, we have $|N_u|=k_1n_2+k_2$ for each $u\in V(G_1[G_2])$.

For any two vertices u, v, and $u\sim v$, we have

$$\begin{aligned} |N_{uv}|=\left\{ \begin{array}{ll} |N_{u_1v_1}||G_2|+|N_{u_2}|+|N_{v_2}|&{}\quad \mathrm{if}\,u_1\sim v_1,\\ |N_{u_2v_2}|+|N_{u_1}||G_2|&{}\quad \mathrm{if}\,u_1=v_1 \,\mathrm{and}\,u_2\sim v_2. \end{array}\right. \end{aligned}$$

If $u\not \sim v$, then

$$\begin{aligned} |N_{uv}|=\left\{ \begin{array}{ll} |N_{u_1}||G_2|+|N_{u_2v_2}|&{}\quad \mathrm{if}\,u_1= v_1\,\mathrm{and}\,u_2\not \sim v_2,\\ |N_{u_1v_1}||G_2|&{}\quad \mathrm{if}\,u_1\not \sim v_1 \,\mathrm{and}\,u_1\ne v_1. \end{array}\right. \end{aligned}$$

It follows from $\lambda _i<k_1-1$ and $\mu _i<k_1$ that $\lambda _in_2+2k_2\not =\lambda _j'+k_1n_2$ and $k_1n_2+\mu _j'\not =\mu _in_2$ for any $1\le i\le p$, $1\le j\le q$. Notice that both $0<k_1<n_1-1$ and $0<k_2<n_2-1$ hold, which suggest that for each $a_i$ and $c_i$, $1\le i\le p+q$, there exist two adjacent vertices and two non-adjacent vertices which have exactly $a_i$ and $c_i$ common neighbours, respectively. Therefore, $G_1[G_2]$ is a generalized strongly regular graph. $\square$

In particular, the composition of a SRG($n_1,k_1,\lambda ,\mu$), where $\lambda < k_1-1$ and $\mu<k_1<n_1-1$, and a SRG($n_2,k_2,\lambda ',\mu '$) with $0<k_2<n_2-1$ is a generalized strongly regular graph of grade 2. In what follows we consider the join of a generalized strongly regular graph and an empty graph.

Theorem 7

Let $G_1$ be a GSRG$(n_1,k_1;\lambda _1,\lambda _2,\ldots ,\lambda _p; \mu _1,\mu _2,\ldots ,\mu _p)$, where $n_1+\lambda _i\not =2k_1$ and $\mu _i<k_1<n_1-1$ for $1\le i \le p$. Let $G_2$ be a ${\overline{K}}_{n_1-k_1}$ (the graph on $n_1-k_1$ vertices with no edges). Then the join of $G_1$ and $G_2$ is a generalized strongly regular graph of grade $p+1$ with parameters $n=2n_1-k_1$, $k=n_1$, and

$$\begin{aligned} a_i= & {} \lambda _i+n_1-k_1\;\; \mathrm{for} \;\;1\le i\le p,\,\,a_{p+1}=k_1;\\ c_i= & {} \mu _i+n_1-k_1\;\;\mathrm{for} \;\;1\le i\le p,\;\;c_{p+1}=n_1. \end{aligned}$$

Proof

The proof is straightforward.$\square$

The graph $G_0$ in Fig. 1 is the join of $C_5$ and ${\overline{K}}_3$. Next, by the product of two strongly regular graphs, we obtain a class of generalized strongly regular graphs.

Theorem 8

Let $G_1$ be a strongly regular graph with parameters $(n_1,k_1,$ $\lambda _1,$ $\mu _1)$, and $G_2$ be a strongly regular graph with parameters $(n_2,k_2,\lambda _2,\mu _2)$, where $0<k_j<n_j-1$ for $j=1,2$. Then the product $G_1\times G_2$ is a k-regular graph on $n=n_1n_2$ vertices, where $k=(k_1n_2+k_2n_1-2k_1k_2)$, and the number of common neighbours of two adjacent vertices in $V(G_1\times G_2)$ is

$$\begin{aligned} a_1= & {} \lambda _1n_2+k_2n_1-2k_1k_2,\\ a_2= & {} \lambda _1n_2-4\lambda _1k_2+4\lambda _1\mu _2+n_1\mu _2-4k_1\mu _2+2k_1k_2,\\ a_3= & {} \lambda _2n_1+k_1n_2-2k_1k_2,\mathrm{or}\\ a_4= & {} \lambda _2n_1-4\lambda _2k_1+4\lambda _2\mu _1+n_2\mu _1-4k_2\mu _1+2k_1k_2;\\ \end{aligned}$$

the number of common neighbours of two non-adjacent vertices is

$$\begin{aligned} c_1= & {} \lambda _1n_2-4\lambda _1k_2+4\lambda _1\lambda _2-4k_1\lambda _2+\lambda _2n_1+2k_1k_2,\\ c_2= & {} \mu _2n_1+n_2k_1-2k_1k_2,\\ c_3= & {} \mu _1n_2+n_1k_2-2k_1k_2,\mathrm{or}\\ c_4= & {} \mu _1n_2+n_1\mu _2+2k_1k_2-4\mu _1k_2-4\mu _2k_1+4\mu _1\mu _2. \end{aligned}$$

For $1\le i\le 4$, if both $a_i$’s and $c_i$’s take on $p'\le 4$ distinct values, then $G_1\times G_2$ is a GSRG$(n,k;a_{1'},\ldots , a_{p'};c_{1'},\ldots ,c_{p'})$, where for $1'\le j'\le p'$, $a_{j'}=a_i$ for some $i\in \{1,2,3,4\}$, and $c_{j'}=c_i$ for some $i\in \{1,2,3,4\}$.

Proof

It is easy to show that $G_1\times G_2$ is $k_1(n_2-k_2)+k_2(n_1-k_1)$-regular according to the adjacency of $G_1\times G_2$. Now we determine $a_i$ and $c_i$ for $i=1,2,3,4$.

Let $u=(u_1,u_2),v=(v_1,v_2)\in V(G_1\times G_2)$. Then $u\sim v$ if and only if either (i) $u_1\sim v_1$ and $u_2\not \sim v_2$ or (ii) $u_1\not \sim v_1$ and $u_2\sim v_2$.

For (i), if $u_2=v_2$, then let

$$\begin{aligned} S_1= & {} \{(w_1,w_2)|w_1\sim u_1,w_1\sim v_1, w_2\not \sim u_2=v_2\}, \,\,\mathrm{and}\\ S_2= & {} \{(w_1,w_2)|w_1\not \sim u_1,w_1\not \sim v_1, w_2\sim u_2=v_2\}. \end{aligned}$$

Clearly, the common neighbours of u and v are exactly the vertices in $S_1\cup S_2$. Therefore,

$$\begin{aligned} a_1=|S_1|+|S_2|=\lambda _1(n_2-k_2)+k_2(n_1-2k_1+\lambda _1)=\lambda _1n_2+k_2n_1-2k_1k_2. \end{aligned}$$

If $u_2\not =v_2$, and $w=(w_1,w_2)$ is a common neighbour of u and v, then w must belong to one of the following four sets:

$$\begin{aligned} W_1= & {} \{(w_1,w_2)\in V(G_1\times G_2)|w_1\sim u_1,w_1\sim v_1,w_2\not \sim u_2,w_2\not \sim v_2\},\\ W_2= & {} \{(w_1,w_2)\in V(G_1\times G_2)|w_1\not \sim u_1,w_1\not \sim v_1,w_2\sim u_2,w_2\sim v_2\},\\ W_3= & {} \{(w_1,w_2)\in V(G_1\times G_2)|w_1\sim u_1,w_1\not \sim v_1,w_2\not \sim u_2,w_2\sim v_2\},\\ W_4= & {} \{(w_1,w_2)\in V(G_1\times G_2)|w_1\not \sim u_1,w_1\sim v_1,w_2\sim u_2,w_2\not \sim v_2\}. \end{aligned}$$

Hence, we have

$$\begin{aligned} a_2= & {} |W_1|+|W_2|+|W_3|+|W_4|\\= & {} \lambda _1(n_2-2k_2+\mu _2)+(n_1-2k_1+\lambda _1)\mu _2+2(k_1-\lambda _1)(k_2-\mu _2)\\= & {} \lambda _1n_2-4\lambda _1k_2+4\lambda _1\mu _2+n_1\mu _2-4k_1\mu _2+2k_1k_2. \end{aligned}$$

For (ii), there still need to consider the case $u_1=v_1$ and $u_1\not =v_1$, respectively. The proof for $a_3,a_4$ is similar to that for $a_1,a_2$, so will be omitted.

For $u=(u_1,u_2),v=(v_1,v_2)\in V(G_1\times G_2)$, $u\not \sim v$ if and only if the vertices u and v satisfy one of the following four conditions:

(a) $u_1\sim v_1$ and $u_2\sim v_2$; (b) $u_1=v_1$ and $u_2\not \sim v_2$;

(c) $u_1\not \sim v_1$ and $u_2=v_2$; (d) $u_1\not \sim v_1$, $u_1\not =v_1$, $u_2\not \sim v_2$ and $u_2\ne v_2$.

It follows from the adjacency that the set of common neighbours of u and v is $W_1\cup W_2\cup W_3\cup W_4$.

For (a), we have

$$\begin{aligned} c_1= & {} |W_1|+|W_2|+|W_3|+|W_4|\\= & {} \lambda _1(n_2-2k_2+\lambda _2)+(n_1-2k_1+\lambda _1)\lambda _2+2(k_1-\lambda _1)(k_2-\lambda _2)\\= & {} \lambda _1n_2-4\lambda _1k_2+4\lambda _1\lambda _2-4k_1\lambda _2+\lambda _2n_1+2k_1k_2. \end{aligned}$$

For (b), $W_3=W_4=\emptyset$, so we have

$$\begin{aligned} c_2= & {} |W_1|+|W_2|\\= & {} k_1(n_2-2k_2+\mu _2)+\mu _2(n_1-k_1)\\= & {} \mu _2n_1+n_2k_1-2k_1k_2. \end{aligned}$$

For (c), we conclude that $W_3=W_4=\emptyset$, and

$$\begin{aligned} c_3= & {} |W_1|+|W_2|\\= & {} \mu _1(n_2-k_2)+k_2(n_1-2k_1+\mu _1)\\= & {} \mu _1n_2+n_1k_2-2k_1k_2. \end{aligned}$$

For (d), we have

$$\begin{aligned} c_4= & {} |W_1|+|W_2|+|W_3|+|W_4|\\= & {} \mu _1(n_2-2k_2+\mu _2)+(n_1-2k_1+\mu _1)\mu _2+2(k_1-\mu _1)(k_2-\mu _2)\\= & {} \mu _1n_2+n_1\mu _2+2k_1k_2-4\mu _1k_2-4\mu _2k_1+4\mu _1\mu _2. \end{aligned}$$

Let u be a vertex of $G_1\times G_2$, $s_i(u)$ denote the number of vertices that are adjacent to u and share $a_i$ common neighbours with u, and $t_i(u)$ denote the number of vertices that are non-adjacent to u and share $c_i$ common neighbours with u for $1\le i\le 4$. It is obvious that $s_1=k_1$, $s_2=k_1(n_2-k_2-1)$, $s_3=k_2$ and $s_4=k_2(n_1-k_1-1)$. It is also obvious that $t_1=k_1k_2$, $t_2=n_2-k_2-1$, $t_3=n_1-k_1-1$ and $t_4=(n_1-k_1-1)(n_2-k_2-1)$. Note that $k_j$ satisfies $0<k_j<n_j-1$ for $j=1,2$, which implies that both $s_i$’s and $t_i$’s are greater than 0 for $1\le i\le 4$. Thus for each $a_i$ and $c_i$, $1\le i\le 4$, there exist two adjacent vertices and two non-adjacent vertices that have $a_i$ and $c_i$ common neighbours, respectively. Hence $G_1\times G_2$ is a generalized strongly regular graph of grade $p'$ if both $a_i$’s and $c_i$’s take on $p'$ distinct values. $\square$

For example, the product of a SRG(4,2,0,2) and a SRG(6,4,2,4) is a semi-strongly regular graph with parameters $(24,12;4,12;-\,4)$; the product of a SRG(5,2,0,1) and a SRG(9,4,1,2) is a GSRG (45,22; 6,10,7;13,12,11); the product of a SRG(9,4,1,2) and a SRG(10,3,0,1) is a GSRG (90,43;13,19,16,20;22,25, 23,21).

If $G_1$ is a strongly regular graph with parameters $(n_1,k_1,\lambda ,\mu )$, $G_2$ is a ${\overline{K}}_{n_2}$, then $G_1[G_2]$ and $G_1\times G_2$ are equivalent and are quasi-strongly regular graphs with parameters $(n_1n_2,k_1n_2,\lambda n_2;k_1n_2,\mu n_2)$. Next we provide a similar result to Theorem 2.6 in [5]. We first introduce the following lemma in [7].

Lemma 1

[7] Let G be a quasi-strongly regular graph with parameters (n, k, a;  $c_1,c_2)$. Let u be some vertex of G and let $l_i(u)$ denote the number of vertices that are non-adjacent to u and share $c_i$ common neighbours with u for $i=1,2$. Then $l_1(u)$, $l_2(u)$ do not depend on the choice of u and satisfy:

$$\begin{aligned} l_1=\frac{k(k-a-1)-c_2(n-k-1)}{c_1-c_2} \end{aligned}$$

and

$$\begin{aligned} l_2=\frac{c_1(n-k-1)-k(k-a-1)}{c_1-c_2}. \end{aligned}$$

By Lemma 1 and the same method as in the proof of Theorem 2.6 in [5], we obtain

Theorem 9

Let G be a quasi-strongly regular graph with parameters (n, k, a;  $c_1,c_2)$. Then $c_1=k$ if and only if G is isomorphic to $G_1[G_2]$, where $G_1$ is a SRG$(n_1,k_1,\lambda ,\mu )$ and $G_2$ is a ${\overline{K}}_{n_2}$ with parameters satisfying

$$\begin{aligned} n=n_1n_2,\,\, k=c_1=k_1n_2,\,\,a=\lambda n_2,\,\,c_2=\mu n_2\,\,\mathrm{and}\,\, n_2=\frac{k(k-a)-c_2(n-k)}{k-c_2}. \end{aligned}$$

Proof

Since the “if” part is clear, it is enough to prove the “only if” part. Assume that G is a quasi-strongly regular graph with parameters $(n,k,a;c_1,c_2)$, where $c_1=k$. We define an equivalence relation R on the vertex set as: $(u,v)\in R$ iff u and v share $c_1$ common neighbours. Then Lemma 1 implies that each equivalence class has the same size $l_1+1$.

We define $G_1$ and $G_2$. Let $n_2=l_1+1$, and $G_2=\overline{K}_{n_2}$. The graph $G_1$ is defined to have the equivalence classes as its vertices, and two vertices $C_1$ and $C_2$ are defined to be adjacent if and only if there exists a vertex $u\in C_1$ and a vertex $v\in C_2$ such that u and v are adjacent in G. It is easy to show that $G_1$ is a strongly regular graph with parameters $(n_1,k_1,\lambda ,\mu )$, where $n_1=n/n_2$, $k_1=k/n_2$, $\lambda =a/ n_2$ and $\mu =c_2/n_2$.

Let the equivalence class $C_i$ be $\{v_{i1},v_{i2},$ $\ldots ,v_{in_2}\}$, and let $V(G_2)=\{u_1,u_2,$ $\ldots ,$ $u_{n_2}\}$. We next show that f given by $f(C_i,u_j)=v_{ij}$ is a graph isomorphism from $G_1[G_2]$ to G.

Clearly, f is a bijection. Let $(C_i,u_j)$ and $(C_{i'},u_{j'})$ be vertices of $G_1[G_2]$. Since $G_2$ has no edges, it follows that $(C_i,u_j)\sim (C_{i'},u_{j'})$ if and only if $C_i\sim C_{i'}$ in $G_1$. Thus we need to show that $v_{ij}\sim v_{i'j'}$ in G if and only if $C_i$ is adjacent to $C_{i'}$ in $G_1$. If $i=i'$, then $v_{ij}$ and $v_{i'j'}$ share $c_1=k$ common neighbours. Since G has no loops, we have $v_{ij}\not \sim v_{i'j'}$.

Suppose that $i\not =i'$. If $v_{ij}\sim v_{i'j'}$, then $C_i\sim C_{i'}$ in $G_1$. Conversely, if $C_i\sim C_{i'}$, then there exists a vertex $v_{il}\in C_i$ and a vertex $v_{i'l'}\in C_{i'}$ such that $v_{il}\sim v_{i'l'}$ in G. Since $v_{il}$ and $v_{ij}$ are in the same equivalence class, they share $c_1=k$ common neighbours, which implies that $v_{il}$ and $v_{ij}$ have the same neighbourhood. Thus we have $v_{ij}\sim v_{i'l'}$. Similarly, $v_{ij}\sim v_{i'j'}$ since $v_{i'l'}$ and $v_{i'j'}$ are in the same equivalence class. Therefore, f is an isomorphism. $\square$

5 Constructions Based on Association Schemes

In this section, we obtain a family of generalized strongly regular graphs from symmetric association schemes by merging some classes of an association scheme.

A d-class symmetric association scheme on a finite set ${\varOmega }$ is a partition of ${\varOmega }\times {\varOmega }$ into sets $R_0,R_1,\ldots ,R_d$, whose adjacency matrices are $A_0,A_1,\ldots ,A_d$ respectively, such that:

• (i) $A_0=I_{{\varOmega }}$;

• (ii) $A_i$ is symmetric for $i=1,\ldots ,d$;

• (iii) none of the $A_i$’s equals O, and $\sum _{i=0}^dA_i=J$;

• (iv) for all i, j in $\{1,\ldots ,d\}$, $A_iA_j=\sum _{k=0}^dp^k_{ij}A_k$ for some constants $p^k_{ij}$. (See [2] or [1] for more details.)

Theorem 10

Let $({\varOmega },\{R_0,R_1,\ldots ,R_d\})$ be a symmetric association scheme, and $A_i$ be the adjacency matrix of $R_i$, for $0\le i\le d$. Let $E\subseteq \{1,2,\ldots ,d\}$, $F=\{1,2,\ldots ,d\}\backslash E$, and let G be the graph with adjacency matrix $\sum _{i\in E}A_i$. Then G is a generalized strongly regular graph of grade $p\le \lfloor d/2\rfloor$ if and only if $\sum _{i,j\in E}p^e_{ij}$ take on p distinct values as e ranges over E, and $\sum _{i,j\in E}p^{f}_{ij}$ take on p distinct values as f ranges over F.

Proof

For $u,v\in V(G)$, $u\sim v$ if and only if $(u,v)\in R_e$ for some $e\in E$. Hence G is regular of degree $\sum _{e\in E}p^0_{ee}$.

For two adjacent vertices u, v, if $(u,v)\in R_{e_i}$ for some $e_i\in E$, then the number of common neighbours of u and v is

$$\begin{aligned} a_i=\sum _{j,k\in E}p^{e_i}_{jk}. \end{aligned}$$

If $u\not \sim v$, then $(u,v)\in R_{f_i}$ for some $f_i\in F$. Therefore, the number of common neighbours of u and v is

$$\begin{aligned} c_i=\sum _{j,k\in E}p^{f_i}_{jk}. \end{aligned}$$

Since $A_i\not =O$ for $i=1,2,\ldots ,d$, G is a generalized strongly regular graph of grade $p\le \lfloor d/2\rfloor$ when both $a_i$’s and $c_i$’s take on p distinct values. $\square$

We illustrate Theorem 10 by the following example, in which we obtain several generalized strongly regular graphs from a Hamming scheme.

Example 1

For a Hamming scheme H(6,2), $({\varOmega },\{R_0,R_1,R_2,R_3,R_4,R_5,$ $R_6\})$, let ${\varOmega }=F_2^6$, and for $u,v\in {\varOmega }$, $(u,v)\in R_i$ if u and v differ in exactly i positions, where $0\le i\le 6$. Thus $|{\varOmega }|=64$, and for each $u\in {\varOmega }$, $0\le i\le 6$, we have $|\{v| (u,v)\in R_i\}|=\left( {\begin{array}{c}6\\ i\end{array}}\right)$.

From Theorem 10, we obtain:

a GSRG(64, 36; 30, 28, 10; 30, 12, 10)  if  $E=\{1,2,4\},$ $F=\{3,5,6\};$

a GSRG(64, 21; 20, 2; 12, 0)  if  $E=\{3,6\}$, $F=\{1,2,4,5\};$

a semi-strongly regular graph with parameters $(64,41;30,26;-\,6)$ if $E=\{2,3,5\}$, $F=\{1,4,6\}.$