УДК 519.17
MSC: 05C25
DOI: 10.21538/0134-4889-2018-24-3-155-163
Полный текст статьи
Если дистанционно регулярный граф $\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$ является графом Шилла. В работе изучаются графы с массивом пересечений $\{a(p+1),cp,a+1;1,c,ap\}$, в которых любые две вершины, находящиеся на расстоянии 3, лежат в максимальном 1-коде. В частности, найдены новые бесконечные серии допустимых массивов пересечений: $\{a(a-2),(a-1)(a-3),a+1;1,a-1,a(a-3)\}$, $a\ge 5$, $\{a(2a+3),2(a-1)(a+1),a+1;1,a-1,2a(a+1)\}$, $a$ не сравнимо с $1$ по модулю $3$, $\{a(2a-3),2(a-1)(a-2),a+1;1,a-1,2a(a-2)\}$, $a$ четно и не сравнимо с $1$ по модулю $3$, $\{a(3a-4),(a-1)(3a-5),a+1;1,a-1,a(3a-5)\}$, $a$ четно и сравнимо с $0$ или $2$ по модулю $5$.
Ключевые слова: дистанционно регулярный граф, максимальный код
СПИСОК ЛИТЕРАТУРЫ
1. Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Berlin; Heidelberg; N Y: Springer-Verlag, 1989. 495 p. ISBN: 0387506195 .
2. 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 .
3. Махнев A.A., Нирова M.С. Дистанционно регулярные графы Шилла с $b_2 = c_2$ // Мат. заметки 2018. Т. 103, вып. 5. С. 730–744. doi: 10.4213/mzm11503 .
4. 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 .
5. Koolen J.H., Park J., Yu H. An enequality involving the second largesr and smallest eigenvalues of a distance-regular graphs // Linear Algebra and Appl. 2011. Vol. 434, no. 12. P. 2404–2413. doi: 10.1016/j.laa.2010.12.032 .
6. Maхнев A.A. Графы, в которых граница Хофмана для коклик совпадает с границей Цветковича // Докл. АН. 2011. Т. 438, № 3. С. 303–307.
7. Махнев А.А. (мл.), Махнев А.А. Овоиды и двудольные подграфы в обобщенных четырехугольниках // Мат. заметки. 2003. Т. 73, № 6. С. 878–885.
Поступила 26.06.2018
Нирова Марина Сефовна
канд. физ.-мат. наук, доцент
Кабардино-балкарский государственный университет имени Х.М. Бербекова,
г. Нальчик
e-mail: m_nirova@mail.ru
English
M.S. Nirova. Codes in distance-regular graphs with $\theta_2 = -1$
If a distance-regular graph $\Gamma$ of diameter 3 contains a maximal 1-code $C$ that is both locally regular and last subconstituent perfect, 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}}$ and Vidali). In 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 graphs with intersection array $\{a(p+1),cp,a+1;1,c,ap\}$ in which any two vertices at distance 3 are in a maximal 1-code. In particular, we find four new infinite families of intersection arrays: $\{a(a-2),(a-1)(a-3),a+1;1,a-1,a(a-3)\}$ for $a\ge 5$, $\{a(2a+3),2(a-1)(a+1),a+1;1,a-1,2a(a+1)\}$ for $a$ not congruent to $1$ modulo $3$, $\{a(2a-3),2(a-1)(a-2),a+1;1,a-1,2a(a-2)\}$ for even $a$ not congruent to $1$ modulo $3$, and $\{a(3a-4),(a-1)(3a-5),a+1;1,a-1,a(3a-5)\}$ for even $a$ congruent to 0 or 2 modulo 5.
Keywords: distance-regular graph, maximal code
The paper was received by the Editorial Office on June, 26, 2018.
Marina Sefovna Nirova, Cand. Sci. (Phys.-Math.), Kabardino-Balkarian State University named after H.M. Berbekov, Nal’chik, 360004 Russia, e-mail: nirova_m@mail.ru.
[References -> on the "English" button bottom right]
