|
О небольших дистанционно регулярных графах с массивами пересечений $\{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$.
Статья поступила: 18.11.2020
Образец цитирования:
А. А. Махнев, М. П. Голубятников, “О небольших дистанционно регулярных графах с массивами пересечений $\{mn-1,(m-1)(n+1),n-m+1;1,1,(m-1)(n+1)\}$”, Дискрет. матем., 34:1 (2022), 76–87; Discrete Math. Appl., 33:5 (2023), 273–281
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1698https://doi.org/10.4213/dm1698 https://www.mathnet.ru/rus/dm/v34/i1/p76
|
Статистика просмотров: |
Страница аннотации: | 298 | PDF полного текста: | 76 | Список литературы: | 56 | Первая страница: | 8 |
|