И.Н. Белоусов. Коды в дистанционно регулярных графах Шилла ... С. 34-39

УДК 519.17

MSC: 05C25

DOI: 10.21538/0134-4889-2018-24-2-34-39

Работа выполнена при финансовой поддержке гранта РНФ, проект 14-11-00061-П.

Если дистанционно регулярный граф $\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$).

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

СПИСОК ЛИТЕРАТУРЫ

1.   Brouwer A. E., Cohen A. M., Neumaier A. Distance-regular graphs. Berlin; Heidelberg; N Y: Springer-Verlag, 1989. 495 p. ISBN: 0387506195 .

2.   Koolen J.H., Park J. Shilla distance-regular graphs // Europ. J. Comb. 2010. Vol. 31, no. 8. P. 2064–2073. doi: 10.1016/j.ejc.2010.05.012 .

3.   Vidali J. Kode v razdaljno regularnih grafih: Doctorska dissertacija / Univerza v Ljubljani. Ljubljana, 2013. 155 str.

4.   Jurisic A., Vidali J. Extremal 1-codes in distance-regular graphs of diameter 3 // Des. Codes Cryptogr. 2012. Vol. 65, no. 1-2. P. 29–47. doi: 10.1007/s10623-012-9651-0 .

5.   Махнев А. А., Нирова М. С. Дистанционно регулярные графы Шилла с $b_2 = c_2$ // Мат. заметки. 2018. Т. 103, № 5. C. 730–744. doi: 10.4213/mzm11503 .

6.   Белоусов И. Н., Махнев А. А. К теории графов Шилла с $b_2 = c_2$ // Сиб. электрон. мат. известия. 2017. Т. 14. С. 1135–1146. doi: 10.17377/semi.2017.14.097 .

7.   Koolen J.H., Park J., Yu H. An inequality involving the second largest and smallest eigenvalue of a distance-regular graph // Linear Algebra Appl. 2011. Vol. 434, no. 12. P. 2404–2412. doi: 10.1016/j.laa.2010.12.032 .

Поступила 25.12.2017

Белоусов Иван Николаевич
канд. физ.-мат. наук, старший науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
Уральский федеральный университет,
г. Екатеринбург
e-mail: i_belousov@mail.ru

English

I.N. Belousov. Codes in Shilla distance-regular graphs.

Let $\Gamma$ be a distance-regular graph of diameter $3$ containing a maximal 1-code $C$, which is locally regular and perfect with respect to the last neighborhood. Then $\Gamma$ has intersection array $\{a(p+1),cp,a+1;1,c,ap\}$ or $\{a(p+1),(a+1)p,c;1,c,ap\}$, where $a=a_3$, $c=c_2$, and $p=p^3_{33}$ (Juri$\check{\mathrm{s}}$i$\acute{\mathrm{c}}$, Vidali). In the first case, $\Gamma$ has eigenvalue $\theta_2=-1$ and the graph $\Gamma_3$ is pseudogeometric for $GQ(p+1,a)$. In the second case, $\Gamma$ is a Shilla graph. We study Shilla graphs in which every two vertices at distance 2 belong to a maximal $1$-code. It is proved that, in the case $\theta_2=-1$, a graph with the specified property is either the Hamming graph $H(3,3)$ or a Johnson graph. We find necessary conditions for the existence of $Q$-polynomial Shilla graphs in which any two vertices at distance 3 lie in a maximal 1-code. In particular, we find two infinite families of feasible intersection arrays of $Q$-polynomial graphs with the specified property: $\{b(b^2-3b)/2,(b-2)(b-1)^2/2,(b-2)t/2;1,bt/2,(b^2-3b)(b-1)/2\}$ (graphs with $p^3_{33}=0$) and $\{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\}$ (graphs with $p^3_{33}=1$).

Keywords: distance-regular graph, graph automorphism.

The paper was received by the Editorial Office on Dezember 25, 2017.

Ivan NIkolaevich Belousov, Cand. Sci. (Phis.-Math.), Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia: Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: i_belousov@mail.ru.