A family of generalized strongly regular graphs of grade 2

Abstract

A generalized strongly regular graph of grade p, as a new 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. For any vertex v of a generalized strongly regular graph of grade 2 with parameters (n,k\mathrm{;}{a}_1,a_2\mathrm{;}{c}_1,c_2), if the number of the vertices that are adjacent to v and share a_i(i=1,2) common neighbours with v, or are non-adjacent to v and share c_i(i=1,2) common neighbours with v is independent of the choice of the vertex v, then the generalized strongly regular graph of grade 2 is free. In this paper, we investigate the generalized strongly regular graph of grade 2 with parameters (n,k\mathrm{;}k-1,a_2\mathrm{;}k-1,c_2) and provide the sufficient and necessary conditions for the existence of a family of free generalized strongly regular graphs of grade 2.

Graphical abstract

Keywords

Strongly regular graph / generalized strongly regular graph / graph composition, isomorphism

1 Introduction

Throughout this paper, graphs are assumed to be finite, undirected and simple. For a non-empty and k-regular graph G with n vertices, if there are two non-negative integers \lambda and \mu such that every pair of adjacent vertices in G have \lambda common neighbours, and every pair of distinct non-adjacent vertices in G have \mu common neighbours, then the graph G is said to be a strongly regular graph with parameters (n,k,\lambda ,\mu ), denoted by SRG(n,k,\lambda ,\mu ). The reader is referred to [1,2] for more properties of strongly regular graphs.

Erickson et al. [3] generalized the concept of strong regular graphs and gave the definition of Deza graphs. A Deza graph with parameters (n,k,\lambda ,\mu ) is a k-regular graph on n vertices such that any two distinct vertices have a or b common neighbours. It is easily seen that the number of common neighbours of any two vertices in the Deza graph 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. On the other hand, Golightly et al. [5] generalized the concept of strongly regular graphs from distinct perspectives, which is quasi-strongly regular graphs. For a non-empty and k-regular graph G with n vertices, if any two adjacent vertices in G have a common neighbours and any two non-adjacent vertices have c_i(1⩽i⩽p) common neighbours, where a and c_i are non-negative integers, then the graph G is said to be a quasi-strongly regular graph with parameters (n,k,a;c_1,c_2,\dots ,c_p). Comparing the concepts of quasi-strongly regular graphs and strongly regular graphs, it is easy to get that a quasi-strongly regular graph with p=1 is a strongly regular graph. Goidberg et al. [4] studied quasi-strongly regular graphs and gave some properties of quasi-strong regular graphs with p=2.

Huo and Zhang [6] have made a new generalization of strongly regular graphs, proposed the concept of generalized strongly regular graphs for the first time, and proved that the secondary components of a class of finite geometric graphs happen to be generalized strongly regular graphs. Below we give the definition of a generalized strongly regular graph.

Definition 1.1 [6,7]　For 1⩽i⩽p, let a_i and c_i be non-negative integers, and a_i\ne a_j,c_i\ne c_j if i\ne j(1⩽i,j⩽p). For a non-empty and k-regular graph G with n vertices, if

(\mathrm{i}) any two adjacent vertices have a_i common neighbours and any two non-adjacent vertices have c_i common neighbours for some 1⩽i⩽p;

(\mathrm{i}\mathrm{i}) for each 1⩽i⩽p, there exist two adjacent vertices and two non-adjacent vertices which have exactly a_i and c_i common neighbours, respectively,

then G is a generalized strongly regular graph with parameters(n,k;a_1,a_2,\dots ,a_p;c_1,c_2,\dots ,c_p), denoted by GSRG(n,k;a_1,a_2,\dots ,a_p;c_1,c_2,\dots ,c_p).

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 not difficult to find that a generalized strongly regular graph of grade 1 is a strongly regular graph. In this paper, we mainly focus on the generalized strongly regular graphs of grade 2. Let G be a generalized strongly regular graphs of grade 2 with parameters (n,k;a_1,a_2;c_1,c_2). In particular, when a_i=c_i(i=1,2), the graph G is actually a Deza graph. Here, we regard the graph G with a_i=c_i(i=1,2) as a special class of generalized strongly regular graphs. For example, Fig.1 is a generalized strongly regular graph of grade 2 with parameters (10,5;4,2;4,2) and it is also a Deza graph with the parameters (10,5,4,2).

In the past two years, there are some results on the structural characterization of Deza graphs and quasi-strongly regular graphs with particular parameters. Erickson et al. [3] characterized the structure of Deza graphs with parameters (n,k,k,a). Kabanov et al. [8, 9] gave the sufficient conditions for the existence of Deza graphs with parameters (n,k,k-1,a) and (n,k,k-2,a), respectively. Jia et al. [7] characterized the structure of the quasi-strongly regular graphs with parameter c_1=k. But so far, there are few conclusions about the specific structure of generalized strongly regular graphs. This paper gives sufficient conditions for the existence of a class of generalized strongly regular graphs of grade 2.

2 Preliminary knowledge

In this section, let us introduce some concepts and notations.

Let \mathrm{\Gamma } be a generalized strongly regular graph of grade 2 with parameter (n,k;k-1,a_2;k-1,c_2). Write the vertex set of the graph \mathrm{\Gamma } as V(G). For any vertex v\in V(\mathrm{\Gamma }), we consider some subsets of V(\mathrm{\Gamma }):

N(v):=\{u\in V(\mathrm{\Gamma })\mid u\sim v\},

N[v]:=N(v)\cup \{v\},

A_i(v):=\{u\in V(\mathrm{\Gamma })\mid u\sim v and |N(v)\cap N(u)|=a_i\}(i=1,2),

A_i[v]:=A_i(v)\cup \{v\}(i=1,2),

C_i(v):=\{u\in V(\mathrm{\Gamma })\mid u\nsim v and |N(v)\cap N(u)|=c_i\}(i=1,2),

C_i[v]:=C_i(v)\cup \{v\}(i=1,2).

We denote the number of vertices in A_i(v) by s_i(v), the number of vertices in C_i(v) by t_i(v) (i=1,2). By definition, for each v\in V(\mathrm{\Gamma }), the equality

V(\mathrm{\Gamma })=\{v\}\cup A_1(v)\cup A_2(v)\cup C_1(v)\cup C_2(v)

holds. Thus,

n=1+s_1(v)+s_2(v)+t_1(v)+t_2(v).

Because \mathrm{\Gamma } is k-regular, the vertex v have k neighbours, and (n-k-1) non-neighbours. Jia et al. [7] counted the total number of edges between the neighbours and non-neighbours of v in two ways, and they obtained the following linear system of equations:

(1)\{\begin{array}{l}{s}_1(v)+s_2(v)=k,\\ t_1(v)+t_2(v)=n-k-1,\\ s_1(v)(k-a_1-1)+s_2(v)(k-a_2-1)=c_1{t}_1(v)+c_2{t}_2(v).\end{array}

In general, the values of s_1(v),s_2(v),t_1(v) and t_2(v) are related to the choice of v. For example, s_1(1)=2, but s_1(2)=0 in Fig.2.

Definition 2.1　Let \mathrm{\Gamma } be a generalized strongly regular graph of grade 2. We say that a generalized strongly regular graph \mathrm{\Gamma } of grade 2 is free if the values of s_1(v),s_2(v),t_1(v) and t_2(v) are independent of the choice of the vertex v for any vertex v\in V(\mathrm{\Gamma }).

Denote s_1(v),s_2(v),t_1(v) and t_2(v) by s_1,s_2,t_1 and t_2, respectively. For example, the graph shown in Fig.3 is a free and generalized strongly regular graph \mathrm{\Gamma } of grade 2. We can easily find that s_1=1,s_2=8,t_1=2,t_2=8.

In fact, we conclude from the linear relationship (1) that as long as any value of s_1(v),s_2(v),t_1(v), t_2(v) is determined, the values of the rest are also determined. Thus, if any value of these four numbers is independent of the choice of v, then generalized strongly regular graphs of grade 2 are free.

By Definition 1.1, we know that it is impossible that each vertices v\in V(\mathrm{\Gamma }) satisfies s_1(v)=0, otherwise, the statement (ii) of Definition 1.1 is not true. The same conclusion can be drawn for s_2(v),t_1(v) and t_2(v). Thus, for the graph \mathrm{\Gamma }, one of the following statements holds.

(a) The inequalities s_1(v)>0 and t_1(v)>0 hold for each v in V(\mathrm{\Gamma }).

(b) The inequality s_1(v)>0 holds for each v in V(\mathrm{\Gamma }), and t_1(v)=0 holds for some v in V(\mathrm{\Gamma }).

(c) There is a vertex v\in V(\mathrm{\Gamma }) such that s_1(v)=t_1(v)=0.

(d) There is a vertex v\in V(\mathrm{\Gamma }) such that s_1(v)=0, and the vertex v satisfies t_1(v)>0.

If the graph \mathrm{\Gamma } satisfies statement (a), (b), (c) or (d), we say that the graph \mathrm{\Gamma } is of type (A), (B), (C) or (D), respectively.

In next section, we will give the sufficient conditions for the existence of the graph of type (A).

3 Main conclusions

In this section, we characterize the structure of a GSRG(n,k;k-1,a_2;k-1,c_2) of type (A). Before giving the main conclusions, we first introduce the definition of composition of graphs.

Definition 3.1 [3]　Let G_1 and G_2 be graphs. Then graph G is called the composition G_1[G_2] of G_1 and G_2 if G satisfies the following two statements:

(1) V(G)=\{(v_1,v_2):v_1\in V(G_1),v_2\in V(G_2)\};

(2) in the graph G, (v_1,v_2) and (u_1,u_2) are adjacent if and only if v_1 and u_1 are adjacent, or v_1=u_1, v_2 and u_2 are adjacent.

After introducing the definition of composition of graphs, the following theorem will be proved in the following pages.

Theorem 3.1　 Let G be a generalized strongly regular graph of grade 2 with parameter (n,k;k-1,a_2;k-1,c_2). Then G is a graph of type (A) if and only if G is isomorphic to G_1[G_2], where G_1 is an SRG(n_1,k_1,\lambda ,\mu ) and G_2 is an \frac{n_2}{2}{K}_2 with parameters satisfying

(1) when n_2=2, \lambda \ne k_1-1;

(2) \mu \ne k_1.

Obviously, the parameters of G are:

\begin{array}{c}n=n_1{n}_2,k=k_1{n}_2+1,a_1=k_1{n}_2,a_2=\lambda n_2+2,c_1=k_1{n}_2,c_2=\mu n_2\end{array}

and

n_2=\frac{(k-1)(k-a_2+1)-c_2(n-k+1)}{k-1-c_2}.

Before proving the above theorem, let us give some lemmas. Unless otherwise stated, we assume that the graph G discussed below is of type (A).

Lemma 3.1　 Let G be a generalized strongly regular graph of grade 2 with parameter (n,k;k-1,a_2;k-1,c_2). Then s_1=1.

Proof　We know that G is of type (A), that is the inequalities s_1(v)>0 and t_1(v)>0 hold for each v in V(G). Suppose that s_1(v)>1. Then the number of vertices which is adjacent to v and shares k-1 common neighbours with v is greater than 1. In this case, the number of common neighbours between vertices which is not adjacent to v and v is less than k-1. However, t_1(v)>0, which implies that there must be a vertex that is not adjacent to the vertex v and has k-1 common neighbours with v, a contradiction. Thus, s_1(v)=1. Because v is arbitrary, we have s_1=1.□

Since there is no connection between s_1(v)=1 and the choice of v, the values of s_2(v),t_1(v) and t_2(v) are not related to the choice of v. Thus, we know that all graphs of type (A) are free and generalized strongly regular graph of grade 2. After a simple calculation, we have the following corollary.

Corollary 3.1　 Let G be a generalized strongly regular graph of grade 2 with parameter (n,k;k-1,a_2;k-1,c_2). Then

\begin{array}{rl}& s_2=k-1,\\ & t_1=\frac{(k-1)(k-a_2-1)-c_2(n-k-1)}{k-1-c_2},\\ & t_2=\frac{(k-1)(n-2k+a_2)}{k-1-c_2}.\end{array}

By Lemma 3.1, for an arbitrary vertex v of G, there is a unique vertex v^{\ast } which is adjacent to v and shares k-1 common neighbours with v. Next, we detail the structure of a generalized strongly regular graph of grade 2 and type (A).

Corollary 3.2　 There exist no generalized strongly regular graphs of grade 2 with parameter (n,k;k-1,k-2;k-1,k-3), where k-3>0.

Proof　Let G be a generalized strongly regular graph of grade 2 with parameter (n,k;k-1,k-2;k-1,k-3), where k-3>0. In view of Lemma 3.1 and Corollary 3.1, we get

\begin{array}{rl}{s}_1+2t_1& =1+2\times \frac{(k-1)[k-(k-2)-1]-(k-3)(n-k-1)}{k-1-(k-3)}\\ & =1+2\times \frac{(k-1)-(k-3)(n-k-1)}{2}\\ & =1+k-1-(k-3)(n-k-1)\\ & =k+(k-3)(k+1)-(k-3)n\\ & =(k^2-k-3)-(k-3)n.\end{array}

Moreover, s_1,t_1>0, which yields

s_1+2t_1=(k^2-k-3)-(k-3)n⩾3,

that is,

\begin{array}{rl}(k-3)n& ⩽(k^2-k-3)-3\\ & ⩽k^2-k-6\\ & ⩽(k-3)(k+2).\end{array}

By k-3>0, we get n⩽k+2. However, G is not a complete graph. So, n=k+2. By Corollary 3.1 again, the equality t_2=0 holds, which contradicts t_2>0.□

Lemma 3.2　 Let G be a generalized strongly regular graph of grade 2 with parameter (n,k;k-1,a_2;k-1,c_2) and v be a vertex of G. If the vertex u\in C_1[v]\cup \{v^{\ast }\}, then C_1[u]\cup \{u^{\ast }\}=C_1[v]\cup \{v^{\ast }\}.

Proof　On the contrary, suppose that u\in C_1[v]\cup \{v^{\ast }\} and C_1[u]\cup \{u^{\ast }\}\ne C_1[v]\cup \{v^{\ast }\}.

Since G is k-regular, v is adjacent to v^{\ast } and shares k-1 common neighbours with v^{\ast }, N[v]=N[v^{\ast }] and (v^{\ast }{)}^{\ast }=v. Thus, N(v^{\ast })\setminus \{v\}=N(v)\setminus \{v^{\ast }\}. For each z\in C_1(v), we have N(z)\cap N(v)=N(v)\setminus \{v^{\ast }\}=N(v^{\ast })\setminus \{v\}, which implies that z\in C_1(v^{\ast }). Similarly, for each y\in C_1(v^{\ast }), we infer that y\in C_1(v). Thus, C_1(v)=C_1(v^{\ast }), and so C_1[v]\cup \{v^{\ast }\}=C_1[v^{\ast }]\cup \{v\}. By assumption C_1[u]\cup \{u^{\ast }\}\ne C_1[v]\cup \{v^{\ast }\}, we get u\ne v^{\ast }. Hence u\in C_1[v]. On the other hand, if u=v, then C_1[u]\cup \{u^{\ast }\}=C_1[v]\cup \{v^{\ast }\}. Thus, u\ne v. This shows that u\in C_1(v), that is u and v are not adjacent and N(v)\cap N(u)=N(v)\setminus \{v^{\ast }\}=N(u)\setminus \{u^{\ast }\}.

Consider the vertex u^{\ast }. We know that u^{\ast } and u are adjacent and they share k-1 common neighbours. If there is a vertex u^{\ast }\in N(v), then the number of neighbours of u^{\ast } is k+1. This leads to a contradiction since G is k-regular. Thus u^{\ast }\notin N(v), that is, u^{\ast } is not adjacent to v. Recall that u\in C_1(v), so we infer that u and v are not adjacent and they share k-1 common neighbours. We see at once that u^{\ast } and v have exactly k-1 common neighbours. Therefore, u^{\ast } belongs to C_1(v).

Finally, from C_1[u]\cup \{u^{\ast }\}\ne C_1[v]\cup \{v^{\ast }\}, let w\in (C_1[u]\cup \{u^{\ast }\})\setminus (C_1[v]\cup \{v^{\ast }\}). By u^{\ast }\in C_1(v), it follows that w\ne u^{\ast }. Since u\in C_1[v]\cup \{v^{\ast }\}, w\ne u. So w\in C_1(u)\setminus (C_1[v]\cup \{v^{\ast }\}). Thus, N(w)\cap N(u)=N(u)\setminus \{u^{\ast }\}=N(u)\cap N(v)=N(v)\setminus \{v^{\ast }\} (where w\ne v,v^{\ast }) holds, which leads to N(w)\cap N(v)=N(v)\setminus \{v^{\ast }\}, so w\in C_1(v). This contradicts w\notin C_1[v]\cup \{v^{\ast }\}, which completes the proof.□

Lemma 3.3　 Let G be a generalized strongly regular graph of grade 2 with parameter (n,k;k-1,a_2;k-1,c_2) and v be a vertex of G. Then, for each u\in N(v)\setminus \{v^{\ast }\}, we have C_1[u]\cup \{u^{\ast }\}\subseteq N(v)\setminus \{v^{\ast }\}.

Proof　On the contrary, suppose that there is a vertex u^{\prime }\in (C_1[u]\cup \{u^{\ast }\})\mathrm{\setminus }(N(v)\setminus \{v^{\ast }\}).

Since u\in N(v)\setminus \{v^{\ast }\}, u\in A_2(v). Thus, |N(u)\setminus N[v]|=k-a_2-1. As , k-a_2-1>0, that is, N(u)\setminus N[v]\ne \mathrm{\varnothing }. Since w is not adjacent to v for each w\in N(u)\setminus N[v] and u^{\ast } is adjacent to each vertex in N(u)\setminus \{u^{\ast }\}, we get w,v\ne u^{\ast }. So, u^{\ast }\in N(v)\cap N(u).

By assumption u^{\prime }\notin N(v)\setminus \{v^{\ast }\}, we have u^{\prime }\ne u, which implies u^{\prime }\in C_1(u)\cup \{u^{\ast }\}.

(1) If u^{\prime }=u^{\ast }, then u^{\prime }\in N(v)\cap N(u) follows from u^{\ast }\in N(v)\cap N(u). This contradicts u^{\prime }\notin N(v)\setminus \{v^{\ast }\}.

(2) If u^{\prime }\in C_1(u), then u^{\prime } and u are not adjacent and they have k-1 common neighbours. Thus, both v and v^{\ast } belong to N(u) as u\in N(v)\setminus \{v^{\ast }\}. Therefore, u^{\prime } is adjacent to v and v^{\ast }, and so u^{\prime }\in N(v)\setminus \{v^{\ast }\}. But this contradicts u^{\prime }\notin N(v)\setminus \{v^{\ast }\}.

From above, we conclude that C_1[u]\cup \{u^{\ast }\}\subseteq N(v)\setminus \{v^{\ast }\}.□

The proof of Theorem 3.1

Proof　Let us prove the necessity first. We define the relation R on the vertex set of G as: uRv\iff v\in C_1[u]\cup \{u^{\ast }\}. Lemma 3.2 implies that the relation R is an equivalence relation.

(1) Reflexive: u\in C_1[u]\cup \{u^{\ast }\}\iff uRu.

(2) Symmetry: we know uRv\iff v\in C_1[u]\cup \{u^{\ast }\}, hence C_1[u]\cup \{u^{\ast }\}=C_1[v]\cup \{v^{\ast }\}, and finally u\in C_1[v]\cup \{v^{\ast }\}\iff vRu.

(3) Transitivity: since uRv\iff v\in C_1[u]\cup \{u^{\ast }\}, vRw\iff w\in C_1[v]\cup \{v^{\ast }\}. Thus, C_1[v]\cup \{v^{\ast }\}=C_1[u]\cup \{u^{\ast }\}=C_1[w]\cup \{w^{\ast }\}. Therefore, w\in C_1[u]\cup \{u^{\ast }\}\iff uRw.

Clearly, each equivalence class has the same size t_1+2.

Now, we define G_1 and G_2. Let n_2=t_1+2, G_2=\frac{n_2}{2}{K}_2. Set V(G_2)=\{u_1,u_2,\dots ,u_{n_2}\}. The graph G_1 is defined to have the equivalence classes as its vertices, and two vertices E_1 and E_2 are defined to be adjacent if and only if there exists a vertex v\in E_1 and a vertex u\in E_2 such that u and v are adjacent in G. Obviously, |V(G_1)|=\frac{n}{t_1+2}. In view of Lemma 3.3, the degree of each vertex is \frac{k-1}{t_1+2}.

Let E_1,E_2 be two distinct vertices in V(G_1) and v\in E_1,u\in E_2, where v,u\in V(G). According to the equivalence relation R, we detail the number of vertices from N(E_1)\cap N(E_2) in G_1.

(1) Suppose that u and v are not adjacent and they have c_2 common neighbours. In this case, v^{\ast },u^{\ast }\notin N(v)\cap N(u). However, Lemma 3.3 implies that N(v)\cap N(u) contains C_1[w]\cup \{w^{\ast }\} for each w\in N(v)\cap N(u). Thus, there are exactly \frac{c_2}{t_2+2} common neighbours between E_1 and E_2.

(2) Suppose that u and v are not adjacent and they share a_2 common neighbours. In this case, v^{\ast },u^{\ast }\in N(v)\cap N(u). Furthermore, N(v)\cap N(u) contains C_1[w]\cup \{w^{\ast }\} for each w\in (N(v)\cap N(u)). Thus, there are exactly \frac{a_2-2}{t_2+2} common neighbours between E_1 and E_2.

From above, G_1 is a strongly regular graph with parameters (n_1,k_1,\lambda ,\mu ), where n_1=\frac{n}{n_2},k_1=\frac{k-1}{n_2},\lambda =\frac{a_2-2}{n_2},\mu =\frac{c_2}{n_2}.

We next show that G is isomorphic to G_1[G_2]. Let the equivalence class E_i be \{v_{i1},v_{i2},\dots ,v_{i{n}_2}\}. Let us first prove that f(E_i,u_j)=v_{ij} is a graph isomorphism from G_1[G_2] to G.

Let (E_i,u_j),(E_{i^{\prime }},u_{j^{\prime }}) be two distinct vertices in G_1[G_2]. Clearly, f is a bijection. Thus we need to show that v_{ij} is adjacent to v_{i^{\prime }{j}^{\prime }} if and only if (E_i,u_j) is adjacent to (E_{i^{\prime }},u_{j^{\prime }}).

By the definition of composition of graphs, we conclude that if i\ne i^{\prime }, then (E_i,u_j) and (E_{i^{\prime }},u_{j^{\prime }}) are adjacent if and only if E_i and E_{i^{\prime }} are adjacent; if i=i^{\prime }, then (E_i,u_j) and (E_{i^{\prime }},u_{j^{\prime }}) are adjacent if and only if u_j and u_{j^{\prime }} are adjacent. Thus, we have the following two cases.

Case 1　 i\ne i^{\prime }. If v_{ij} is adjacency to v_{i^{\prime }{j}^{\prime }}, then E_i is adjacent to E_{i^{\prime }}. If E_i and E_{i^{\prime }} are adjacent, then there is a vertex v_{il}\in E_i and a vertex v_{i^{\prime }{l}^{\prime }}\in E_{i^{\prime }} such that v_{il} is adjacent to v_{i^{\prime }{l}^{\prime }}. Notice that v_{ij}\in E_i, which shows that there are k-1 common neighbours between v_{ij} and v_{il}. Suppose that v_{ij} and v_{il} are adjacent, then N[v_{ij}]=N[v_{il}]. Thus, v_{ij} is adjacent to v_{i^{\prime }{l}^{\prime }}. Suppose that v_{ij} and v_{il} are not adjacent. If v_{i^{\prime }{l}^{\prime }}\notin N(v_{ij})\cap N(v_{il}), then v_{i^{\prime }{l}^{\prime }}=v_{il}^{\ast }, which leads to v_{i^{\prime }{l}^{\prime }}\in E_i, a contradiction. Therefore, v_{i^{\prime }{l}^{\prime }}\in N(v_{ij})\cap N(v_{il}). Hence v_{ij} is adjacent to v_{i^{\prime }{l}^{\prime }}. Moreover, v_{i^{\prime }{j}^{\prime }} and v_{i^{\prime }{l}^{\prime }} are in the same equivalence class. In the same manner, we can see that v_{i^{\prime }{j}^{\prime }} and v_{ij} are adjacent.

Case 2　 i=i^{\prime }. To prove that f is a graph isomorphism, it suffices to show that v_{ij} is adjacency to v_{i^{\prime }{j}^{\prime }} if and only if u_j is adjacent to u_{j^{\prime }}. The conclusion clearly holds.

From above, f is a graph isomorphism.

Since G is a generalized strongly regular graph of grade 2 with parameter (n,k;k-1,a_2;k-1,c_2), we know k-1\ne a_2 and k-1\ne c_2. This yields k_1{n}_2\ne \lambda n_2+2 and k_1{n}_2\ne \mu n_2. Thus, \mu \ne k_1 and when n_2=2, \lambda \ne k_1-1.

Next we prove sufficiency.

It is known that G is isomorphic to G_1[G_2], where G_1 is a strongly regular graph with parameter (n_1,k_1,\lambda ,\mu ) and G_2 is \frac{n_2}{2}{K}_2. This means that the parameters of graph G are (n_1{n}_2,k_1{n}_2+1,k_1{n}_2,\lambda n_2+2,k_1{n}_2,\mu n_2). From \mu \ne k_1 and when n_2=2, \lambda \ne k_1-1, it is obvious that a_1=c_1=k-1 and a_1\ne a_2,c_1\ne c_2.

On the other hand, for an arbitrary vertex v_{ij}\in V(G), there are \frac{k-1}{n_2}\cdot n_2=k-1 vertices v_{i^{\prime }{j}^{\prime }}(i^{\prime }\ne i) which are adjacent to v_{ij} and there is a unique vertex v_{i{j}^{\prime }} that is adjacent to v_{ij}. However, there are \lambda n_2+2=a_2 common neighbours which between v_{ij} and v_{i^{\prime }{j}^{\prime }}(i^{\prime }\ne i). Thus, for any vertex v_{ij}\in V(G), there is a unique vertex which is adjacent to v_{ij} and share k-1 common neighbours with v_{ij}, that is, s_1(v_{ij})=1>0.

The number of vertices v_{i^{\prime }{j}^{\prime }}(i^{\prime }\ne i) which are not adjacent to v_{ij} is (n_1-\frac{k-1}{n_2})n_2=n-k+1; the number of vertices v_{i{j}^{\prime }} which are not adjacent to v_{ij} is n_2-1. However, v_{ij} and v_{i^{\prime }{j}^{\prime }}(i^{\prime }\ne i) have \mu n_2=c_2 common neighbours, and v_{ij} share k_1{n}_2=k-1 vertices with v_{i{j}^{\prime }}. That means, for any vertex v_{ij}\in V(G), there are n_2-1 vertices that are not adjacent to v_{ij} and share k-1 common neighbours with v_{ij}. Moreover, as n_2⩾2, we have (n_2-1)⩾1. Thus, t_1(v_{ij})>0. So, G is a generalized strongly regular graph of grade 2 and type (A).□

In fact, Fig.1 is a composition of a strongly regular graph with parameters (5,2,0,1) and K_2; Fig.3 is a composition of a strongly regular graph with parameters (5,2,0,1) and 2K_2.

References

[1] BrouwerA ECohenA MNeumaierA. Distance-Regular Graphs. Berlin: Springer-Verlag, 1989

[2] BrouwerA EHaemersW H. Spectra of Graphs. Universitext. New York: Springer, 2012

[3] Erickson M, Fernando S, Haemers W H, Hardy D, Hemmeter J. Deza graph: a generalization of strongly regular graphs. J Combin Des 1999; 7(6): 395–405

[4] Goldberg F. On quasi-strongly regular graphs. Linear Multilinear Algebra 2006; 54(6): 437–451

[5] Golightly W L, Haynsworth W H, Sarvate D G. A family of connected quasi-strongly regular graphs. Congr Numer 1997; 124: 89–95

[6] Huo L, Zhang G. Subconstituents of the orthogonal graph of type (m,m−1,0) of odd characteristic. Linear Algebra Appl 2017; 524: 1–12

[7] Jia D D, Yuan L D, Zhang G S. On generalized strongly regular graphs. Graphs Combin 2018; 34(4): 555–570

[8] Kabanov V V, Maslova L V, Shalaginov L V. On strictly Deza graphs with parameters (n,k,k−1,a). European J Combin 2019; 80: 194–202

[9] Kabanov V V, Shalaginov L V. Deza graphs with parameters (v,k,k−2,a). J Combin Des 2020; 28(9): 658–669

RIGHTS & PERMISSIONS

Higher Education Press 2023