А.А. Махнев, Д.В. Падучих. Обратные задачи в классе дистанционно регулярных графов диаметра 4 ... С. 199-208

УДК 519.17

MSC: 05E30, 05C50

DOI 10.21538/0134-4889-2022-28-1-199-208

Работа выполнена при финансовой поддержке гранта Российского фонда фундаментальных исследований-ГФЕН Китая (проект № 20-51-53013).

Для дистанционно регулярного графа $\Gamma$ диаметра $4$ граф $\Delta=\Gamma_{1,2}$ может быть сильно регулярным. В этом случае граф $\Gamma_{3,4}$ является сильно регулярным, дополнительным к $\Delta$. Нахождение массива пересечений графа $\Gamma$ по параметрам графа $\Gamma_{3,4}$ является обратной задачей. В данной работе решена обратная задача в случае антиподального графа $\Gamma$ диаметра $4$. Здесь $r=2$ и $\Gamma_{3,4}$ - сильно регулярный граф без треугольников. Далее, $\Gamma$ является $AT4(p,q,r)$-графом только в случае $q=p+2,r=2$. Ранее авторы доказали, что $AT4(p,p+2,2)$-граф не существует. Графом Крейна назовем сильно регулярный граф без треугольников для которого достигается равенство в границе Крейна (равносильно, $q^2_{22}=0$). Граф Крейна $\mathrm{Kre}(r)$ со вторым собственным значением $r$ имеет параметры $((r^2+3r)^2,r^3+3r^2+r,0,r^2+r)$. Для графа $\mathrm{Kre}(r)$ антиокрестность вершины сильно регулярна с параметрами $((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)$ и  пересечение антиокрестностей двух смежных вершин сильно регулярно с параметрами $((r^2+2r)(r^2+2r-1),r^3+r^2-r,0,r^2-r)$. Пусть $\Gamma$ - антиподальный граф диаметра $4$ и $\Delta=\Gamma_{3,4}$ - сильно регулярный граф без треугольников. В работе доказано, что $\Delta$ не может быть графом с параметрами $((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)$, а если $\Delta$ - граф с параметрами $((r^2+2r)(r^2+2r-1),r^3+r^2-r,0,r^2-r)$, то $r>3$. Затем доказано, что дистанционно регулярный граф с массивом пересечений $\{32,27,12(r-1)/r,1;1,12/r,27,32\}$ существует только при $r=3$, а для графа с массивом $\{96,75,32(r-1)/r,1;1,32/r,75,96\}$ имеем $r=2$.

Ключевые слова: дистанционно регулярный граф, антиподальный граф, граф $\Gamma$ с сильно регулярным графом $\Gamma_{i,j}$

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

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

2.   Jurisic A., Koolen J., Terwilliger P. Tight distance-regular graphs // J. Algebr. Comb. 2000. Vol.12. P. 163–197. doi: 10.1023/A:1026544111089 

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

4.   Soicher L. The uniqueness of a distance-regular graph with intersection array {32,27,8,1;1,4,27,32} and related results // Des. Codes Cryptogr. 2017. Vol. 84. P. 101–108. doi: 10.1007/s10623-016-0223-6 

5.   Гаврилюк А. Л., Махнев А. А. О графах Крейна без треугольников // Докл. РАН. 2005. Т. 403, № 6. С. 727–730.

6.   Махнев А. А. Граф Крейна Kre(4) не существует // Докл. РАН. 2017. Т. 475, № 3. С. 251–253. doi: 10.7868/S0869565217210022 

7.   Махнев A. A., Падучих Д. В. О сильно регулярных графах с собственным значением μ и их автоморфизмах // Тр. Ин-та математики и механики УрО РАН. 2013. Т. 19, № 3. С. 207–214.

8.   Vidali J. Using symbolic computation to prove nonexistence of distance-regular graphs // Electronic J. Сombinatorics. 2018. Vol. 25, no. 4. Art. no. 4.21. doi: 10.37236/7763 

9.   Гаврилюк А. Л., Махнев А. А., Падучих Д. В. Дистанционно регулярные графы, в которых окрестности вершин изоморфны графу Гевиртца // Тр. Ин-та математики и механики УрО РАН. 2010. Т. 16, № 2. С. 35–47.

10.   Jurishich A., Koolen J. Classification of the AT4(qs,q,q) family of distance-regular graphs // J. Comb. Theory. 2011. Vol. 118, no. 3. P. 842–852. doi: 10.1016/j.jcta.2010.10.001 

11.   Bamberg J., etc. GAP 4, Package FinInG. 2018. 314 p. URL: https://www.gap-system.org/Manuals/pkg/fining/doc/manual.pdf 

12.   Ефимов К. С. Автоморфизмы AT4(4,4,2)-графа и отвечающих ему сильно регулярных графов // Тр. Ин-та математики и механики УрО РАН. 2017. Т. 23, № 4. С. 119–127.

Поступила 14.10.2021

После доработки 19.01.2022

Принята к публикации 24.01.2022

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

Падучих Дмитрий Викторович
д-р физ.-мат. наук, ведущий науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: dpaduchikh@gmail.com

Ссылка на статью: А.А. Махнев, Д.В. Падучих. Обратные задачи в классе дистанционно регулярных графов диаметра 4 // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 1. С. 199-208

English

A.A. Makhnev, D. V. Paduchikh. Inverse problems in the class of distance-regular graphs of diameter 4

For a distance-regular graph $\Gamma$ of diameter 4, the graph $\Delta=\Gamma_{1,2}$ can be strongly regular. In this case, the graph $\Gamma_{3,4}$ is strongly regular and complementary to $\Delta$. Finding the intersection array of $\Gamma$ from the parameters of $\Gamma_{3,4}$ is an inverse problem. In the present paper, the inverse problem is solved in the case of an antipodal graph $\Gamma$ of diameter $4$. In this case, $r=2$ and $\Gamma_{3,4}$ is a strongly regular graph without triangles. Further, $\Gamma$ is an $AT4(p,q,r)$-graph only in the case $q=p+2$ and $r=2$. Earlier the authors proved that an $AT4(p,p+2,2)$-graph does not exist. A Krein graph is a strongly regular graph without triangles for which the equality in the Krein bound is attained (equivalently, $q^2_{22}=0$). A Krein graph $\mathrm{Kre}(r)$ with the second eigenvalue $r$ has parameters $((r^2+3r)^2,r^3+3r^2+r,0,r^2+r)$. For the graph $\mathrm{Kre}(r)$, the antineighborhood of a vertex is strongly regular with parameters $((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)$ and the intersection of the antineighborhoods of two adjacent vertices is strongly regularly with parameters $((r^2+2r)(r^2+2r-1),r^3+r^2-r,0,r^2-r)$. Let $\Gamma$ be an antipodal graph of diameter 4, and let $\Delta=\Gamma_{3,4}$ be a strongly regular graph without triangles. In this paper it is proved that $\Delta$ cannot be a graph with parameters $((r^2+2r-1)(r^2+3r+1),r^3+2r^2,0,r^2)$, and, if $\Delta$ is a graph with parameters $((r^2+2r)(r^2+2r-1),r^3+r^2-r,0,r^2-r)$, then $r>3$. It is proved that a distance-regular graph with intersection array $\{32,27,12(r-1)/r,1;1, 12/r,27,32\}$ exists only for $r=3$, and, for a graph with array $\{96,75,32(r-1)/r,1;1,32/r,75,96\}$, we have $r=2$.

Keywords: distance-regular graph, antipodal graph, graph $\Gamma$ with strongly regular graph $\Gamma_{i,j}$

Received November 14, 2021

Revised January 19, 2022

Accepted January 24, 2022

Funding Agency: This work was supported by the Russian Foundation for Basic Research — the National Natural Science Foundation of China (project no. 20-51-53013).

Aleksandr Alekseevich Makhnev, Dr. Phys.-Math. Sci., Corresponding member of RAS, Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: makhnev@imm.uran.ru

Dmitrii Viktorovich Paduchikh, Dr. Phys.-Math. Sci., Prof. of RAS, Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: dpaduchikh@gmail.com

Cite this article as: A.A. Makhnev, D.V. Paduchikh. Inverse problems in the class of distance-regular graphs of diameter 4, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 1, pp. 199–208.

[References -> on the "English" button bottom right]