A family of generalized strongly regular graphs of grade 2

Simin SONG; Lifang YANG; Gengsheng ZHANG

doi:10.3868/S140-DDD-023-001-X

PDF(1305 KB)

Front. Math. China ›› 2023, Vol. 18 ›› Issue (1) : 33-42. DOI: 10.3868/S140-DDD-023-001-X

RESEARCH　ARTICLE

A family of generalized strongly regular graphs of grade 2

Author information +

History +

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; a 1, a 2; 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; k − 1,$ $a 2; 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

Cite this article

EndNote

Ris (Procite)

Bibtex

Download citation ▾

Simin SONG, Lifang YANG, Gengsheng ZHANG. A family of generalized strongly regular graphs of grade 2. Front. Math. China, 2023, 18(1): 33‒42 https://doi.org/10.3868/S140-DDD-023-001-X

References

Publishing order | Descend order by publishing year | Descend order by cited within

[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

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.