## Abstract

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 1, where beta is the number of vertices with b common neighbours with a given vertex. Here, we start with a characterisation of Deza graphs (not necessarily strictly Deza graphs) with parameters (n, k, k - 1, 0). Then, we deal with the case beta = 1 and a > 0, and thus complete the characterisation of Deza graphs with b = k - 1. It follows that all Deza graphs with b = k - 1, beta = 1 and a > 0 can be made from special strongly regular graphs, and in fact are strictly Deza except for K-2. We present several examples of such strongly regular graphs. A divisible design graph (DDG) is a special Deza graph, and a Deza graph with beta = 1 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.

Original language | English |
---|---|

Pages (from-to) | 188-202 |

Journal | Journal of Combinatorial Designs |

Volume | 27 |

Issue number | 3 |

DOIs | |

Publication status | Published - Mar 2019 |

## Keywords

- Deza graph
- divisible design graph
- dual Seidel switching
- involution
- strongly regular graph