В.В. Биткина, А.К. Гутнова. Дистанционно регулярные локально $pG_{s-6}(s,t)$-графы диаметра, большего 3 ... C. 34-42

УДК 519.17+512.54

MSC: 05C25, 20B25

DOI: 10.21538/0134-4889-2018-24-3-34-42

Дж. Кулен предложил задачу изучения дистанционно регулярных графов, в которых окрестности вершин — сильно регулярные графы со вторым собственным значением, не большим $t$ для данного натурального числа $t$. Решение задачи Кулена состоит из двух этапов: первый этап — перечисление допустимых массивов пересечений дистанционно регулярных графов; второй этап — нахождение автоморфизмов графов с полученными массивами. В настоящее время первый этап решения задачи Кулена закончен для $t = 5$ (А. А. Махнев, Д. В. Падучих и А. К. Гутнова, А. А. Махнев). Завершен второй этап решения задачи Кулена для $t = 3$ (А. А. Махнев, М. Х. Шерметова). Программа изучения дистанционно регулярных графов, в которых окрестности вершин — сильно регулярные графы со вторым собственным значением $r, 5 < r ≤ 6$, состоит из трех частей. Это получение списка параметров исключительных локальных подграфов с помощью теоремы редукции, перечисление массивов пересечений дистанционно регулярных локально исключительных псевдогеометрических графов, перечисление массивов пересечений дистанционно регулярных локально исключительных непсевдогеометрических графов. В данной работе перечислены массивы пересечений дистанционно регулярных локально псевдогеометрических графов для $pG_{s-6}(s,t)$ диаметра, большего $3$.

Ключевые слова: дистанционно регулярный граф, локальный подграф, собственное значение графа.

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

1.   Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Berlin etc: Springer-Verlag, 1989. 495 p. ISBN: 3-540-50619-5 .

2.   Гутнова А.К., Махнев А.А. Расширения псевдогеометрических графов для $pG_{s-5}(s,t)$ // Владикавказ. мат. журн. 2016. Т. 18, № 3. С. 35–42.

3.   Махнев А.А., Шерметова М.Х. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {96,76,1;1,19,96} // Сиб. электрон. мат. изв. 2018. Т. 15. С. 167–174. doi: 10.17377/semi.2018.15.016 .

4.   Brouwer A.E., Haemers W.H. Spectra of graphs Berlin etc: Springer, 2012. 250 p. doi: 10.1007/978-1-4614-1939-6 .

5.   Koolen J.H., Park J. Distance-regular graphs with $a_1$ or $c_2$ at least half the valency // J. Comb. Theory. Ser. A. 2012. Vol. 119. P. 546–555. doi: 10.1016/j.jcta.2011.11.001 .

6.   Makhnev A.A., Paduchikh D.V. Small AT4-graphs and strongly regular subgraphs corresponding to them // Proc. Steklov Institute Math. 2017. Vol. 296, Suppl. 1. P. S164–S174. doi: 10.1134/S0081543817020158 .

Поступила 20.06.2018

Биткина Виктория Васильевна
канд. физ.-мат. наук, старший преподаватель
Северо-Осетинский государственный университет,
г. Владикавказ
e-mail: bviktiriyav@mail.ru

Гутнова Алина Казбековна
канд. физ.-мат. наук, доцент
Северо-Осетинский государственный университет,
г. Владикавказ
e-mail: gutnovaalina@mail.ru

English

V.V. Bitkina, A.K. Gutnova. Distance-regular locally $pG_{s-6}(s,t)$-graphs of diameter greater than 3.

J. Koolen suggested the problem of studying distance-regular graphs in which neighborhoods of vertices are strongly regular graphs with the second eigenvalue at most t for some natural $t$. The solution of Koolen’s problem consists of two steps: the first step is the enumeration of admissible intersection arrays of such graphs, and the second step is finding the automorphisms of the graphs with these arrays. At present, the first step is complete for $t = 5$ (A. Makhnev, D. Paduchikh, and A. Gutnova; A. Makhnev). The second step is complete for $t = 3$ (A. Makhnev and M. Shermetova). The program of studying distance-regular graphs in which neighborhoods of vertices are strongly regular graphs with the second eigenvalue $r$ such that $5 < r ≤ 6$ consists of three parts: the theorem of reduction to exceptional local subgraphs, the enumeration of intersection arrays of distance-regular locally exceptional pseudogeometric graphs, and the enumeration of intersection arrays of distance-regular locally exceptional nonpseudogeometric graphs. In this paper we enumerate intersection arrays of distance-regular locally pseudogeometric graphs for $pG_{s-6}(s,t)$ with diameter greater than $3$.

Keywords: distance-regular graph, local subgraph, eigenvalue of a graph

The paper was received by the Editorial Office on June 20, 2018.

Viktoriya Vasil’evna Bitkina, Cand. Sci. (Phys.-Math.), North Ossetian State University, Vladikavkaz, North Ossetia-Alania, 362025 Russia, e-mail: bviktiriyav@mail.ru.

Gutnova Alina Kazbekovna, Cand. Sci. (Phys.-Math.), North Ossetian State University, Vladikavkaz, North Ossetia-Alania, 362025 Russia, e-mail: gutnovaalina@mail.ru.

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