Spectra of strongly Deza graphs (Q2231732)

A graph \(\Gamma\) is called strongly regular with parameters \((n,k,\lambda,\mu)\) if it has \(n\) vertices, is regular of valency \(k\), any two adjacent vertices have exactly \(\lambda\) common neighbors and any two distinct and non-adjacent vertices have exactly \(\mu\) common neighbors. The study of strongly regular graphs is an important part of algebraic combinatorics (see [\textit{A. E. Brouwer} and \textit{H. Van Maldeghem}, Strongly regular graphs. Cambridge: Cambridge University Press (2022; Zbl 1498.05001)]). A graph \(\Gamma\) is called a Deza graph with parameters \((n,k,b,a)\) if it has \(n\) vertices, is regular of valency \(k\) and any two distinct vertices have either \(a\) or \(b\) common neighbors. A strongly regular graph is a Deza graph, but the converse is not true. There are many examples of Deza graphs that are not strongly regular, but perhaps the simplest one is the graph obtained from two copies of the complete graph \(K_4\) by adding a perfect matching between them. This is a \((8,4,2,0)\) Deza graph, but not a strongly regular graph. Deza graphs were formally introduced in [\textit{M. Erickson} et al., J. Comb. Des. 7, No. 6, 395--405 (1999; Zbl 0959.05122)] although an example of \((40,15,5,4)\) was discovered in [\textit{A. Deza} and \textit{M. Deza}, NATO ASI Ser., Ser. C, Math. Phys. Sci. 440, 359--372 (1994; Zbl 0809.52017)]. The children \(\Gamma_A\) and \(\Gamma_B\) of a Deza graph \(\Gamma\) have the same vertex set as \(\Gamma\) and two distinct vertices are adjacent in \(\Gamma_A\) or \(\Gamma_B\) if and only if they have exactly \(a\) or \(b\) common neighbors, respectively. A strongly Deza graph is a Deza graph with strongly regular children. In this paper, the authors obtain a spectral characterization of strongly Deza graphs and study strongly Deza graphs that are either distance-regular graphs or cospectral with distance-regular graphs.