ДОКЛАДЫ АКАДЕМИИ НАУК, 2015, том 461, № 6, с. 629-632
МАТЕМАТИКА
УДК 519.17
ГРАФЫ ДИАМЕТРА, НЕ БОЛЬШЕГО 3, В КОТОРЫХ ОКРЕСТНОСТИ ВЕРШИН - ПСЕВДОГЕОМЕТРИЧЕСКИЕ ГРАФЫ ДЛЯ рв, _3(,, 1)
© 2015 г. А. К. Гутнова, член-корреспондент РАН А. А. Махнев
Поступило 02.06.2014 г.
БО1: 10.7868/80869565215120038
Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины а графа Г через Г ¡(а) обозначим /-окрестность вершины а, т.е. подграф, индуцированный Г на множестве всех вершин, находящихся на расстоянии / от а. Подграф Г(а) = Г1(а) называется окрестностью вершины а и обозначается [а], если граф Г фиксирован. Положим а1 = {а} и [а]. Если не оговорено противное, то слово "подграф" будет означать "индуцированный подграф".
Пусть 9 — некоторый класс графов. Граф Г назовем локально 9 -графом, если [а] лежит в 9 для любой вершины а графа Г.
Пусть Г — граф, а, Ь еГ. Тогда число вершин в [а] п [Ь] обозначается через ц(а,Ь) (Х(а,Ь)), если а, Ь находятся на расстоянии 2 (смежны) в Г; [а] п [Ь] называется ц-подграфом (X -подграфом).
Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а из Г равна к. Граф Г назовем реберно-регулярным с параметрами (V, к, X), если он содержит V вершин, регулярен степени к и каждое его ребро лежит в X треугольниках. Граф Г — вполне регулярный граф с параметрами (V, к, X, р), если он реберно-регуля-рен с соответствующими параметрами и [а] п [Ь] содержит точно ц вершин для любых двух вершин а, Ь, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
Система инцидентности с множеством точек Р и множеством прямых ¡£ называется а -частич-
Северо-Осетинский государственный университет им. К.Л. Хетагурова, Владикавказ Институт математики и механики им. Н.Н. Красовского
Уральского отделения Российской Академии наук, Екатеринбург
E-mail: makhnev@imm.uran.ru
ной геометрией порядка (я, г), если каждая прямая содержит ровно 5 + 1 точку, каждая точка лежит ровно на г + 1 прямой, любые две точки лежат не более чем на одной прямой и для любого антифлага (а, I) е (Р, £) найдется точно а прямых, проходящих через а и пересекающих I (обозначение рОа(я, г)). В случае а = 1 геометрия называется обобщенным четырехугольником и обозначается г). Точечный граф геометрии определяется на множестве точек Р и две точки смежны, если они лежат на прямой. Точечный граф геометрии рОа(я, г)
сильно регулярен с параметрами V = (я + 1) (1 + а),
к = + 1), X = я - 1 + г(а - 1), ц = а(г + 1). Сильно регулярный граф с такими параметрами для некоторых натуральных чисел а, я, г называется псевдогеометрическим графом для рОа(я, г).
Дж. Кулен предложил задачу изучения дистанционно-регулярных графов, в которых окрестности вершин — сильно регулярные графы с неглавным собственным значением < г для данного натурального числа г. Заметим, что сильно регулярный граф с нецелым собственным значением является графом в половинном случае, а вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы в половинном случае, либо имеет диаметр 2, либо является графом Тейлора. Таким образом, задача Кулена может быть решена пошагово для г = 1,2,...
В работе [1] получено описание дистанционно-регулярных графов, в которых окрестности вершин — сильно регулярные графы с собственным значением 1.
Недавно [2] была завершена программа изучения дистанционно-регулярных графов, в которых окрестности вершин — сильно регулярные графы с собственным значением 2.
В [3] начато решение задачи Кулена для г = 3, а именно получена редукция задачи к изучению дистанционно-регулярных графов, в которых окрестности вершин являются псевдогеометрическими графами для р05_3(я, г) или исключитель-
630
ГУТНОВА, МАХНЕВ
ными сильно регулярными графами с неглавным собственным значением 3. В данной работе продолжается решение задачи описания дистанционно-регулярных графов, в которых окрестности вершин — псевдогеометрические графы для р05_3($, г). В [4] получены следующие результаты.
Предложение. Пусть Г — вполне регулярный граф, в котором окрестности вершин — псевдогеометрические графы для р05_3($, г). Тогда выполняется одно из следующих утверждений:
1) Г — сильно регулярный граф;
2) d(Г) = 3;
3) d(Г) > 4 и либо 5 = 4, либо 5 = 5 и г < 6.
Следствие 1. Пусть Г — дистанционно-регулярный граф диаметра d > 4, в котором окрестности вершин — псевдогеометрические графы для р05_3($, г). Тогда для вершины и еГ граф [и] является либо
1) (5 х 5)-решеткой и Г — граф Джонсона /(10, 5), либо
2) псевдо 00.(4, 2) -графом и граф Г имеет массив пересечений {45, 32, 12, 1; 1, 6, 32, 45} и спектр
451, 1542, 390, -3210, -935.
В данной работе получена редукция указанной задачи к задаче исследования дистанционно-регулярных графов диаметра, не большего 3, в которых окрестности вершин — псевдогеометрические графы для 00(4, г).
Теорем а. Пусть Г — вполне регулярный граф диаметра 3, в котором окрестности вершин — псевдогеометрические графы для р05_3($,г). Тогда выполняется одно из следующих утверждений:
1) 5 = 6 и Г — граф Тейлора;
2) 5 = 4 и окрестности вершин в Г — псевдогеометрические графы для 00(4, г);
3) 5 = 5.
Следствие 2. Пусть Г — дистанционно-ре -гулярный граф диаметра, не большего 3, в котором окрестности вершин — псевдогеометрические графы для р05_3($, г), s > 4. Тогда Г является сильно регулярным графом с параметрами (117, 36,15, 9), (232, 81, 30, 27), (287,126, 45, 63) или верно одно из утверждений:
1) s = 6 и Г — граф Тейлора;
2) s = 5, t = 1 и Г — половинный граф 7-куба.
Для сильно регулярных графов из заключения следствия 2 известно существование только графа с параметрами (117, 36,15, 9).
Лемма 1. Пусть Г — псевдогеометрический граф для р05_3($, г), А — регулярный подграф степени
(s - 3) (t + 1) на w вершинах. Тогда выполняются следующие утверждения:
1} (s + 1)(st - 3t + s - 6) < w < (s - 2)(st + s - 3) ; s - 3 s - 3
2) если Xi — множество вершин из Г - A, смежных точно с i вершинами из А, = |X,1, то
(2st +1 + 2s - 2)2w ■ x0 < (v - w)(v - x0)(t + 4)2;
(3) если w = x0, то 2(st + t + s + 1)w < v(t + 4).
Доказательство. Ввиду [5, § 3.15, упражнение 3] верны неравенства
3(t + 1)w
-(t + 1) < (s - 3)(t + 1)-
(s + 1) (1 + S3 )-w
< 3.
w < (s - 2) (1 +
(1+T-! )
и
< w.
Отсюда
(5 + 1)(5г - 3г + 5 - 6) 5 - 3
По [5, предложение 4.6.1]
* . Хо < (У - - Хо)(г + 4)2.
(2з(г +1) - 3 + (г +1))2
Поэтому
(25? + г + 25 - 2)2w ■ х0 < (v - т)(/ - х0)(? + 4)2.
Если w = Х0, то (2+ г + 25 - 2)м! < (V - w)(г + 4). Отсюда следует требуемое неравенство.
Лемма 2 [6, теорема 4.4.3]. Пусть Г — дистанционно-регулярный граф диаметра d > 3, 00 = к > 01 > ... > 0d — собственные значения графа Г. Если окрестности вершин сильно регулярны с неглавными собственными значениями г, 5 < 0, то
s > b- = -1 -■
)1+1
r < b =-1 -■
b1
+1
В леммах 3, 4 предполагается, что Г — связный вполне регулярный граф диаметра, большего 2, в котором окрестности вершин — псевдогеометрические графы для р05 _3($, г). Зафиксируем геодезический 3-путь в Г и положим Г(- = Г;(и), к1 = |Г;|.
Лемма 3 [4, лемма 2]. Если 5 < 6, то выполняется одно из следующих утверждений:
1) 5 = 4, [и] — псевдогеометрический граф для 00(4, г), г е { 1, 2,4,6, 8,11,12,16};
2) 5 = 5, [и] — псевдогеометрический граф для р02(5, г), г е {1, 2, 5, 6, 8, 11, 14, 16, 26};
3) 5 = 6, [и] — псевдогеометрический граф для р03(6,г), г е {2, 3, 4, 8, 10, 17, 20, 24, 38, 52}.
Лемма 4. Если диаметр Г больше 2, то либо 5 < 5, либо 5 = 6 и Г — граф Тейлора.
Доказательство. Имеем к = V=st + s + 4t +
+ 1 + -12-, X = к' = + 5 и Ь1 = 4г + 1 + —. По-
5 - 3 5 - 3
скольку диаметр Г больше 2, то ввиду леммы 1 имеем
ГРАФЫ ДИАМЕТРА, НЕ БОЛЬШЕГО 3
631
(я + 1)(яг - 3г + я - 6) я - 3
< ц < Ь1. Поэтому 3 — — 3? +
+ з2 - - 6 < 4яг + я - 3 и (я - 6я - 3)(г - 1) < 0. Отсюда я < 6.
В случае я = 6 имеем к' = 2ц' и по [7] Г — граф Тейлора.
Лемма, а вместе с ней и теорема доказаны.
В леммах 5—8 Г — дистанционно-регулярный граф диаметра 3, в котором окрестности вершин — псевдогеометрические графы для рО2(5, г). По
3(5/ + 2)
лемме 1 имеем 3(2г -1) < ц <:
2
Лемма 5. Если г < 5, то г = 1 и Г — половинный граф 7-куба.
Доказательство. Если г = 1, то для вершины и е Г граф А = [и] — треугольный граф Т(7). В этом случае каждый ц-подграф является октаэдром и Г — половинный граф 7-куба.
Если г = 2, то граф Д = [и] — псевдогеометрический граф для сети рО2(5, 2) с параметрами (36, 15, 6, 6). Из леммы 1 следуют неравенства 9 < ц < 18. Поскольку ц делит 36 • 20 , то ^е {9,10,12,15,16,18}. По лемме 2 имеем 01 < 9, 03 > -6.
Если ц = 9, то ввиду леммы 1 имеем Ь2 < 3, если ц = 10, то Ь2 < 3, а если ц = 12, то Ь2 < 2. Поскольку Ь1Ь2 делится на ц, то ц = 10, к2 = 72 и либо 01 > 9, либо Г имеет массив пересечений {36, 20, 1; 1, 10, 36} и кратности собственных значений 01 = 9 и 03 = -4 не целые, противоречие.
Если ц = 15,16,18, то Ь2 < 1, противоречие с тем, что Ь1Ь2 не делится на ц.
Если г = 5, то граф Д = [и] — псевдогеометрический граф для геометрии рО2(5, 5) с параметрами (81, 30, 9, 12). Из леммы 1 следуют неравенства
3 <
9ц
< 9, поэтому 27 < ц < 40. Поскольку ц
36 - ц
делит 81 ■ 50, то ^ е {27, 30}. По лемме 2 имеем 01 < 9, 03 >-13.
Если ц = 27, то ввиду леммы 1 имеем Ь2 < 3, если ц = 30, то Ь2 < 2, противоречие с тем, что Ь1Ь2 не делится на ц.
Лемма 6. Если г > 1, то г > 8. Доказательство. Если г = 6, то для вершины и е Г граф Д = [и] — геометрия рО2(5, 6) с параметрами (96, 35, 10, 14). Из леммы 1 следуют не-
равенства 11 <
21ц
< 21, поэтому 33 <ц< 48.
96 -ц
Поскольку ц делит 96 • 60, то ц е {36, 40, 45, 48}. По лемме 2 имеем 01 < 9, 03 > -16.
Если ц = 36, то ввиду леммы 1 имеем Ь2 < 2, а если ц = 40, 45, 48, то Ь2 < 1, противоречие с тем, что Ь1Ь2 не делится на ц.
Если г = 8, то граф Д = [и] — псевдогеометрический граф для геометрии рО2(5, 8) с параметрами (126, 45, 12, 18). Из леммы 1 следуют неравенства 45 <ц< 63. Поскольку ц делит 126 • 80, то це {45, 48, 56, 60
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.