УДК 519.17
MSC: 05C25
DOI: 10.21538/0134-4889-2018-24-3-133-144
Полный текст статьи
Работа выполнена при поддержке гранта РНФ, проект 14-11-00061-П
Для дистанционно регулярного графа $\Gamma$ диаметра 3 граф $\Gamma_i$ может быть сильно регулярным для $i=2$ или $i=3$. Нахождение параметров $\Gamma_i$ по массиву пересечений графа $\Gamma$ является прямой задачей. Нахождение массива пересечений графа $\Gamma$ по параметрам $\Gamma_i$ является обратной задачей. Ранее прямая и обратная задачи были решены А.А. Махневым и М.С. Нировой для $i=3$. В данной работе решена обратная задача для $i=2$: по параметрам сильно регулярного графа $\Gamma_2$ найден массив пересечений дистанционно регулярного графа $\Gamma$ диаметра 3. Доказано, что граф $\Gamma_2$ не является графом в половинном случае. Уточняются также результаты М.С. Нировой о дистанционно регулярных графах $\Gamma$ диаметра 3, для которых $\Gamma_2$ и $\Gamma_3$ сильно регулярны. Найдены новые бесконечные серии допустимых массивов пересечений: $\{r^2+3r+1,r(r+1),r+2;1,r+1,r(r+2)\}$, $r$ нечетно и делится на 3, $\{2r^2+5r+2,r(2r+2),2r+3;1,2r+2,r(2r+3)\}$, $r$ не делится на $3$ и $r$ не сравнимо с $\pm 1$ по модулю $5$.
Ключевые слова: сильно регулярный граф, дистанционно регулярный граф, массив пересечений.
СПИСОК ЛИТЕРАТУРЫ
1. Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Berlin: Springer-Verlag, 1989. 495 p. ISBN: 0387506195 .
2. Makhnev A., Nirova M. On distance-regular Shilla graphs with $b_2 = c_2$ // Mat. Zametki. 2018. Vol. 103, no. 5. P. 730–744. doi: 10.4213/mzm11503 .
3. Coolsaet K., Jurisic A. Using equality in the Krein conditions to prove the nonexistence of certain distance-regular graphs // J. Comb. Theory Ser. A. 2008. Vol. 115. P. 1086–1095. doi: 10.1007/s10623-012-9651-0 .
4. Shi M., Krotov D., Sole P. A new distance-regular graph of diameter 3 on 1024 vertices [e-resource]. 2018. 12 p. URL: https://arxiv.org/pdf/1806.07069.pdf .
5. Gavrilyuk A., Makhnev A. Distance-regular graph with intersection array {45,30,7;1,2,27} does not exist // Discrete Math. Appl. 2013. Vol. 23. P. 225–244.
6. Gavrilyuk A., Makhnev A. Distance-regular graphs with intersection arrays {52,35,16;1,4,28} and {69,48,24;1,4,46} do not exist // Des. Codes Cryptogr. 2012. Vol. 65. P. 49–54.
7. Urlep M. Triple intersection numbers in Q-polinomial distance-regular graphs // Europ. J. Comb. 2012. Vol. 33. P. 1246–1252.
8. 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 .
9. Nirova M. On distance-regular graphs $\Gamma$ with strongly regular $\Gamma_2$ and $\Gamma_3$ // Sibirean Electr. Math. Reports. 2018. Vol. 15. P. 175–185. doi: 10.17377/semi.2018.15.017 .
10. 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 .
11. Koolen J.H., Park J. A relationship between the diameter and the intersection number $c_2$ for a distance-regular graphs // Des. Codes Cryptogr. 2012. Vol. 65, no. 1-2. P. 55–63. doi: 10.1007/s10623-011-9600-3 .
12. Degraer J. Isomorphism-free exhaustive generation algorithms for association schemes: PHD. Gent: Univ. Gent., 2007. 240 p.
Поступила 11.05.2018
Махнев Александр Алексеевич
д-р физ.-мат. наук, чл.-корр. РАН,
зав. отделом
Институт математики и механики им. Н.Н.Красовского УрО РАН
Уральский федеральный университет,
г. Екатеринбург
e-mail: makhnev@imm.uran.ru
Падучих Дмитрий Викторович
д-р физ.-мат. наук, главный. науч. сотрудник
профессор РАН,
Институт математики и механики им. Н.Н.Красовского УрО РАН,
г. Екатеринбург
e-mail: dpaduchikh@gmail.com
English
A.A. Makhnev, D.V. Paduchikh. Inverse problems in the theory of distance-regular graphs.
For a distance-regular graph $\Gamma$ of diameter 3, the graph $\Gamma_i$ can be strongly regular for $i=2$ or $3$. Finding the parameters of $\Gamma_i$ given the intersection array of $\Gamma$ is a direct problem, and finding the intersection array of $\Gamma$ given the parameters of $\Gamma_i$ is the inverse problem. The direct and inverse problems were solved earlier by A.A. Makhnev and M.S. Nirova for $i=3$. In the present paper, we solve the inverse problem for $i=2$: given the parameters of a strongly regular graph $\Gamma_2$, we find the intersection array of a distance-regular graph $\Gamma$ of diameter 3. It is proved that $\Gamma_2$ is not a graph in the half case. We also refine Nirova's results on distance-regular graphs $\Gamma$ of diameter 3 for which $\Gamma_2$ and $\Gamma_3$ are strongly regular. New infinite series of admissible intersection arrays are found: $\{r^2+3r+1,r(r+1),r+2;1,r+1,r(r+2)\}$ for odd $r$ divisible by 3 and
$\{2r^2+5r+2,r(2r+2),2r+3;1,2r+2,r(2r+3)\}$ for $r$ indivisible by $3$ and not congruent to $\pm 1$ modulo $5$.
Keywords: strongly regular graph, distance-regular graph, intersection array.
The paper was received by the Editorial Office on May 11, 2018.
Funding Agency: This work was supported by the Russian Science Foundation (project no. 14-11-00061-П).
Aleksandr Alekseevich Makhnev, Dr. Phys.-Math. Sci., Prof., 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: makhnev@imm.uran.ru.
Dmitrii Viktorovich Paduchikh, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia,
e-mail: dpaduchikh@gmail.com.
[References -> on the "English" button bottom right]
