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

9 Citations (Scopus)


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 languageEnglish
Pages (from-to)188-202
JournalJournal of Combinatorial Designs
Issue number3
Publication statusPublished - Mar 2019


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


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

Cite this