А.А. Махнев, М.П. Голубятников. Несуществование некоторых Q-полиномиальных дистанционно регулярных графов ... С. 136-141

УДК 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.