ДОКЛАДЫ АКАДЕМИИ НАУК, 2015, том 462, № 3, с. 268-273
МАТЕМАТИКА
УДК 519.17
АНТИПОДАЛЬНЫЕ ДИСТАНЦИОННО-РЕГУЛЯРНЫЕ НАКРЫТИЯ ГРАФОВ ЭРМИТОВЫХ ФОРМ Шт(2,
© 2015 г. Член-корреспондент РАН А. А. Махнев, Д. В. Падучих, Л. Ю. Циовкина
Поступило 02.06.2014 г.
DOI: 10.7868/S0869565215150049
Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины а графа Г через Г,(а) обозначим /-окрестность вершины а, т.е. подграф, индицированный Г на множестве всех вершин, находящихся на расстоянии / от а. Положим [а] = Г^а), а1 = {а} и [а].
Если вершины и, м> находятся на расстоянии / в Г, то через Ъ(и, (через с((и, обозначим число вершин в пересечении Г,-+1(и) (Г,-_х(и)) с [^]. Граф Г диаметра d называется дистанционно-регулярным с массивом пересечений {Ъ0, Ъх, ..., Ъdс1, ..., cd}, если значения Ъ(и, w) и с ¡(и, не зависят от выбора вершин и, м> на расстоянии / в Г для любого / = 0, 1, ..., d. Положим а/ = к — Ъ1 — с. Заметим, что для дистанционно-регулярного графа Ъ0 — это степень графа, с1 = 1. Граф Г диаметра d называется дистанционно-транзитивным, если для любого / е {0, 1, ..., d} и для любых двух пар вершин (и, и (у, ¿) с d(u, = d(y, ¿) = / найдется автоморфизм g графа Г такой, что (и^ ^) = (у, ¿). Для подмножества X автоморфизмов графа Г через Б1х(Х обозначается множество всех вершин графа Г, неподвижных относительно любого автоморфизма из X. Далее, через р1ц (х, у) обозначим число вершин в подграфе Г,(х) п ГДу) для вершин х, у, находящихся на расстоянии I в графе Г. В дистанционно-регулярном графе числа р(х, у) не зависят от выбора вершин х, у, обозначаются ри называются числами пересечений графа Г.
Институт математики и механики им. Н.Н. Красовского
Уральского отделения Российской Академии наук, Екатеринбург
Уральский федеральный университет им. Б.Н. Ельцина, Екатеринбург
E-mail: makhnev@imm.uran.ru
Граф называется реберно-симметричным, если его группа автоморфизмов действует транзитивно на множестве его дуг (упорядоченных ребер).
В [1] классифицированы антиподальные дистанционно-регулярные накрытия примитивных графов ранга 3.
Предложение [1]. Пусть Г — антиподаль-ный дистанционно-регулярный граф диаметра 5, являющийся накрытием графа ранга 3. Тогда Г — один из следующих дистанционно-транзитивных графов:
1) двудольное удвоение сильно регулярного графа без треуольников с параметрами (к2 + 1, к, 0, 1), к е {2, 3, 7}, (16, 5, 0, 2), (56, 10, 0, 2), (77, 16, 0, 4) или (100, 22, 0, 6);
2) граф Джонсона /(10, 5) (2-накрытие свернутого графа Джонсона /(10, 5));
3) 5-куб (2-накрытие свернутого 5-куба);
4) граф додекаэдра (2-накрытие графа Петерсе-на);
5) половинный 10-куб (2-накрытие свернутого половинного 10-куба);
6) граф смежных классов тернарного кода Голея (3-накрытие графа с параметрами (243, 22, 1, 2)).
К сожалению, в [1] при описании антиподаль-ных дистанционно-регулярных накрытий диаметра 4 примитивных графов ранга 3 некорректно рассмотрен случай графов эрмитовых форм. В данной работе исследуются антиподальные дистанционно-регулярные накрытия графов эрмитовых форм Иегш(2, #2), для которых группа автоморфизмов индицирует группу ранга 3 на антипо-дальном частном.
Граф эрмитовых форм Иегш(п, #2), q — степень простого числа, является дистанционно-регуляр-
ным графом диаметра n с v = q
= q-1( q - (-i /).
q + 1
b=
2n 2 j
_ q - q
q + 1
cJ =
2
Граф Иегш(2, д2) сильно регулярен с параметрами (д4, (д — 1)(д2 + 1), д — 2, (д — 1)д) и спектром
к1, (д — 1)(?2-9,(92 +1), —(д2 - д + 1)(9- 1)9 +и.
Теорем а. Пусть Г — реберно-симметричный антиподальный дистанционно-регулярный граф диаметром 4, являющийся накрытием графа эрмитовых форм Иегш(2, д2). Если О = Аи^Г) индуцирует группу ранга 3 на антиподальном частном графа Г, то Г — один из следующих графов:
1) граф Уэлса (2-накрытие графа Иегш(2, д2), изоморфного графу свернутого 5-куба с параметрами (16, 5, 0, 2));
2) граф смежных классов укороченного тернарного кода Голея (3-накрытие графа эрмитовых форм Иегш(2, 32) с параметрами (81, 20, 1, 6)).
Следствие. Пусть Г — антиподальный дистанционно-регулярный граф диаметра 4 и степени к > 2, являющийся накрытием примитивного графа ранга 3. Тогда Г — один из следующих графов:
1) 4-куб (2-накрытие свернутого 4-куба) или граф Уэлса (2-накрытие свернутого 5-куба);
2) 8-клетка Татта с массивом пересечений {6, 4, 2, 1; 1, 1, 4, 6} (3-накрытие обобщенного четырехугольника О0(2, 2));
3) граф Джонсона /(8, 4) (2-накрытие свернутого графа 1 (8, 4));
4) половинный 8-куб (2-накрытие свернутого половинного 8-куба);
5) граф Конвея—Смита (3-накрытие графа Т(7));
6) граф с массивом пересечений \ 20, 18, —^ ,
I г
1; 1, - , 18, 20 > (г-накрытие графа эрмитовых г \
форм Иегш(2, 32), г е {2, 3, 6});
7) граф с массивом пересечений \ 22, 21, 6(г—^ ,
I г
1; 1, - , 21, 22 > (г-накрытие графа Хигмена-Сим-
г \ са, г е {2, 3, 6});
8) первый граф Сойчера (3-накрытие графа с параметрами (162, 56, 10, 24));
9) второй граф Сойчера (3-накрытие графа Судзуки с параметрами (1782, 416, 100, 96));
10) 3. П24 -граф (3-накрытие графа 3-транспозиций с параметрами (306936, 31671, 3510, 3240).
Графы из пунктов 1)—5), 8)—10) дистанционно-транзитивны. Ввиду [2] группа автоморфизмов графа из пункта 6) при г Ф 3 действует интранзитивно
на множестве вершин. Ввиду [3, 4] группа автоморфизмов любого графа из пункта 7) действует интранзитивно на множестве антиподальных классов.
Сначала приведем вспомогательные результаты.
Лемма 1. Пусть Г — сильно регулярный граф с V = 2к + 1 и неглавными собственными значениями г, — т. Тогда выполняются утверждения:
1) к = 2гт + т — г — 1, X = гт — 1, ц = (т — 1)(г +
, 1\ , 1 (2т -1)к + 1) = гт + т — г — 1, кратность г равна --'—
г + т
и кратность —т равна
( 2 г + 1) к. г + т
2) если Г имеет дистанционно-регулярное накрытие А, то либо Г — пятиугольник и А — десятиугольник, либо Г — дополнительный граф к треугольному графу Т(7) и А — граф Конвея—Смита с массивом пересечений {10, 6, 4, 1; 2, 6, 10}.
Доказательство. По условию имеем ц = = к — X — 1. Дополнительный граф Г имеет параметры к = к, X = ц — 1 и ц = X + 1 и неглавные собственные значения т — 1, —(г + 1). Отсюда
(т — 1)(г + 1) = к — ц = ц и гт = к — ц = X + 1, поэтому к = 2гт + т — г — 1.
Кратность г равна
Симметрично, кратность —т равна
= ( 2 г + 1) к г + т
( т - 1) к ( к + т ) = ( 2 т - 1 ) к ц(г + т) г + т
гк( к + г + 1) = гт( г + т)
Пусть Г имеет дистанционно-регулярное накрытие А. Если X = 0, то Г — пятиугольник и А — десятиугольник. Если X > 0, то X2 + 4к = (гт + 3)2 + + 4т — 4г — 12 — квадрат натурального числа, поэтому 4т — 4г — 12 = 0 и т = г + 3. Значит, к = 2г2 + + 6г + 2, X = г2 + 3г — 1, ц = г2 + 3г + 2 и 2г+3 делит (2г2 + 6г + 2)(2г + 5). Поскольку (2г + 3, 2г2 + 6г + + 2) = (2г + 3, 3г + 2) делит 5, то г = 1, Г — дополнительный граф к треугольному графу Т(7) и А — граф Конвея—Смита с массивом пересечений {10, 6, 4, 1; 1, 2, 6, 10}. Лемма доказана.
Из леммы 1 и [1, предложение 1.5] следует, что дистанционно-регулярное накрытие диаметра 4 может существовать не более чем для одного из пары дополнительных сильно регулярных графов.
Лемма 2 [5, лемма 1.1]. Пусть Г — антиподальный граф диаметра 4 с массивом пересечений
270
МАХНЕВ и др.
[к, Ъ1, (r— 1)ц, 1; 1, ц, Ъ1, к}, 0О > 0! > ... > 04 - собственные значения Г и mj — кратность 0;. Тогда
рицы P1 являются собственными значениями графа Г кратностей m0 = 1, 2, ..., md. Матрицы Pи Q,
mjPi (j )
1) антиподальное частное Г — связный сильно ре- у которых на месте (., /) стоят ру(0 и д(-) =
К1
соответствено, называются первой и второй матрицей собственных значений схемы и связаны равенством РО = ОР = VI.
Пусть и/ и М/ — левый и правый собственные векторы матрицы Р1, отвечающие собственному значению р1(/) и имеющие первую координату 1. Тогда кратность т/ собственного значения р1(/) равна v/{Uj, м/). Более того, М/являются столбцами матрицы Р и тии/ являются строками матрицы О.
Подстановочное представление группы О = = Аи;(Г) на вершинах графа Г обычным образом дает матричное представление у группы О в ОЬ^, С). Пространство С^ является ортогональной прямой суммой собственных О-инвариантных подпространств Щ0, ..., матрицы смежности А = А1 графа Г. Для любого g е О матрица перестановочна с А, поэтому подпространство Щ является у(О)-инвариантным. Пусть х. — характер представления уW¡. Тогда (см. § 3.7 [6]) для g е О получим
й
-1
гулярный граф с параметрами ( - , к, а1, rc2 J и собственными значениями к и 02, 04, которые являются корнями уравнения x2 — (a1 — rc2)x — (к — rc2) = 0. Оставшиеся собственные значениями 01, 03 являются корнями уравнения x2 — a1x — к = 0;
2) верны равенства к = —0103 и (02 + 1)(04 + 1) =
= (01 + 1)(0з + 1);
3) параметры антиподального частного выражаются через r и собственные значения к = 0О, a1 =
= 01 + 0з, Ъ1 = —(02 + 1)(04 + 1), С2 = ( 00 + 0204 ) ;
r
4) кратности собственных значений равны m0 = 1, (04 + 1)k(k - 04)
m2 =
' v ,
■, m4 = — m2 - 1,
ГС2(04 - 02) 4 Г 2
mi
= (r - 1)v
г ( 2 + а10;- / к)' для I = 1, 3;
5) собственные значения 02, 04 целые, 04 < —2, 02 > 0 с 02 = 0 тогда и только тогда, когда Г — двудольный граф, 03 < —1 и 01, 03 целые, если а1 Ф 0.
Доказательство теоремы опирается на метод Хигмена работы с автоморфизмами дистанционно-регулярного графа, представленный в третьей главе монографии Камерона [6]. При этом граф Г рассматривается как симметричная схема отношений (X, Ш) с d классами, где X — множество вершин графа, В0 — отношение равенства на X и для I > 1 класс В. состоит из пар (и, м) таких, что d(u, м) = Для и е Г положим к1 = |Г,-(и)|, V = |Х|. Классу В.1 отвечает граф Г,- на множестве вершин X, в котором вершины и, м> смежны, если (и, м) е В.. Пусть А. — матрица смежности графа Г. для . > 0 и
А0 = I — единичная матрица. Тогда АА/ = ^ Рц Ак
„ I
для чисел пересечений ру.
Пусть Р. — матрица, в которой на месте (/, I) стоит р\:. Тогда собственные значенияр1(0), ..., р-^) мат-
Xi(g) = v- X Qijaj(g),
У = о
где О/^) — число точек х из Xтаких, что (х, X) е В/.
Лемма 3. Пусть Г — ди
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.