Коды в дистанционно регулярных графах Шилла
И. Н. Белоусовab a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
b Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
Аннотация:
Если дистанционно регулярный граф
$\Gamma$ диаметра 3 содержит максимальный 1-код
$C$, являющийся локально регулярным и совершенным относительно последней окрестности, то
$\Gamma$ имеет массив пересечений
$\{a(p+1),cp,a+1;1,c,ap\}$ или
$\{a(p+1),(a+1)p,c;1,c,ap\}$, где
$a=a_3,c=c_2,p=p^3_{33}$ (Юришич и Видали). В первом случае
$\Gamma$ имеет собственное значение
$\theta_2=-1$, и граф
$\Gamma_3$ является псевдогеометрическим для
$GQ(p+1,a)$, во втором случае
$\Gamma$ является графом Шилла. В работе изучаются графы Шилла, в которых любые две вершины, находящиеся на расстоянии 3, лежат в максимальном 1-коде. Доказано, что в случае
$\theta_2=-1$ граф с указанным свойством являетcя либо графом Хэмминга
$H(3,3)$, либо графом Джонсона. Кроме того найдены необходимые условия существования
$Q$-полиномиальных графов Шилла, в которых любые две вершины, находящиеся на расстоянии 3, лежат в максимальном 1-коде. В частности, найдены две бесконечные серии допустимых массивов пересечений
$Q$-полиномиальных графов с указанным свойством $\{b(b^2-3b)/2,(b-2)(b-1)^2/2,(b-2)t/2;1,bt/2,(b^2-3b)(b-1)/2\}$ (графы с
$p^3_{33}=0$), $\{b^2(b-4)/2,(b^2-4b+2)(b-1)/2,(b-2)l/2;1,bl/2,(b^2-4b)(b-1)/2\}$ (графы с
$p^3_{33}=1$).
Ключевые слова:
дистанционно регулярный граф, автоморфизм графа.
УДК:
519.17
MSC: 05C25 Поступила в редакцию: 25.12.2017
DOI:
10.21538/0134-4889-2018-24-2-34-39