Deza–Cayley graphs from difference sets

[Графы Кэли — Деза, построенные из разностных множеств]

G. K. Ryabov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Аннотация: Регулярный граф $\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$ называется разностным множеством. В настоящей статье приводятся некоторые новые конструкции графов Кэли-Деза над группами, содержащими обобщенную диэдральную подгруппу. В основе этих конструкций лежат (относительные) разностные множества.

Ключевые слова: графы Деза, графы Кэли, разностные множества.

MSC: 05B10, 20C05, 05E30

Поступила в редакцию: 10.08.2025
Исправленный вариант: 02.09.2025
Принята в печать: 08.09.2025

Язык публикации: английский

DOI: 10.21538/0134-4889-2025-31-4-281-289

Реферативные базы данных:

•