УДК 519.17
MSC: 05C25
DOI: 10.21538/0134-4889-2019-25-4-136-141
Полный текст статьи (Full text)
Работа выполнена при поддержке соглашения между Министерством образования и науки Российской Федерации и Уральским федеральным университетом от 27.08.2013, № 02.A03.21.0006.
И.Н. Белоусов, А.А. Махнев и М.С. Нирова нашли описание $Q$-полиномиальных дистанционно регулярных графов $\Gamma$ диаметра $3$, для которых графы $\Gamma_2$ и $\Gamma_3$ сильно регулярны. Пусть $a=a_3$. $\Gamma$ - граф типа (I), если $c_2+1$ делит $a$; $\Gamma$ - граф типа (II), если $c_2+1$ делит $a+1$; $\Gamma$ - граф типа (III), если $c_2+1$ не делит $a$ и не делит $a+1$. Если $\Gamma$ - граф типа (II), то $a+1=w(c_2+1)$, $t^2=w(w(c_2+1)+c_2)$ и либо
(i) $w=s^2$, $t^2=s^2(s^2(c_2+1)+c_2)$, $(s^2(c_2+1)+c_2$ является квадратом некоторого целого числа $u$, $c_2=(u^2-s^2)/(s^2+1)$, $t=su$, $a=(u^2s^2-1)/(s^2+1)$, либо
(ii) $c_2=sw$, $t^2=w^2(sw+1+s)$, $sw+1+s$ является квадратом некоторого целого числа $u$, $c_2=(u^2-1)w/(w+1)$, $t=uw$, $a=(u^2w^2-1)/(w+1)$ и $\Gamma$ имеет массив пересечений $$\left\{ \frac{u^3w^2+u^2w^2+uw-1}{w+1},\frac{(u^2-1)uw^2}{w+1},\frac{(u^2w+1)w}{w+1};1, \frac{(u^2-1)w}{w+1},\frac{(u^2w+1)uw}{w+1}\right\}.$$ В случае графа типа (IIii) для $w=u$ мы получаем массив пересечений $\{w^4+w-1,w^4-w^3,(w^2-w+1)w;1,w(w-1),(w^2-w+1)w^2\}$. В статье доказано, что графы с такими массивами пересечений не существуют для четных $w$.
Ключевые слова: дистанционно регулярный граф, $Q$-полиномиальный граф
СПИСОК ЛИТЕРАТУРЫ
1. Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Berlin; Heidelberg; N Y: Springer-Verlag, 1989. 495 p.
2. Белоусов И.Н., Махнев А.А., Нирова М.С. О дистанционно регулярных Q-полиномиальных графах Γ с сильно регулярными графами $Γ_2$ и $Γ_3$ // Сиб. электрон. мат. изв. 2019. Т. 16. C. 1358–1365.
3. Coolsaet K., Jurishich A. Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs // J. Comb. Theory. Ser. A. 2008. Vol. 115, no. 6. P. 1086–1095. doi: 10.1016/j.jcta.2007.12.001
Поступила 10.09.2019
После доработки 7.11.2019
Принята к публикации 11.11.2019
Махнев Александр Алексеевич
д-р физ.-мат. наук, чл.-корр. РАН, главный науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет, г. Екатеринбург
e-mail: makhnev@imm.uran.ru
Голубятников Михаил Петрович
математик 1 кат.
Институт математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет, г. Екатеринбург
e-mail: mike_ru1@mail.ru
Ссылка на статью: А.А. Махнев, М.П. Голубятников. Несуществование некоторых Q-полиномиальных дистанционно регулярных графов // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 4. С. 136-141.
English
A.A. Makhnev, M.P. Golubyatnikov. Nonexistence of certain Q-polynomial distance-regular graphs
I.N. Belousov, A.A. Makhnev, and M.S. Nirova described $Q$-polynomial distance-regular graphs $\Gamma$ of diameter 3 for which the graphs $\Gamma_2$ and $\Gamma_3$ are strongly regular. Set $a=a_3$. A graph $\Gamma$ has type (I) if $c_2+1$ divides~$a$, type (II) if $c_2+1$ divides $a+1$, and type (III) if $c_2+1$ divides neither $a$ nor $a+1$. If $\Gamma$ is a graph of type (II), then $a+1=w(c_2+1)$, $t^2=w(w(c_2+1)+c_2)$, and either
(i) $w=s^2$, $t^2=s^2(s^2(c_2+1)+c_2)$, $(s^2(c_2+1)+c_2$ is the square of an integer $u$, $c_2=(u^2-s^2)/(s^2+1)$, $t=su$, and $a=(u^2s^2-1)/(s^2+1)$ or
(ii) $c_2=sw$, $t^2=w^2(sw+1+s)$, $sw+1+s$ is the square of an integer $u$, $c_2=(u^2-1)w/(w+1)$, $t=uw$, $a=(u^2w^2-1)/(w+1)$, and $\Gamma$ has intersection array
$$\left\{ \frac{u^3w^2+u^2w^2+uw-1}{w+1},\frac{(u^2-1)uw^2}{w+1},\frac{(u^2w+1)w}{w+1};1,\frac{(u^2-1)w}{w+1},\frac{(u^2w+1)uw}{w+1}\right\}.$$ If a graph of type (IIii) is such that $w=u$, then it has intersection array $\{w^4+w-1,w^4-w^3,(w^2-w+1)w;$ $1,w(w-1),(w^2-w+1)w^2\}$. We prove that graphs with such intersection arrays do not exist for even $w$.
Keywords: distance-regular graph, $Q$-polynomial graph
Received September 10, 2019
Revised November 7, 2019
Accepted November 11, 2019
Funding Agency: This work was supported by the Russian Academic Excellence Project (agreement no. 02.A03.21.0006 of August 27, 2013, between the Ministry of Education and Science of the Russian Federation and Ural Federal University).
Aleksandr Alekseevich Makhnev, Dr. Phys.-Math. Sci., Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: makhnev@imm.uran.ru
Mikhail Petrovich Golubyatnikov, graduate student, Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: mike_ru1@mail.ru
Cite this article as: A.A.Makhnev, M.P.Golubyatnikov. Nonexistence of certain Q-polynomial distance-regular graphs, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 4, pp. 136–141.
