New constructions of Deza digraphs

Document Type : 2022 CCGTA IN SOUTH FLA


1 Faculty of Mathematics, University of Rijeka, Rijeka, Croatia

2 Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Canada

3 Department of Mathematics, National Defense Academy of Japan, 2-10-20 Hashirimizu, Yokosuka, Kanagawa, Japan


Deza digraphs were introduced in 2003 by Zhang and Wang as directed graph version of Deza graphs, that also generalize the notion of directed strongly regular graphs. In this paper, we give several new constructions of Deza digraphs. Further, we introduce twin and Siamese twin (directed) Deza graphs and construct several examples. Finally, we study a variation of directed Deza graphs and provide a construction from finite fields.


Main Subjects

[1] E. Bannai and T. Ito, Algebraic combinatorics I: Association schemes, Benjamin-Cummings Lecture Note Series,
58, Benjamin/Cummings, London, 1984.
[2] D. Crnković and H. Kharaghani, Divisible design digraphs, Algebraic design theory and Hadamard matrices, Springer Proc. Math. Stat., 133, Springer, Cham, 2015 43–60.
[3] Database of small strictly Cayley-Deza graphs, Available at:,
Accessed on 5/2/2023.
[4] A. Duval, A directed graph version of strongly regular graphs, J. Combin. Theory Ser. A, 47 (1988) 71–100.
[5] M. Erickson, S. Fernando, W. H. Haemers, D. Hardy and J. Hemmeter, Deza graphs: A generalization of strongly
regular graphs, J. Combin. Des., 7 (1999) 395–405.
[6] T. Feder and P. Hell, List homomorphisms to reflexive graphs, J. Combin. Theory Ser. B, 72 (1998) 236–250.
[7] W. Fish, J. D. Key and E. Mwambene, Ternary codes from some reflexive uniform subset graphs, Appl. Algebra
Engrg. Comm. Comput., 25 (2014) 363–382.
[8] R. W. Goldbach and H. L. Claasen, 3-class association schemes and Hadamard matrices of a certain block form,
Europ. J. Combin., 19 (1998) 943–951.
[9] S. Goryainov, W. H. Haemers, V. Kabanov and L. Shalaginov, Deza graphs with parameters (n, k, k − 1, a) and
β = 1, J. Combin. Des., 27 (2019) 188–202.
[10] S. Goryainov and D. Panasenko, On vertex connectivity of Deza graphs with parameters of the complements to
Seidel graphs, European J. Combin., 80 (2019) 143–150.
[11] W. H. Haemers, H. Kharaghani and M. A. Meulenberg, Divisible Design Graphs, J. Combin. Theory Ser. A, 118
(2011) 978–992.
[12] A. Hanaki and I. Miyamoto, Classification of association schemes of small order, Discrete Math., 264 (2003) 75–80.
[13] N. Ito, On spectra of doubly regular asymmetric digraphs of RH-type, Graphs Combin., 5 (1989) 229–234.
[14] Z. Janko and H. Kharaghani, A block negacyclic Bush-type Hadamard matrix and two strongly regular graphs, J.
Combin. Theory Ser. A, 98 (2002) 118–126.
[15] E. M. Jawhari, M. Pouzet and I. Rival, A classification of reflexive graphs: the use of “holes”, Canad. J. Math., 38
(1986) 1299–1328.
[16] L. Jørgensen, On normally regular digraphs, Preprint R-94-2023, Institute for Electronic Systems, Aalborg University (1994), Revised version (1999).
[17] L. Jørgensen, G. Jones, M. Klin and S. Y. Song, Normally regular digraphs, association schemes and related
combinatorial structures, Sém. Lothar. Combin., 71 (2013/14) 39 pp.
[18] V. Kabanov, N. V. Maslova and L. V. Shalaginov, On strictly Deza graphs with parameters (n, k, k − 1, a), European J. Combin., 80 (2019) 194–202.
[19] H. Kharaghani, On the twin designs with the Ionin-type parameters, Electron. J. Combin., 7 (2000) 11 pp.
[20] H. Kharaghani, On the Siamese twin designs, Finite fields and applications (Augsburg, 1999), Springer, Berlin, 2001 303–312.
[21] H. Kharaghani, S. Sasani and S. Suda, A strongly regular decomposition of the complete graph and its association scheme, Finite Fields Appl., 48 (2017) 356–370.
[22] H. Kharaghani and S. Suda, Hoffman’s coclique bound for normal regular digraphs, and nonsymmetric association schemes, Mathematics Across Contemporary Sciences, Springer Proc. Math. Stat., 190, Springer, Cham, 2017 137–150.
[23] H. Kharaghani, S. Suda and B. Tayfeh-Razaie, Disjoint weighing matrices, J. Algebraic Combin., 55 (2022) 27–41.
[24] K. Wang and Y. Feng, Deza digraphs, European J. Combin., 27 (2006) 995–1004.
[25] K. Wang and F. Li, Deza digraphs II, European J. Combin., 29 (2008) 369–378.
[26] G. Zhang and K. Wang, A directed version of Deza graphs – Deza digraphs, Australas. J. Combin., 28 (2003)
Volume 13, Issue 3 - Serial Number 3
September 2024
Pages 225-240
  • Receive Date: 30 December 2022
  • Revise Date: 12 February 2023
  • Accept Date: 20 February 2023
  • Published Online: 01 September 2024