Deza graphs with parameters and

Abstract

Abstract A Deza graph with parameters is a ‐regular graph with vertices, in which any two vertices have or ( ) common neighbours. A Deza graph is strictly Deza if it has diameter , and is not strongly regular. In an earlier paper, the two last authors et al characterised the strictly Deza graphs with and , where is the number of vertices with common neighbours with a given vertex. Here, we start with a characterisation of Deza graphs (not necessarily strictly Deza graphs) with parameters . Then, we deal with the case and , and thus complete the characterisation of Deza graphs with . It follows that all Deza graphs with , and can be made from special strongly regular graphs, and in fact are strictly Deza except for . We present several examples of such strongly regular graphs. A divisible design graph (DDG) is a special Deza graph, and a Deza graph with is a DDG. The present characterisation reveals an error in a paper on DDGs by the second author et al. We discuss the cause and the consequences of this mistake and give the required errata.