научная статья по теме ОБ АВТОМОРФИЗМАХ СИЛЬНО РЕГУЛЯРНОГО ГРАФА С ПАРАМЕТРАМИ (486, 100, 22, 20) Математика

Текст научной статьи на тему «ОБ АВТОМОРФИЗМАХ СИЛЬНО РЕГУЛЯРНОГО ГРАФА С ПАРАМЕТРАМИ (486, 100, 22, 20)»

ДОКЛАДЫ АКАДЕМИИ НАУК, 2013, том 449, № 4, с. 389-392

МАТЕМАТИКА

УДК 519.17+512.54

ОБ АВТОМОРФИЗМАХ СИЛЬНО РЕГУЛЯРНОГО ГРАФА С ПАРАМЕТРАМИ (486, 100, 22, 20)

© 2013 г. Член-корреспондент РАН А. А. Махнев, Д. В. Падучих

Поступило 01.11.2012 г.

БО1: 10.7868/80869565213100058

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, Ь — вершины графа Г, то через d(a, Ь) обозначается расстояние между а и Ь, а через Г((а) — подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии I от вершины а. Подграф Г(а) = Г1(а) называется окрестностью вершины а и обозначается через [а], если граф Г фиксирован. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а. Для подграфа А пусть Х(А) — множество всех вершин из Г — А, смежных точно с I вершинами из А.

Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г. Граф Г называется реберно регулярным графом с параметрами (V, к, А), если Г содержит V вершин, является регулярным степени к и каждое ребро Г лежит в А треугольниках. Граф Г называется вполне регулярным графом с параметрами (V, к, А, ц), если Г реберно регулярен и подграф [а] п [Ь] содержит ц вершин в случае d(a, Ь) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом. Число вершин в [а] п [Ь] обозначим через А(а, Ь) (через ц(а, Ь)), если d(а, Ь) = 1 (если d(а, Ь) = 2, а соответствующий подграф назовем ц-подграфом (А-подгра-фом).

Через Кт,, , т обозначим полный п-дольный граф с долями порядков тъ ..., тп. Если т1 = ... ... = тп = т, то соответствующий граф обозначается через Кп х т. Если т > 2, то граф К1, т называется т-лапой. Треугольным графом Т(т), т > 5, называется граф с множеством неупорядоченных пар из Xв качестве вершин, |Х| = т, и пары {а, Ь}, {с, d} смежны тогда и только тогда, когда они имеют единственный общий элемент. Граф на множестве вершин X х У называется (т х я)-решеткой, если X = т > 2, |У| = п > 2, и вершины (х1, у1),

Институт математики и механики Уральского отделения Российской Академии наук, Екатеринбург

(х2, у2) смежны тогда и только тогда, когда х1 = х2 или у1 = у2.

Пусть Ш — некоторый класс графов. Граф Г назовем локально Ш-графом, если [а] лежит в Ш для любой вершины а графа Г. Если при этом класс Ш состоит из графов, изоморфных некоторому графу А, то граф Г назовем локально Д-графом.

Если вершины и, м> находятся на расстоянии I в Г, то через Ь(и, (через с (и, обозначим число вершин в пересечении Г;- +1 (и) (в пересечении Г -1 (и)) с [^]. Граф диаметра d называется дистанционно-регулярным с массивом пересечений {Ь0, ..., Ьd_ 1; с1, ..., с^, если значения Ь(и, и с (и, не зависят от выбора вершин и, м> на расстоянии I.

Сильно регулярный граф без треугольников с собственным значением 2 является четырехугольником, пятиугольником, графом Хофмана—Син-глтона, графом Гевиртца, графом Хигмена—Симса или графом Матье. Связный локально четырехугольный граф является октаэдром, а связный локально пятиугольный граф является графом икосаэдра. Дистанционно-регулярные графы, в которых окрестности вершин изоморфны графу Хофмана—Синглота или графу Гевиртца, классифицированы в [1] и [2] соответственно. В [3] изучены графы, в которых окрестности вершин изоморфны графу Хигмена—Симса.

Предложение. Пусть Г — связный вполне регулярный граф, в котором окрестности вершин изоморфны графу Хигмена—Симса. Тогда выполняется одно из следующих утверждений:

1) диаметр Г равен 2 и Г имеет параметры (486, 100, 22, 20);

2) диаметр Г равен 3, ц = 25, к3 = 2, V = 411 и Г не является антиподальным графом, или ц = 28 и либо

(1) к3 = 2 и если Г является антиподальным графом, то антиподальное частное графа Г — сильно регулярный граф с параметрами (126, 100, 78, 84);

(И) к3 = 5 и V = 381.

390

МАХНЕВ, ПАДУЧИХ

В данной работе найдены возможные автоморфизмы сильно регулярного графа с параметрами (486, 100, 22, 20).

Теорем а. Пусть Г — сильно регулярный граф с параметрами (486, 100, 22, 20), в котором окрестности вершин изоморфны графу Хигмена—Симса, О = Аи^Г), g — элемент простого порядка р из О и О = Fix(g). Тогда выполняется одно из следующих утверждений:

1) О — пустой граф, либор = 2 и а^) = 36г, либо р = 3 и а^) = 54«;

2) О является п-кликой и либо

(0р = 5, п = 1 и а^) = 90? + 10, либо (и) р = 7, п = 3 и а^) = 126/ + 84, либо (ш)р = 11, п = 2 и а^) = 308;

3) О является т-кокликой (2 < т < 36) и либо (0р = 5, т сравнимо с 1 по модулю 5 и а^) = 90? +

+ 10т, либо

(и) р = 2, т четно и а^) + 8т делится на 36;

4) О содержит геодезический 2-путь ир = 2. Следствие. Пусть Г — сильно регулярный

граф с параметрами (486, 100, 22, 20), в котором окрестности вершин изоморфны графу Хигмена— Симса. Тогда Г не является реберно-симметричным.

Лемма 1. Пусть Г является сильно регулярным графом с параметрами (V, к, А, ц) и неглавными собственными значениями г, « < 0. Если А — индуцированный регулярный подграф из Г степени й на w вершинах, то

: < й - "Ск - Л )< Г,

V - Ж

причем одно из равенств достигается тогда и только тогда, когда каждая вершина из Г — А смежна

ж (к - й) А

—^-- вершинами из А.

точно с

V - Ж

Доказательство. Это утверждение хорошо известно (см., например, § 2 из [3]).

Пусть Г является сильно регулярным графом с параметрами (486, 100, 22, 20) и неглавными собственными значениями 10 и —8 кратностей 210 и 275. Если А — индуцированный регулярный подграф из Г степени й на w вершинах, то

й - 10 < ЖС100 - й) < й + 8.

486 - ж

Поэтому число вершин в коклике (клике) не больше 36 (не больше 13). Если С является 36-ко-кликой из Г, то любая вершина из Г — С смежна точно с 8 вершинами из С.

Доказательство теоремы опирается на метод Хигмена работы с автоморфизмами сильно регулярного графа, представленный в третьей главе монографии Камерона [5]. При этом графу Г отвечает симметричная схема отношений (X, [Я0, ... ..., ^2}), где X — множество вершин графа, Я0 — отношение равенства на X, Я1 — отношение смежно-

сти в Г, Я2 — отношение смежности в дополнител-

ном графе Г . Если Р и О — первая и вторая матрицы собственных значений схемы, то

( \

1 1 1

к г и

V V - к - 1 —г - 1 —и - 1

Р =

РО = ОР = V/. Здесь V — число вершин, к, г, « — собственные значения графа Г кратностей 1, /, V — / — 1 соответственно (указанные кратности образуют первый столбец матрицы 0.

Подстановочное представление группы О = = Аи;(Г) на вершинах графа Г обычным образом дает мономиалное матричное представление у группы О в ОЬ^, С). Пространство С^ является ортогональной прямой суммой собственных у(О)-инвариантных подпространств Ж0, Щ, Ж2 матрицы смежности графа Г. Пусть х — характер представления у щ. Тогда для любого g е О получим равенство

2

Х/С 8) = ^ X ),

1 = о

где ау-^) — число точек х из Хтаких, что (х, х%) е ^.

Лемма 2. Пусть Г — сильно регулярный граф с параметрами (486, 100, 22, 20), О = Аи(Г), g — элемент простого порядка р из О и %1 — характер, полученный при проектировании у(О) на подпростран-

8 ао С g) + а1 (g)

ство размерности 210. Тогда х^) =

18

— 6, а¡(¿) = а¡(¿) для любого /, не кратного р, и 210 — х^) делится на р.

Доказательство. Рассмотрим сильно регулярный граф Г с параметрами (486, 100, 22, 20). Тогда

/ л

1 1 1

0 = 210 21 -6

V 277 -22 5 .

и значение характера, полученного при проектировании на подпространство размерности 210,

равно Х1^) = 2 10 а0 С*) + 21 а ) - 6 а2 С*). Под-

486

ставляя в эту формулу значение а2^) = V — а0^) —

8 а0 С *) + а1 (*)

- аl(g), получим х^) =

18

— 6. В част-

ности, a1(g) четно.

Два последних утверждения леммы следуют из леммы 2 [6].

Лемма 3 [7, теорема 3.2]. Пусть Г является сильно регулярным графом с параметрами (V, к, А, ц)

ОБ АВТОМОРФИЗМАХ СИЛЬНО РЕГУЛЯРНОГО ГРАФА

391

и собственными значениями к, r, —m. Еслиg — автоморфизм Г и Q = Fix(g), то |Q| < vmax{ ^- I1) .

к - r

В случае сильно регулярного графа с параметрами (486, 100, 22, 20) получим |Q| < 118.

Лемма 4. Пусть Г — граф Хигмена—Симса, g — автоморфизм Г простого порядка p и Q = Fix(g). Тогда выполняется одно из утверждений:

1) p = 2 и либо a0(g) = 0, a1(g) = 40, a2(g) = 60, либо a0(g) = 6, a1(g) = 32, a2(g) = 62 и Q является 6-кокликой, либо a0(g) = 20, a1(g) = 0, a2(g) = 80 и Q является 2-кокликовым расширением графа Пе-терсена, либо a0(g) = 30, a1(g) = 0, a2(g) = 70 и Q является дистанционно-регулярным графом с массивом пересечений {8, 7, 4; 1, 4, 8};

2) p = 3, a0(g) = 10, a1(g) = 0, a2(g) = 90 и Q является графом K5 5 с удаленным максимальным па-росочетанием;

3) p = 5 и либо a0(g) = 0, a1(g) = 0, a2(g) = 100, либо a2(g) = 0, a1(g) = 50, a2(g) = 50, либо a0(g) = 5, a1(g) = 10, a2(g) = 85 и Q — пятиугольник;

4) p = 7, ac(g) = 2, a1(g) = 14, ^(g) = 84 и Q -ребро;

5)p = 11 и ac(g) = 1, a1(g) = 22, a2(g) = 77.

Доказательство. Компьютерные вычисления в GAP.

Лемма 5. Пусть Г — сильно регулярный граф с параметрами (77, 16, 0, 4), А является регулярным подграфом из Г степени 4 на n < 20 вершинах, Xi — множество вершин из Г — А, смежных точно с i вершинами из А, xi = |Xj|. Тогда выполняется одно из следующих утверждений:

1) |А| = 12, и x0 = 1, x2 = 48, x3 = 16;

2) |А| = 13, x0 = 2, x2 = 34, x3 = 24, x4 = 4 и X0 является кокликой;

3) |А| = 14, x0 e {1, 3} и X0 является кокликой;

4) |А| = 15, либоx0 e {1, 2, 4} иX0 является кокликой, либо x0 = 2, x2 = 30, x4 = 30 и X0 является ребром;

5) |А| = 16, либо x0 e {1, 2, 3, 5} иX0 является ко-кликой, либо x0 = 3, x2 = 20, x3 = 8, x4 = 22, x5 = 8 и X0 — объединение изолированной вершины и ребра;

6) |А| = 17, либоx0 e {1, 3, 4} иX0 является кокликой, либо x0 = 2 и X0 является 2-кликой, либо x0 = 4 и X0 — объединение двух изолированных вершин и ребра;

7) |А| = 18, либо x0 e {2, 3, 4, 5, 7} и X0 является кокликой, либо x0 = 2 и X0 является ребром, либо x0 = 3 и X0 — объединение изолированной вершины и ребра, либо x0 = 5 и X0 — объединение трех изолированных вершин и ребра;

8) |А| = 18, либо x0 = 3 и X0 — объединение изолированной вершины и ребра, либо x0 = 4 и X0 — объединение двух изолированных ребер;

9) |А| = 20, либо

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком