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

Cite this