MSC: 05B10, 20C05, 05E30
DOI: 10.21538/0134-4889-2025-31-4-281-289
The author was supported by the state contract of the Sobolev Institute of Mathematics (project number FWNF-2022-0017).
A regular graph $\Gamma$ is called a Deza graph if there exist nonnegative integers $a$ and $b$ such that any two distinct vertices of $\Gamma$ have either $a$ or $b$ common neighbors. A subset $R$ of a group $G$ is called a relative difference set in $G$ if there exist a subgroup $N$ of $G$ and a nonnegative integer $\lambda$ such that every element of $G\setminus N$ has exactly $\lambda$ representations in the form $g_1g_2^{-1}$, where $g_1,g_2\in R$, and no non-identity element of $N$ has such a representation. If $N$ is trivial, then $R$ is defined to be a difference set. In the present paper, we provide several new constructions of Deza Cayley graphs over groups having a generalized dihedral subgroup. These constructions are based on usage of (relative) difference sets.
Keywords: Deza graphs, Cayley graphs, difference sets
REFERENCES
1. Akbari S., Ghodrati A.H., Hosseinzadeh M.A., Kabanov V.V., Konstantinova E.V., Shalaginov L. Spectra of Deza graphs. Linear Multilinear A., 2020, vol. 70, no. 2, pp. 310–321.
2. Akbari S., Haemers W.H., Hosseinzadeh M.A., Kabanov V.V., Konstantinova E.V., Shalaginov L. Spectra of strongly Deza graphs. Discrete Math., 2021, vol. 344, no. 12, article ID 112622.
3. Arasu K.T., Dillon J.F., Leung K.H., Ma S.L. Cyclic relative difference sets with classical parameters. J. Comb. Theory Ser. A, 2001, vol. 94, pp. 118–126.
4. Beth T., Jungnickel D., Lenz H. Design Theory, 2nd ed. Cambridge, Cambridge University Press, 1999.
5. Bildanov R., Panshin V., Ryabov G. On WL-rank and WL-dimension of some Deza circulant graphs. Graphs Combin., 2021, vol. 37, no. 6, pp. 2397–2421.
6. Brouwer A.E., Maldeghem H.Van. Strongly regular graphs. Encyclopedia of mathematics and its applications. Cambridge, Cambridge University Press, 2022, vol. 182.
7. Churikov D., Ryabov G. On WL-rank of Deza Cayley graphs. Discrete Math., 2022, vol. 345, no. 2, article ID 112692.
8. Davis J.A., Jedwab J. A new family of relative difference sets in 2-groups. Des. Codes Cryptogr., 1998, vol. 17, pp. 305–312.
9. Deza A., Deza M. The ridge graph of the metric polytope and some relatives. In: eds. T. Bisztriczky et al. Polytopes: Abstract, convex and computational, NATO ASI Series, vol. 440, Dordrecht, Springer, 1994, pp. 359–372. https://doi.org/10.1007/978-94-011-0924-6_16
10. Erickson M., Fernando S., Haemers W., Hardy D., Hemmeter J. Deza graphs: a generalization of strongly regular graphs. J. Comb. Designs., 1999, vol. 7, pp. 359–405.
11. Gavrilyuk A., Goryainov S., Kabanov V. On the vertex connectivity of Deza graphs. Proc. Steklov Inst. Math. (Suppl 1), 2014. vol. 285, Suppl. 1, pp. 68–77.
12. Gordon D. Database of difference sets. https://www.dmgordon.org/diffset/
13. Goryainov S. , W. H. Haemers, V. Kabanov, L. Shalaginov. Deza graphs with parameters $(n,k,k-1,a)$ and $\beta=1$. J. Comb. Des., 2019, vol. 27, pp. 188–202.
14. Goryainov S., Panasenko D. On vertex connectivity of Deza graphs with parameters of complements to Seidel graphs. Eur. J. Comb., 2019, vol. 80, pp. 143–150.
15. Goryainov S., Panasenko D., Shalaginov L. Enumeration of strictly Deza graphs with at most 21 vertices. Sib. Elect. Math. Rep., 2021, vol. 18, no. 2, pp. 1423–1432.
16. Goryainov S., Shalaginov L. Cayley–Deza graphs with less than 60 vertices. Sib. Elect. Math. Rep., 2014, vol. 11, pp. 268–310.
17. Goryainov S., Shalaginov L. Deza graphs: a survey and new results. 2021, 30 p. https://doi.org/10.48550/arXiv.2103.00228
18. Haemers W.H., Kharaghani H., Meulenberg M.A. Divisible design graphs J. Combin. Theory, Ser. A. 2011, vol. 118, pp. 978–992.
19. Kabanov V., Konstantinova E., Shalaginov L. Generalised dual Seidel switching and Deza graphs with strongly regular children. Discrete Math., 2021, vol. 344, no. 3, article ID 112238.
20. Kabanov V., Maslova N., Shalaginov L. On strictly Deza graphs with parameters $(n,k,k-1,a)$. Eur. J. Comb., 2019, vol. 80, pp. 194–202.
21. Kabanov V., Shalaginov L. Deza graphs with parameters $(n,k,k-2,a)$. J. Comb. Des., 2020, vol. 28, pp. 658–669.
22. Lam C. W. H. On relative difference sets. In: Proc. 7th Manitoba Conference on Numerical Mathematics and Computing, 1977, pp. 445–474.
23. Ma S. L., Schmidt B. On $(p^a,p,p^a,p^{a-1})$-relative difference sets. Des. Codes Cryptogr., 1995, vol. 6, pp. 57–71.
24. Panasenko D. Strictly Deza graphs, database. http://alg.imm.uran.ru/dezagraphs/main.html
25. Pott A. A survey on relative difference set. In: Groups, Difference Sets, and the Monster, eds. K. T. Arasu et al., Berlin, Walter de Gruyter, 1996, pp. 195–232.
26. Ryabov G. Divisible design graphs from Higmanian association schemes. In: Book of Abstracts of the 8th Workshop on “Algebraic Graph Theory and its Applications” (March 1–4, 2023, ZoomConference). Novosibirsk, 2023.
27. Ryabov G., Shalaginov L. On WL-rank and WL-dimension of some Deza dihedrants. Zapiski Nauchnykh Seminarov POMI, 2022, vol. 518, pp. 152–172.
Received August 10, 2025
Revised September 2, 2025
Accepted September 8, 2025
Funding Agency: The author was supported by the state contract of the Sobolev Institute of Mathematics (project number FWNF-2022-0017).
Grigory Konstantinovich Ryabov, Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: gric2ryabov@gmail.com
Cite this article as: G.K. Ryabov. Deza Cayley graphs from difference sets. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 4, pp. 281–289.
Русский
Г.К. Рябов. Графы Кэли — Деза, построенные из разностных множеств
Регулярный граф $\Gamma$ называется графом Деза, если существуют целые неотрицательные числа $a$ и $b$ такие, что каждые две различные вершины графа $\Gamma$ имеют $a$ или $b$ общих соседей. Подмножество $R$ группы $G$ называется относительным разностным множеством в $G$, если существуют подгруппа $N$ группы $G$ и целое неотрицательное число $\lambda$ такие, что каждый элемент множества $G\setminus N$ имеет в точности $\lambda$ представлений вида $g_1g_2^{-1}$, где $g_1,g_2\in R$, и никакой нетривиальный элемент подгруппы $N$ не может быть представлен в таком виде. Если $N$ тривиальна, то $R$ называется разностным множеством. В настоящей статье приводятся некоторые новые конструкции графов Кэли-Деза над группами, содержащими обобщенную диэдральную подгруппу. В основе этих конструкций лежат (относительные) разностные множества.
Ключевые слова: графы Деза, графы Кэли, разностные множества
