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

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

Пусть а - вершина графа Г. Тогда через 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]

Например:

• 1.    Полные графы являются дистанционно-регулярными графами с диаметром 1 и степенью v-1 (с массивом пересечения {v-1,1});

• 2.    Граф Петерсена является дистанционно-регулярным с массивом пересечений {3,2;1,1}.

Для подсчета количества вершин в дрг используется следующая формула: v=k₀+k₁+k₂+...+k_d, где k₀=1, k₁=k, k_i+1=k_ib_i/c_i+1. Давайте разберемся что из себя представляют эти k i . Если мы выделим любую вершину графа и построим все ее i-окрестности, то k i - число вершин в каждой такой i-ой окрестности.

Спектр графа - множество всех собственных значений матрицы смежности графа с учетом их кратности.

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

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

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

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

Теорема. Сильно регулярные графы [а] имеют параметры: (1276,5G,G,2), (1G73,64,G,4), (1G8G,78,G,6), (1178,99,0,9), (1458,141,0,15), (2256,246,G,3G), (2585,288,G,36), (2916,33G,G,42), (24G57,2976,G,42G).

Доказательство. Для нахождения параметров графа используем пункт (i) теоремы 1.3.1 из [1]. Получаем формулу k=36+7p, для p=1,2,3,... . Используя прямоугольное соотношение для сильно регулярных графов [1], получим ограничение на р<1260 и вычислим v. Выпишем случаи, когда все параметры являются целыми неотрицательными числами: (185G,43,G,1), (1276,5G,G,2), (1122,57,G,3), (1G73,64,G,4), (1G66,71,G,5),

(1080,78,0,6), (1106,85,0,7), (1178,99,0,9), (1220,106,0,10), (1311,120,0,12), (1408,134,0,14), (1458,141,0,15), (1612,162,0,18), (1717,176,0,20), (1770,183,0,21), (2147,232,0,28), (2256,246,0,30), (2530,281,0,35), (2585,288,0,36), (2916,330,0,42), (3082,351,0,45), (3915,456,0,60), (4082,477,0,63), (4472,526,0,70), (5253,624,0,84), (5588,666,0,90), (6426,771,0,105), (7544,911,0,125), (7600,918,0,126), (8383,1016,0,140), (10621,1296,0,180), (12300,1506,0,210), (14651,1800,0,252), (18178,2241,0,315), (24057,2976,0,420), (35816,4446,0,630), (71095,8856,0,1260).

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

Так как кратности собственных значений сильно регулярных графов являются целыми положительными числами, мы можем сделать вывод, что сильно регулярные графы без треугольников со вторым собственным значением 6 имеют параметры: (1276,50,0,2), (1073,64,0,4), (1080,78,0,6), (1178,99,0,9), (1458,141,0,15), (2256,246,0,30), (2585,288,0,36), (2916,330,0,42), (24057,2976,0,420).

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