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

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