ДОКЛАДЫ АКАДЕМИИ НАУК, 2015, том 464, № 4, с. 396-400
= МАТЕМАТИКА
УДК 519.17
ДИСТАНЦИОННО-РЕГУЛЯРНЫЕ ГРАФЫ, В КОТОРЫХ ОКРЕСТНОСТИ ВЕРШИН СИЛЬНО РЕГУЛЯРНЫ СО ВТОРЫМ СОБСТВЕННЫМ ЗНАЧЕНИЕМ, НЕ БОЛЬШИМ 3
© 2015 г. Член-корреспондент РАН А. А. Махнев, Д. В. Падучих
Поступило 10.06.2014 г.
Ранее изучение графов с заглавным свойством было редуцировано к случаю окрестностей с параметрами (35, 18, 9, 9), (36, 21, 12, 12), (40, 27, 18, 18), (50, 28, 15, 16), (56, 45, 36, 36), (64, 27, 10, 12). В работе доказано, что вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы с соответствующими параметрами, либо сильно регулярен с параметрами (76, 35, 18, 14) или (64, 35, 18, 20), либо является графом Тейлора с массивом пересечений {38, 16, 1; 1, 16, 35} (теорема). Как следствие, получена классификация дистанционно-регулярных графов, в которых окрестности вершин — сильно регулярные графы с неглавным собственным значением г, 2 < г < 3.
Б01: 10.7868/80869565215280051
Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины а графа Г через Г(-(а) обозначим г -окрестность вершины а, т.е. подграф, индуцированный Г на множестве всех вершин, находящихся на расстоянии г от а. Подграф Г(а) = Г1(а) называется окрестностью вершины а и обозначается [а], если граф Г фиксирован. Положим а1 = {а} и [а].
Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а из Г равна к. Граф Г назовем реберно-регулярным с параметрами (V, к,Х), если он содержит V вершин, регулярен степени к и каждое его ребро лежит в X треугольниках. Граф Г — вполне регулярный граф с параметрами (V, к,Х, ц), если он реберно-регуля-рен с соответствующими параметрами и [а] п [Ь] содержит точно ц вершин для любых двух вершин а,Ь, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
Дж. Кулен предложил задачу изучения дистанционно-регулярных графов, в которых окрестно-
Институт математики и механики им. Н.Н. Красовского
Уральского отделения Российской Академии наук, Екатеринбург
Уральский федеральный университет им. Б.Н. Ельцина, Екатеринбург
E-mail: makhnev@imm.uran.ru
сти вершин — сильно регулярные графы со вторым собственным значением < г для данного натурального числа г. Заметим, что сильно регулярный граф с нецелым собственным значением является графом в половинном случае, а вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы в половинном случае, либо имеет диаметр 2, либо является графом Тейлора. Таким образом, задача Кулена может быть решена пошагово для г = 1,2,...
В работе [1] классифицированы дистанционно-регулярные графы, в которых окрестности вершин — сильно регулярные графы со вторым собственным значением, не большим 1.
Предложение 1. Пусть Г — дистанционно-регулярный граф диаметра, большего 2, в котором окрестности вершин — сильно регулярные графы со вторым собственным значением, не большим 1. Если и — вершина графа Г, А = [и], то выполняется одно из следующих утверждений:
1 диаметр Г равен 2 и либо
(1) А — объединение изолированных ребер и Г — сильно регулярный граф с X = 1, либо
(И) А — дополнительный граф к (п х п) -решетке или графу Шрикханде и Г — дополнительный граф к ((п + 1) х (п + 1))-решетке, либо
(111) А — дополнительный граф к треугольному графу Т(п) или графу Чанга и Г — дополнительный граф к Т(п + 2), или п = 6, и Г имеет параметры (3 6,15,6,6) или (28,15,6,10), либо
ДИСТАНЦИОННО-РЕГУЛЯРНЫЕ ГРАФЫ
397
(IV) А — дополнительный граф к графу Петерсе-на, Клебша или Шлефли и Г — граф Клебша (локально Т(5)-граф), или локально 00(2,4)-граф с параметрами (64,27,10,12);
2) диаметр Г больше 2, и либо
(1) [и] — граф в половинном случае с параметрами (4п + 1,2п, п - 1, п), 1 < п < 2 и Г — граф Тейлора, либо
(И) А — объединение изолированных ребер, либо
(ш) А — дополнительный граф к (3 х 3) -решетке и Г — граф Джонсона I(6,3), либо
(IV) А — дополнительный граф к треугольному графу Т(п), п = 6 и Г — граф Тейлора на 32 вершинах или п = 5 и Г — граф Конвея—Смита или граф Доро, либо
(V) А — дополнительный граф к графу Шлефли или Клебша и Г — граф Тейлора на 56 вершинах или единственный дистанционно-регулярный граф с массивом пересечений {16, 10, 1; 1,5, 16}.
В работе [2] классифицированы дистанционно-регулярные графы, в которых окрестности вершин — сильно регулярные графы со вторым собственным значением г, 1 < г < 2.
Предложение 2. Пусть Г — дистанционно-регулярный граф диаметра, большего 2, в котором окрестности вершин — сильно регулярные графы со вторым собственным значением г, 1 < г < 2. Если и — вершина графа Г, то либо Г — сильно регулярный граф с параметрами (6,4,2,4), (27,16,10,8), (35, 16, 6, 8), (100,36,14,12), (162,56,10,24), (176,40,12,8), (210, 95, 40, 45), (245,64,18,16), (275,112,30,56), (372, 56, 10, 8) или (486,100,22,20), либо диаметр Г больше 2 и верно одно из утверждений:
1) [и] — объединение изолированных 3-клик;
2) [и] — граф в половинном случае с параметрами (4п + 1,2п, п - 1, п), 4 < п < 12 или псевдогеометрический граф дляр02(4, 0, г е {1,2,3,7,9,12,17,27} и Г является графом Тейлора;
3) Г — граф Джонсона I(8,4);
4) Г — граф Тервиллигера с массивом пересечений {50,42,1; 1,2,50} или {50,42,9; 1,2,42};
5) Г — антиподальное 3-накрытие сильно регулярного графа с параметрами (162,56,10,24), имеющее массив пересечений {56,45,16,1; 1,8,45,56};
6) Г имеет массив пересечений {81,6 0,1; 1,20,81}.
В работе [3] начато изучение дистанционно-
регулярных графов, в которых окрестности вершин — сильно регулярные графы со вторым собственным значением г, 2 < г < 3. В частности, получена редукция к графам, в которых окрестности вершин — исключительные графы или псевдогеометрические графы для р05 г). В [4—6] найдены массивы пересечений дистанционно-регуляр-
ных графов диаметра, большего 3, в которых окрестности вершин — псевдогеометрические графы для р05 г). В [7] найдены параметры исключительных сильно регулярных графов с собственным значением 3. В [8—10] описание дистанционно-регулярных графов, в которых окрестности вершин — исключительные сильно регулярные графы с собственным значением 3, сведено к случаю, когда окрестности вершин имеют параметры (35,18,9,9), (36,21,12,12), (40, 27, 18, 18), (50,28,15,16), (56,45,36,36), (64,27,10,12).
В данной работе завершено исследование дистанционно-регулярных графов, в которых окрестности вершин — сильно регулярные графы со вторым собственным значением г, 2 < г < 3.
Теорема. Пусть Г — вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы с параметрами (35,18,9,9), (3 6,21,12,12), (40, 27, 18, 18), (50,28,15,16), (56,45,36,36), (64, 27, 10, 12). Тогда [и] имеет параметры (35,18,9,9) и верно одно из утверждений:
1) Г — сильно регулярный граф с параметрами (76,35,18,14) или (64,35,18,20);
2) Г является графом Тейлора с массивом пересечений {35,16,1;1,16,35}.
Графы с параметрами, указанными в условии теоремы, существуют — это полярный граф
О+(6,2), граф ранга 3 для группы и3(3) со стабилизатором точки Х2(7), дополнительный граф для 00(3,3), блочный граф для р04(3,7), дополнительный граф для графа Гевиртца и аффинный полярный граф УО"(6,2) соответственно. Аффинный
полярный граф УО+(6,2) имеет параметры (64, 35, 18, 20). Существование графа с параметрами (76,35,18,14) неизвестно.
Следствие. Пусть Г — дистанционно-регулярный граф диаметра, большего 2, в котором окрестности вершин — сильно регулярные графы со вторым собственным значением г, 2 < г < 3. Если и — вершина графа Г, то верно одно из утверждений:
1) [и] — объединение изолированных 4-клик;
2) [и] — граф в половинном случае с параметрами (4п + 1,2п, п - 1, п), 7 < п < 12 или псевдогеометрический граф для р03(6, г), г е {2,3,4,8,10,17,20,24,38,52} и Г является графом Тейлора;
3) [и] является (5 х 5) -решеткой и Г — граф Джонсона I(10, 5) или граф с массивом пересечений {25,16,1;1,8,25};
4) [и] является псевдо-00(4,2)-графом и граф Г имеет массив пересечений {45,32,12,1; 1,6,32,45};
5) [и] является псевдо-00(4,6)-графом и Г — граф с массивом пересечений {125, 96, 1; 1,48, 125};
398
МАХНЕВ, ПАДУЧИХ
6) [и] — граф с параметрами (99,14,1,2), Г имеет массив пересечений {99,84,1;1,14,99}, {99, 84, 1; 1, 12, 99} или {99,84,30; 1,6,54};
7) [и] — граф с параметрами (115,18,1,3), Г имеет массив пересечений {115,96,8;1,8,92} или {115, 96, 30, 1; 1, 10, 96, 115};
8) граф [и] либо изоморфен треугольному графу Т(7) и Г — половинный граф 7-куба, либо сильно регулярен с параметрами (169, 42, 5, 12) и Г имеет массив пересечений {169, 126, 1;1,42, 169};
9) [и] — граф с параметрами (96,19,2,4), Г имеет массив пересечений {96,76,1;1,19,96}, или [и] — граф с параметрами (256,51,2,12), Г имеет массив пересечений {256,204,1;1,51,256}.
До конца работы предполагается, что Г — вполне регулярный граф с параметрами (V, к, X, д), в котором окрестности вершин сильно регулярны с параметрами (Vк ', д') и неглавными собственными значениями 3,02. Зафиксируем вершину и е Г и положим Гг = Гг(и), к = | Гг|.
Лемма 1 [7, лемма 3]. Пусть и, ^ — вершины из Г с й(и, м>) = 2. Тогда выполняются следующие утверждения:
36 • 14, то д = 27, v = 232, противоречие с тем, что 2•36•39
кратность 6 равна -
9 • 18
1)
(И'- 3)v' — м — (И '-82>v'.
— и —
к - 3 к -02
2) если X t — множество вершин из [w] - [u], смежных точно с i вершинами из [u] n [w], x = \Xt|,
то x0 -д< (v'- x°)(v '-^)(3 - Q2)2;
(2k - 3 -e2)2
ii<
2k - 20-
^ ^' (3 -0 2) 3) если х0 = ц, то д < —1-—.
0 Н Н (2к - 202) Лемма 2. Если параметры (Vк,д') принадлежат списку из условия теоремы, и Г является сильно регулярным графом, то Г имеет параметры (76,35,18,14) или (64,35,18,20).
Доказательство. Пусть параметры (Vк , д') принадлежат списку из условия теоремы и к' , 3,02 — собственные значения графа [и]. Если ¿(Г) = 2 и Г имеет неглавные собственные значения п - т,-т, то по [5, лемма 1] число т - 1 делит V'- к'- 1. Далее, т > -02, п - т > 3, поэтому
т -1 < у'-
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.