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

Sergey Goryainov, Willem H. Haemers, Vladislav V. Kabanov, Leonid Shalaginov

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)

## 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 188-202 Journal of Combinatorial Designs 27 3 https://doi.org/10.1002/jcd.21644 Published - Mar 2019

## Keywords

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

## Fingerprint

Dive into the research topics of 'Deza graphs with parameters \$(n,k,k-1,a)\$ and \$β=1\$'. Together they form a unique fingerprint.