RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2022, том 34, выпуск 1, страницы 76–87 (Mi dm1698)

О небольших дистанционно регулярных графах с массивами пересечений $\{mn-1,(m-1)(n+1),n-m+1;1,1,(m-1)(n+1)\}$

А. А. Махнев, М. П. Голубятников

Институт математики и механики им. Н. Н. Красовского УрО РАН, Уральский федеральный университет

Аннотация: Пусть $\Gamma$ — дистанционно регулярный граф диаметра 3 с сильно регулярным графом $\Gamma_3$, где $\Gamma_3$ — граф, у которого множество вершин совпадает с множеством вершин графа $\Gamma$ и две вершины смежны тогда и только тогда, когда они находятся на расстоянии $3$ в графе $\Gamma$. Нахождение параметров $\Gamma_3$ по массиву пересечений графа $\Gamma$ является прямой задачей. Нахождение массива пересечений графа $\Gamma$ по параметрам $\Gamma_3$ является обратной задачей. Ранее обратные задачи были решены для $\Gamma_3$ Махневым А.А. и Нировой М.С. В случае, когда $\Gamma_3$ является псевдогеометрическим графом сети, найдена серия допустимых массивов пересечений $\{{c_2(u^2-m^2)+2c_2m-c_2-1},{c_2(u^2-m^2)},{(c_2-1)(u^2-m^2)+2c_2m-c_2};1,c_2,{u^2-m^2}\}$ (Махнев А.А., Го Вэнь-бинь, Голубятников М.П.) Случаи $c_2=1$ и $c_2=2$ изучены Махневым А.А., Голубятниковым М.П. и Махневым А.А., Нировой М.С. соответственно. В работе в классе графов с массивами пересечений $\{{mn-1},{(m-1)(n+1)},{n-m+1};1,1,{(m-1)(n+1)}\}$ найдены все допустимые массивы пересечений для $3\le m\le 13$: $\{20,16,5;1,1,16\}$, $\{39,36,4;1,1,36\}$, $\{55,54,2;1,2,54\}$, $\{90,84,7;1,1,84\}$, $\{220,216,5;1,1,216\}$, $\{272,264,9;1,1,264\}$ и $\{350,336,15;$ $1,1,336\}$. Доказано, что графы с массивами пересечений $\{20,16,5;1,1,16\}$,$\{39,36,4;1,1,36\}$ и $\{90,84,7;1,1,84\}$ не существуют.

Ключевые слова: дистанционно регулярный граф, граф $\Gamma$ с сильно регулярным графом $\Gamma_3$.

УДК: 519.172

Статья поступила: 18.11.2020

DOI: 10.4213/dm1698


 Англоязычная версия: Discrete Mathematics and Applications, 2023, 33:5, 273–281


© МИАН, 2024