A Deza graph with parameters $(n,k,b,a)$ is a $k$-regular graph with $n$ vertices in which any two vertices have $a$ or $b$ ($a\leq b$) common neighbours. A Deza graph is strictly Deza if it has diameter $2$, and is not strongly regular. In an earlier paper, the two last authors et el. characterized the strictly Deza graphs with $b=k-1$ and $\beta > 1$, where $\beta$ is the number of vertices with $b$ common neighbours with a given vertex. Here we deal with the case $\beta=1$, thus we complete the characterization of strictly Deza graphs with $b=k-1$. It follows that all Deza graphs with $b=k-1$ and $\beta=1$ can be made from special strongly regular graphs, and we present several examples of such strongly regular graphs. A divisible design graph is a special Deza graph, and a Deza graph with $\beta=1$ is a divisible design graph. The present characterization reveals an error in a paper on divisible design graphs by the second author et al. We discuss the cause and the consequences of this mistake and give the required errata.
- Deza graph
- divisible design graph
- dual Seidel switching
- strongly regular graph
Goryainov, S., Haemers, W. H., Kabanov, V. V., & Shalaginov, L. (2019). Deza graphs with parameters $(n,k,k-1,a)$ and $β=1$. Journal of Combinatorial Designs, 27(3), 188-202. https://doi.org/10.1002/jcd.21644