ДОКЛАДЫ АКАДЕМИИ НАУК, 2014, том 459, № 2, с. 149-153
МАТЕМАТИКА
УДК 519.17
АВТОМОРФИЗМЫ ГРАФА С МАССИВОМ ПЕРЕСЕЧЕНИИ {115, 96, 30, 1; 1, 10, 96, 115}
© 2014 г. Член-корреспондент РАН А. А. Махнев, Д. В. Падучих, М. С. Самойленко
Поступило 30.12.2013 г.
DOI: 10.7868/S0869565214270048
Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, b — вершины графа Г, то через d(a, b) обозначается расстояние между а и b, а через Г(а) — подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии i в Г от вершины а. Подграф Г1(а) называется окрестностью вершины а и
обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г диаметра d называется антиподальным, если отношение — совпадать или находиться на расстоянии d — является отношением эквивалентности. Антиподальным частным Г' называется граф, вершинами которого являются анти-подальные классы графа Г, и два антиподальных класса смежны, если один из них содержит вершину, смежную с вершиной другого класса. Анти-подальный граф Г называется r -накрытием (своего антиподального частного), если каждый его антиподальный класс содержит точно r вершин.
Если вершины u, w находятся на расстоянии i в Г, то через b,(u, w) (через с(и,w)) обозначим число вершин в пересечении ri+1(u) (в пересечении Гм(и)) с [w]. Граф диаметра d называется дистанционно-регулярным с массивом пересечений {b0,...,bd-i;ci,...,Cd}, если значения b(u,w) и с (u,w) не зависят от выбора вершин u, w на расстоянии i. Положим аi = к - bi - с и kt = |Г,(u)| (значение kt не зависит от выбора вершины и).
В [1] изучены дистанционно-регулярные графы, в которых окрестности вершин изоморфны сильно регулярному графу с параметрами (115, 18, 1, 3). С помощью теорем 1, 2 из [2] получается
Институт математики и механики им. Н.Н. Красовского
Уральского отделения Российской Академии наук, Екатеринбург
Уральский федеральный университет им. Б.Н. Ельцина, Екатеринбург
Предложение 1. Пусть Г — дистанционно-регулярный граф, в котором окрестности вершин сильно регулярны с параметрами (115, 18,1,3).
Тогда выполняется одно из следующих утверждений:
1) Г — сильно регулярный граф с параметрами (576,115,18,24), (484,115,18,30) или (392,1 15,18,40);
2) диаметр Г равен 3, Г имеет массив пересечений {115,96, 8; 1,8, 92} и спектр 1151,23217,3713, -9805;
3) диаметр Г равен 4 и Г имеет массив пересечений {1 15,96,30,1; 1,10,96,115}.
Если Г — дистанционно-регулярный граф с массивом пересечений {115,96,3 0,1; 1,10,96,115}, то
1 1 И то210 -,345 -966 -,-46
он имеет спектр 115 , 23 , 3 ,-5 ,-25 , для любой вершины u е Г подграф r(u) является сильно регулярным с параметрами (115,18,1,3), а подграф r2(u) является дистанционно-регулярным с массивом пересечений {75,64,18,1;1,6,64,75}. Ан-типодальные частные Г и r2(u) сильно регулярны с параметрами (392,1 15,18,40) и (276,75,10,24) соответственно.
В данной работе найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (115, 18, 1, 3) и дистанционно-регулярного графа с массивом пересечений {115,96,30,1; 1,10,96,115}.
Теорема 1. Пусть Г — сильно регулярный граф с параметрами (115,18,1,3), G = Aut(r), g — элемент простого порядка p из G, D. = Fix(g).
Тогда n(G) с {2,3,5,23} и выполняется одно из утверждений:
1) Q — пустой граф, либо p = 5 и a1(g) = 15,55, либо p = 23 и a1(g) = 23;
2) Q является l-кокликой, 1 < l < 13, p = 3, l сравнимо с 1 по модулю 3 и a1(g) = 24s + 23 - 51 Ф 0;
3) Q = а1 для некоторой вершины а ей и p = 2.
Теорема 2. Пусть Г — дистанционно-регулярный граф с массивом пересечений {115, 96, 30, 1; 1, 10, 96, 115} и G = Aut(r). Тогда |G| делит 32 • 7.
2*
149
Приведем некоторые вспомогательные результаты.
Лемма 1 [3]. Пусть Г — сильно регулярный граф с параметрами (392,1 15,18,40), G = Aut(r), g — элемент из G простого порядка p и Q = Fix(g).
Тогда | G| делит 8 • 7 • 23 и выполняется одно из следующих утверждений:
1) Q — пустой граф, либо p = 2 и a1(g) = 56r, либо p = 7 и a1(g) = 140;
2) |Q| = 1, p = 23 и a1(g) = 115.
Лемма 2 [4, §3]. Пусть Г является сильно регулярным графом с параметрами (v, k, X, ц) и неглавными собственными значениями r, s, s < 0.
Если А — индуцированный регулярный подграф из Г степени d на w вершинах, то
. , w(k - d) . s < d--1-- < r,
v - w
причем одно из равенств достигается тогда и только тогда, когда каждая вершина из Г - А смежна
w(k - d) .
точно с —-- вершинами из А.
v - w
Пусть Г является сильно регулярным графом с параметрами (115,18,1,3) и неглавными собственными значениями 3 и —5. Если А — индуцированный регулярный подграф из Г степени d на w вершинах, то
d - 3 < wo^-d!) < d+5.
115 - w
Поэтому число вершин в коклике не больше 25. Если А — индуцированный регулярный подграф из Г степени 6 на w вершинах, то w > 23.
Доказательство теоремы опирается на метод Хигмена работы с автоморфизмами дистанционно-регулярного графа, представленный в третьей главе монографии Камерона [5]. При этом графу Г диаметра d на n вершинах отвечает симметричная схема отношений (X, R) с d классами, где X— множество вершин графа, R0 — отношение равенства на Xи для i > 1 класс R состоит из пар (u, w) таких, что d(u, w) = i. Для u е Г положим kt = | Г, (u)|. Классу R отвечает граф Г, на множестве вершин X, в котором вершины u, w смежны, если (u, w) е R. Пусть Аi — матрица смежности графа Г, для i > 0 и
А0 = I — единичная матрица. Тогда AAj = S РуА
i
для чисел пересечений pi].
Пусть P — матрица, в которой на месте (j l) стоит pj. Тогда собственные значения к = =p1(0), ..., p1(d) матрицы P1 являются собственными значениями графа Г кратностей m0 = 1,2,..., md. Матрицы P и Q, у которых на месте
(i, j) стоят p:(i) и д( =
mMf)
k
соответственно, на-
зываются первой и второй матрицами собственных значений схемы и связаны равенством Рй = йР = | X11, где I — единичная матрица порядка й + 1.
Подстановочное представление группы О = = Аи^Г) на вершинах графа Г обычным образом дает матричное представление у группы О в
, С). Пространство С ^ является ортогональной прямой суммой собственных О-инвариант-ных подпространств Ж0,...,матрицы смежности А1 графа Г. Для любого g е О матрица перестановочна с А1, поэтому подпространство Щ является -инвариантным. Пусть х — характер представления . Тогда (см. § 3.7 [5]) для g е О й
получим XI(g) = Vйуау(g), где ау(g) - число
у=0
точек х из X таких, что (х, xg) е Яу. Заметим, что значения характеров являются целыми алгебраическими числами, и если правая часть выражения для х¡(я) — число рациональное, то х^) — целое число.
Лемма 3. Пусть Г — сильно регулярный граф с параметрами (115, 18,1,3), О = АШ(Г), g — элемент простого порядка р из О и х1 — характер, полученный при проектировании на подпространство размерности 69. Тогда
5ао^) + а^) - 23
X1(g) =:
8
Доказательство. Имеем
Q =
1
69
1 1
23 _ 23
2 8
25 15
V 2 8 у и значение характера, полученного при проектировании на подпространство размерности 69, равно
X (£) = 24ао^) + 4а^) - а2^)
Подставляя в эту формулу значение а2^) = = V - ао^) - а^), получим
5а о^) + а^) - 23
X1(g)
8
В леммах 4, 5 предполагается, что Г — сильно регулярный граф с параметрами (115,18,1,3), g — автоморфизм Г простого порядка р и О =
Лемма 4. Выполняются следующие утверждения:
1) если р = 2, то каждая вершина из Г - О смежна с вершиной из О;
2) если О — пустой граф, то либо р = 5 и а^) = 15,55, либо р = 23 и а^) = 23;
3) если О является 1-кокликой, то р = 3, 1 < I < 13, I сравнимо с 1 по модулю 3 и а^) = = 24г + 23 - 51 Ф 0;
4) О не является п -кликой для п > 2. Доказательство. Если О — пустой граф,
то либо р = 5 и а1(^) = 15,55,95, либо р = 23 и а1(^) = 23. Но в случае а1(^) = 95 имеется только
4 орбиты, в которых вершина и не смежна с и&, и
2
4 орбиты, в которых вершина и не смежна с и8 , поэтому имеется не менее 15 орбит, являющихся 5-кликами, противоречие с тем, что Г не содержит 4-клик.
Пусть О является я-кликой. Если п = 1, тор делит 18 и 96, поэтому либо р = 3 и а1(^) = 24г + 18, либо р = 2. Но в последнем случае имеем противоречие с утверждением 1).
Если О содержит смежные вершины и, , то р
делит |[и] - №= 16 и |Г2(и) пГ2(^)| = 80, поэтому р = 2, я = 3, противоречие с утверждением 1).
Пусть О является I-кокликой, I > 2. Для двух вершин и, № еП число р делит |[и] п М = 3 и |Г2(и) п Г2(^)| + 2 -1, поэтому р = 3, I сравнимо с 1 по модулю 3 и а1(^) = 24г + 23 - 51. Число ребер между О и Г - О равно 18|й|, поэтому некоторая вершина из Г - О смежна по крайней мере с
——. Отсюда |й| < 16. Заметим, что вершина 115 -|П|
из треугольной (-орбиты не смежна с вершинами из О, а вершина из 3-кокликовой (-орбиты смежна не более чем с 3 вершинами из О.
В случае 1= 16 имеем а1(^) = 21. Поэтому число ребер между О и Г - О равно 18 • 16, но не больше 78 • 3, противоречие.
Если а1(^) = 0,то/ = 3п + 1, 8г + 6 - 5п = 0 ,п = 6 иг = 3, противоречие.
Лемма 5. Если О содержит геодезический
2-путь, то р = 2 и □ = а1 для некоторой вершины а ей.
Доказательство. Пусть Г содержит собственный сильно регулярный подграф А с X д = 1
и цд = 3. Тогда 4 + 4(кд - 3) = 452 и кА = 52 + 2. Отсюда 5 = 2, А имеет параметры (15, 6, 1, 3) и число ребер между А и Г - А равно 15 • 12, но не больше 100, противоречие.
Если р > 5, то О — сильно регулярный подграф с Хп = 1 и = 3, противоречие.
Пусть р = 3. Тогда число | сравнимо с 1 по модулю 3, поэтому | = 4,7,..., 43. Степень вершины в О делится на 6, Хп = 1 и = 3. По теореме Бо-уза—Доулинга каждая связная компонента графа О является одновершинным графом или вполне регулярным графом с параметрами (V', к', 1,3).
Пусть А — связная компонента графа О, содержащая вершину а. Если степень графа А больше
6, то |Д| > 1 + 12 + 12^10, противоречие. Значит,
кА = 6 и А — сильно регулярный граф с параметрами (15, 6, 1, 3), противоречие.
Пусть р = 2. Тогда число | нечетно, степень вершины в О четна, Xп = 1 и цп е {1,3}. Если вершины и, и8 смежны, то и смежна с единственной вершиной из О. Если же вершины и, и8 не смежн
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.