Некоторые сильно регулярные графы со вторым собственным значением 6

B.S. Fedorenko master's student, 2 course faculty of mathematics and information technology

North Ossetian State University,

Vladikavkaz, Russia

V.V. Bitkina assistant of Department of applied mathematics faculty of mathematics and information technology

North Ossetian State University,

Vladikavkaz, Russia

SOME STRONGLY REGULAR GRAPHS WITH SECOND EIGENVALUE 6

Annotation:

J. Koolen proposed the problem of studying distance-regular graphs in which the neighborhoods of vertices are strongly regular graphs with second eigenvalue ≤ t for a given positive integer t. Earlier Koolen’s problem was solved for t ≤ 5. In this paper we consider some strongly regular graphs with second eigenvalue 6. They are neighborhoods of vertices of distance-regular graphs satisfying the Koolen’s problem for t=6.

Нами рассматриваются простые неориентированные графы.

Пусть а - вершина графа Г. Тогда через r i (a) обозначим i-окрестность вершины a. Через [a] обозначим Г₁(а). Пусть u, w - вершины графа Г, такие что, расстояние между ними d(u,w)=i. Тогда через b i (u, w) (через c_i(u, w)) обозначим количество вершин в множестве r_i+1(u)H[w] (F i _-1(u)n[w]). Если все значения b i (u, w) (соответственно значения c i (u, w)), где i = 0,...,d, равны между собой для любых вершин u, w, таких что d(u,w)=i, то граф Г диаметра d называется дистанционно регулярным с массивом пересечений {b₀, b₁,...,b_d-1; c₁,...,c_d}. [1]

Связные дистанционно регулярные графы диаметра 2 называются сильно регулярными графами. Сильно регулярные графы характеризуются параметрами (v,k,X,p), где v - количество вершин графа, k - степень графа, X - число общих соседей любых двух смежных вершин, р - число общих соседей любых двух несмежных вершин. [1]

Теория дистанционно регулярных графов достаточно молода. Ее основной задачей является классификация дистанционно регулярных графов. Как известно, при классификации дистанционно регулярных графов речь может идти только об описании конкретных классов дистанционно регулярных графов. Джеком Куленом была предложена задача изучения дистанционно регулярных графов, в которых окрестности вершин ˗ сильно регулярные графы со вторым собственным значением, не большим t для данного натурального числа t. Задача Кулена для t = 1 была решена А.А. Махневым и его учениками в 2010 году и независимо Дж. Куленом. Задача Кулена для t=2 была решена А.А. Махневым и его учениками в 2012 году. В 2015 и 2016 годах А.А. Махневым и Д.В. Падучих были найдены массивы пересечений дистанционно регулярных графов при 2

В статье мы находим параметры сильно регулярных графов с k=2p со вторым собственным значением 6, число вершин которых v<1000. Полученные графы являются окрестностями вершин дистанционно регулярных графов, удовлетворяющих задаче Кулена при t=6.

Пусть Г - дистанционно регулярный граф диаметра 3, а - некоторая вершина графа Г, [а]-сильно регулярный граф с параметрами (v,2p,X,p) со вторым собственным значением 6 и v<10000.

Теорема. Сильно регулярные графы [а] имеют параметры: (143,72,36,36), (169,84,41,42), (195,96,46,48), (377,180,81,90), (507,240,106,120), (559,264,116,132), (845,396,171,198), (923,432,186,216).

Доказательство. Для нахождения параметров графа используем пункт (i) теоремы 1.3.1 из [1]. Получаем формулы к=2ц и Х=6+5/6ц для р=1,2,3,... . Используя прямоугольное соотношение для сильно регулярных графов [1], вычислим число вершин v графа. Выпишем случаи, когда все параметры являются целыми неотрицательными числами: (13,12,11,6), (39,24,16,12), (65,36,21,18), (91,48,26,24), (117,60,31,30), (143,72,36,36), (169,84,41,42), (195,96,46,48), (221,108,51,54), (247,120,56,60), (273,132,61,66), (299,144,66,72), (325,156,71,78), (351,168,76,84), (377,180,81,90), (403,192,86,96), (429,204,91,102), (455,216,96,108), (481,228,101,114), (507,240,106,120), (533,252,111,126), (559,264,116,132), (585,276,121,138), (611,288,126,144), (637,300,131,150), (663,312,136,156), (689,324,141,162), (715,336,146,168), (741,348,151,174), (767,360,156,180), (793,372,161,186), (819,384,166,192), (845,396,171,198), (871,408,176,204), (897,420,181,210), (923,432,186,216), (949,444,191,222), (975,456,196,228).

Найдем собственные значения и их кратности полученных графов, используя пункты (i), (vi) теоремы 1.3.1. из [1]. Представим данные в виде таблицы:

Так как кратности собственных значений являются целыми положительными числами, мы можем сделать вывод, что сильно регулярные графы при k=2μ и v≤1000 со вторым собственным значением 6 имеют параметры:   (143,72,36,36),   (169,84,41,42),   (195,96,46,48),

(377,180,81,90),  (507,240,106,120),  (559,264,116,132),  (845,396,171,198),

(923,432,186,216).

Теорема доказана.