Deza graphs with parameters $(n,k,k-1,a)$ and $β=1$

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 $β> 1$, where $β$ is the number of vertices with $b$ common neighbours with a given vertex. Here we deal with the case $β=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 $β=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 $β=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.

No reviews yet.

No comments yet.