О небольших дистанционно регулярных графах с массивами пересечений $\{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