RESEARCH ARTICLE

A family of generalized strongly regular graphs of grade 2

  • Simin SONG 1 ,
  • Lifang YANG 2 ,
  • Gengsheng ZHANG , 1,3
Expand
  • 1. College of Mathematics Science, Hebei Normal University, Shijiazhuang 050024, China
  • 2. Department of Basic Education, Shijiazhuang Engineering Vocational College, Shijiazhuang 050061, China
  • 3. Hebei Key Laboratory of Computational Mathematics and Applications, Shijiazhuang 050024, China
gshzhang@hebtu.edu.cn

Copyright

2023 Higher Education Press 2023

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;a1,a2;c1,c2), if the number of the vertices that are adjacent to v and share ai(i=1,2) common neighbours with v, or are non-adjacent to v and share ci(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;k1,a2;k1,c2) and provide the sufficient and necessary conditions for the existence of a family of free generalized strongly regular graphs of grade 2.

Cite this article

Simin SONG , Lifang YANG , Gengsheng ZHANG . A family of generalized strongly regular graphs of grade 2[J]. Frontiers of Mathematics in China, 2023 , 18(1) : 33 -42 . DOI: 10.3868/S140-DDD-023-001-X

Acknowledgments

This research is partially supported by National Natural Science Foundation of China (No.11571091), Natural Science Foundation of Hebei Province, China (No.F2019205147) and Innovation Program of Hebei Normal University, China (No.CXZZSS2020050).
The authors would also like to thank the referees and editors for their valuable suggestions which have helped improve this paper.
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

Outlines

/