A k-regular graph on v vertices is called a
Deza graph with parameters (v, k, b, a) if the number of common neighbours of two distinct vertices takes just two values, b or a, where b ≥ a. A Deza graph of diameter 2 which is not a strongly regular graph is called a
strictly Deza graph. Deza graphs were introduced in [1] as a generalisation of strongly regular graphs.
A k-regular graph on v vertices is called a
divisible design graph with parameters (v, k, λ
1, λ
2, m, n) if its vertex set can be partitioned into m classes of size n, such that two distinct vertices from the same class have exactly λ
1 common neighbours, and two vertices from different classes have exactly λ
2 common neighbours. A divisible design graph with m = 1, n = 1, or λ
1 = λ
2 is called
improper, otherwise it is called
proper. The definition implies that all divisible design graphs are Deza graphs. Divisible design graphs with λ
1 = 0 or λ
2 = 0 may have diameter 3 and thus not be strictly Deza graphs. Divisible design graphs were first studied in master's thesis by M.A. Meulenberg [40] and studied in more details in the following papers [41, 42], with corrections about classification of graphs with λ
1 = k – 1 provided in [43] and about the existence of graphs with parameters (27, 8, 4, 2, 9, 3) provided in [46].
For more detailed information on Deza graphs in general see a survey [34] by S. Goryainov and L. Shalaginov.
References
The numbering of sources is taken from the bibliography.
[1] M. Erickson, S. Fernando, W.H. Haemers, D. Hardy, J. Hemmeter, Deza graphs: A generalization of strongly regular graphs, Journal of Combinatorial Designs, 7 (1999) 395–405. doi.org/10.1002/(SICI)1520-6610(1999)7:6<395::AID-JCD1>3.0.CO;2-U
[34] S. Goryainov, L. Shalaginov, Deza graphs: a survey and new results, (2021). arxiv.org/abs/2103.00228
[40] M.A. Meulenberg, Divisible design graphs, Master's thesis, Tilburg University (2008). pdf
[41] W.H. Haemers, H. Kharaghani, M.A. Meulenberg, Divisible design graphs, Journal of Combinatorial Theory, Series A, 118 (2011) 978–992. doi.org/10.1016/j.jcta.2010.10.003
[42] D. Crnković, W.H. Haemers, Walk-regular divisible design graphs, Designs, Codes and Cryptography, 72 (2014) 165–175. doi.org/10.1007/s10623-013-9861-0
[43] S. Goryainov, W.H. Haemers, V.V. Kabanov, L. Shalaginov, Deza graphs with parameters (n, k, k–1, a) and β = 1, Journal of Combinatorial Designs, 27 (2019) 188–202. doi.org/10.1002/jcd.21644
[46] D. Panasenko, L. Shalaginov, Classification of divisible design graphs with at most 39 vertices, Journal of Combinatorial Designs, 30(4) (2022) 205–219. doi.org/10.1002/jcd.21818