Deza graphs with parameters (n, k, k−1, a) and β=1. Issue 3 (18th December 2018)

• Record Type: Journal Article
• Authors: Goryainov, Sergey; Haemers, Willem H.; Kabanov, Vladislav V.; Shalaginov, Leonid
• Is Part Of: Journal of combinatorial designs. Volume 27:Issue 3(2019:Mar.)
• Page Start: 188
• Page End: 202
• Publication Date: 2018-12-18
• Subjects: Deza graph -- divisible design graph -- dual Seidel switching -- involution -- strongly regular graph; Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21644
• Languages: English
• ISSNs: 1063-8539

Abstract

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 ≤ b ) common neighbours. A Deza graph is strictly Deza if it has diameter 2, and is not strongly regular. In an earlier paper, the two last authors et al characterised the strictly Deza graphs with b = k − 1 and β > 1, where β 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 β = 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, β = 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 β = 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.