ДОКЛАДЫ АКАДЕМИИ НАУК, 2015, том 460, № 5, с. 512-516
МАТЕМАТИКА
УДК 519.17
О ГРАФАХ, В КОТОРЫХ ОКРЕСТНОСТИ ВЕРШИН СИЛЬНО РЕГУЛЯРНЫ С ПАРАМЕТРАМИ (88, 27, 6, 9)
© 2015 г. К.С. Ефимов, член-корреспондент РАН А.А. Махнев
Поступило 04.03.2014 г.
БО1: 10.7868/80869565215050059
Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины а графа Г через Г((а) обозначим /-окрестность вершины а, т.е. подграф, индуцированный Г на множестве всех вершин, находящихся на расстоянии / от а. Подграф Г(а) = Г1(а) называется окрестностью вершины а и обозначается [а], если граф Г фиксирован. Положим а1 = {а} и [а].
Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а из Г равна к. Граф Г — вполне регулярный граф с параметрами (V, к, А, ц), если он содержит V вершин, регулярен степени к, каждое его ребро лежит точно в А треугольниках и [а] п [Ь] содержит точно ц вершин для любых двух вершин а, Ь, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
Реберно-симметричным называется граф, группа автоморфизмов которого действует транзи-тивно на множестве дуг (упорядоченных ребер).
Если вершины и, м> находятся на расстоянии / в регулярном графе Г, то через Ь(и, (через с(и, обозначим число вершин в пересечении Г; + 1(и) (пересечении Г; -1(и)) с [^]. Положим а ¡(и, = к — Ь(и, — с ¡(и, Граф Г диаметра d называется дистанционно-регулярным графом с массивом пересечений {Ь0, ... , Ьd-1, с1, ..., с^, если для любого / е {0, 1, ..., d} и любых вершин и, w, находящихся на расстоянии / в Г, имеем Ь(и, = Ь1 и с (и, = с.
Гомельский филиал Института математики Национальной академии наук Беларуси Институт математики и механики им. Н.Н. Красовского
Уральского отделения Российской Академии наук, Екатеринбург
Уральский федеральный университет им. Б.Н. Ельцина, Екатеринбург
E-mail: makhnev@imm.uran.ru
Дж. Кулен предложил задачу изучения дистанционно-регулярных графов, в которых окрестности вершин — сильно регулярные графы с неглавным собственным значением < t для данного натурального числа t. В [1] начато решение задачи Кулена для t = 3, а именно, получена редукция задачи к изучению дистанционно-регулярных графов, в которых окрестности вершин являются исключительными сильно регулярными графами с неглавным собственным значением 3. В [2] найдены параметры исключительных сильно регулярных графов с неглавным собственным значением 3. В случае А < 6 возникают следующие параметры.
Предложение 1. Пусть Г — исключительный сильно регулярный граф c неглавным собственным значением 3. Если А < 6, то Г имеет следующие параметры:
1) графы без треугольников: (162, 21, 0, 3), (176, 25, 0, 4), (210, 33, 0, 6), (266, 45, 0, 9);
2) графы с А = 1: (99, 14, 1, 2), (115, 18, 1, 3);
3) графы с А = 2: (96, 19, 2, 4), (196, 39, 2, 9), (256, 51, 2, 12);
4) графы с А = 3: (45, 12, 3, 3), (85, 20, 3, 5), (125, 28, 3, 7), (165, 36, 3, 9), (225, 48, 3, 12), (245, 52, 3, 13), (325, 68, 3, 17);
5) графы с 3 < А < 6: (196, 45, 4, 12), (21, 10, 5, 4), (111, 30, 5, 9), (169, 42, 5, 12), (88, 27, 6, 9), (144, 39, 6, 12).
Дистанционно-регулярные графы, в которых окрестности вершин принадлежат пункту 1) заключения предложения 1, изучены И.Н. Белоусовым и А.А. Махневым [3], М.М. Исаковой и А.А. Мах-невым [4], пункту 2) — А.А. Махневым [5, 6], пункту 3) — В.В. Кабановым и А.А. Махневым [7].
Ранее в [8] авторы нашли возможные автоморфизмы сильно регулярного графа с параметрами (88, 27, 6, 9). Для автоморфизма g графа Г через ai(g) обозначим число а вершин u е Г таких, что d(u, ug) = i.
Предложение 2. Пусть Г является сильно регулярным графом с параметрами (88, 27, 6, 9), g — элемент простого порядка р из Аи^Г) и А = Fix(g). Тогда п(О) с {2, 3, 5, 11} и выполняется одно из следующих утверждений:
1) А — пустой граф, либор = 2 и а^) е {6, 24, 42, 60, 78}, либор = 11 и а^) = 33;
2) р = 5, А является 3-кликой и а^) = 15;
3) р = 3, |А| = 3* + 1, 2 < * < 8 и 9 ? + 2 7 - а <*)
сравнимо с 2 по модулю 3;
4)р = 2, |А| = 2$, 2 < s< 16, 6s — а1(g) + 24 делится на 18 и если для некоторой вершины а из А имеем [а] с А, то |А| = 28 и а^) = 0.
Следствие 1. Сильно регулярные графы с параметрами (88, 27, 6, 9) и (88, 60, 41, 40) не являются реберно-симметричными.
В данной работе изучены вполне регулярные графы, в которых окрестности вершин — сильно регулярные графы с параметрами (88, 27, 6, 9).
Теорем а. Пусть Г — связный вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы с параметрами (88, 27, 6, 9). Если и — вершина графа Г, к1 = |ГДи), то ^(Г) = 3 и выполняется одно из утверждений:
1) ц = 22, к2 = 240 и 2 < к3 < 21;
2) ц = 24, к2 = 220 и 2 < к3 < 14;
3) ц = 30, к2 = 176 и 1 < к3 < 8, причем в случае к3 = 1 антиподальное частное графа Г — сильно регулярный граф с параметрами (133, 88, 57, 60).
Следствие 2. Пусть Г — граф, в котором окрестности вершин — сильно регулярные графы с параметрами (88, 27, 6, 9). Тогда Г не является дистанционно-регулярным.
Приведем некоторые вспомогательные результаты.
Лемма 1 [9, лемма 3.1]. Пусть Г — сильно регулярный граф с параметрами (V, к, А, ц). Тогда либо к = 2ц, А = ц — 1 (так называемый половинный случай), либо неглавные собственные значения п — т, —т графа Г — целые числа, где п2 = (А — ц)2 + 4(к — ц), п — А + ц = 2т и кратность п — т равна
к(т - 1)(к + т) ^ ,
---и--. Далее, если т — целое число, боль-
ц п
ше 1, то т — 1 делит к — А — 1 и
ц = А + 2 + (т - 1) -
к - А - 1, т - 1
п = т - 1 +
к - А - 1. т - 1
Лемма 2. Пусть Г — сильно регулярный граф с параметрами (V, к, А, ц), А — индуцированный подграф с N вершинами, Мребрами и степенями вершин ..., Тогда
(V - Ы) - (кЫ - 2 М) +
АМ+ц((Ы - М - £ (^
N
= Хп +
£ (' -1) -
I = 3
где XI = х((А).
Доказательство. Подсчитав число вершин в Г — А, число ребер между А и Г — А и число троек вида (а, {Ь, с}), где а е Г — А, Ь, с е А п [а], получим равенства:
г-N =
£
АМ + ц
кЫ - 2М =
N
£
и
- М - £ (2
1= 1 А
£ (2) *
Вычитая второе равенство из суммы первого и третьего, получим требуемое.
Лемма 3. Пусть Г является сильно регулярным графом с собственными значениями к, 01, 02 < 0, X, У — такие подмножества вершин из Г, что между Х и У нет ребер. Тогда выполняются следующие утверждения:
1) X ■ У <
(V - |И ) ( V - I И) (02 - 01 )2. ( 2к - 02 - 0 1 )2
( V - И )(02 - 01)
2) если X = |У|, то X <
2к - 02-I
Доказательство. Поскольку между X и У нет ребер, то по предложению 4.6.1 из [10] имеем
( V - И )( V - Щ)(02 - 01 )2
X ■ |У <
(2к - 02 - 01 )2
В случае X = |У имеем X < Лемма доказана.
(V - | И- ) ( 01 - 0 2 ) 2к - 0 2 - 0,
Если Г имеет параметры (88, 27, 6, 9), то 01 = 3, ( 88 - И )( 8 8 - ) • 3 2
02 = -6 и X ■ |У <
514
ЕФИМОВ, МАХНЕВ
Лемма 4. Пусть Г является сильно регулярным графом с параметрами (88, 27, 6, 9), А — регулярный подграф из Г степени 9 на 2п вершинах; X, — множество вершин из Г — А, смежных точно с / вершинами из А, X; = |Х/|. Тогда выполняются следующие утверждения:
1) ^XI = 88 - 2п, ^Iх, = 36п, ^ф = 18п2
лит 88 • 60, то ц = 22, 40 и кратность собственного
— 162п их0+
и х0 + ^
I -1
х, = 88 + 18п2 — 200 п;
— 72п = 18п2 — 162п, поэтому х0 + ^
I - 1
X; =
= 88 + 18п2 — 200п. Утверждение 1) доказано.
Поскольку 88 — 2п(100 — 9п) > 0, то п > 11, причем в случае п = 11 имеем 192 • 22х0 < 32 • 66(88 — х0), поэтому (361 + 27)х0 < 33 • 88 и х0 < 13.
Имеем —6 < 9 —
36 п 8 - 2 п
)г + 1
+ 1
значения п — т равна
5 • 88 • 94 15
• 104
-, про-
2) 28 < п < 63.
Доказательство. По лемме 2 имеем ^ х1 = = 88 — 2п, ^Iх, = 36п, ^(х, = 9((2п) - 9п) —
17 • 22 19 • 40 тиворечие. Утверждение 1) доказано.
Число ц четно, делит 88 • 60 и ввиду леммы 4 имеем 22 < ц < 40. Отсюда ц е {22, 24, 30, 32, 40}.
Если d(Г) > 3 и и, w, х, у, z — геодезический 4-путь в Г, то в графе [х] между [и] п [х] и [х] п И нет ребер и ввиду леммы 3 имеем 19ц < 3(88 — ц), поэтому ц < 12, противоречие. Лемма доказана.
Лемма 7. Если ц = 22, то к2 = 240 и 2 < к3 < 21.
Доказательство. Пусть ц = 22. Тогда к2 = = 240 и ввиду леммы 3 каждая вершина из Г2(и) смежна не более чем с 6 вершинами из Г3(и). По-240 • 6
этому к3 <
22
и к3 < 65. Отсюда степень каждой
вершины в Г3(и) и больше 64 и к3 <
240 • 6 24
= 60.
< 3, поэтому 22п < 5 • 88 и
п < 20. В случае п = 20 имеем 192 • 40х0 < 32 • 48(88 — —х0) и х0 < 2.
Лемма 5. Пусть Г — дистанционно-регулярный граф диаметра d > 3, в котором окрестности вершин сильно регулярны с параметрами (88, 27, 6, 9) и неглавными собственными значениями 3, —6, 00 = = к > 01 > ... > 0d — собственные значения графа Г. Тогда 01 < 11 и 0,, > —16.
Доказательство. По теореме Тервиллиге-ра [11, теорема 4.4.3] выполняются неравенства
« > Ь— = —1 — , г < Ь+ = —1 — Ь1
Поскольку г = 3, 5 = —6, Ь1 = 60, то 01 < 11 и 0d > —16. Лемма доказана.
До конца работы предполагается, что Г является связным вполне регулярным графом, в котором окрестности вершин сильно регулярны с параметрами (88, 27, 6, 9). Пусть и — вершина графа Г и к, = Г,(и).
Лемма 6. ,(Г) = 3 и ц е {22, 24, 30, 32, 40}.
Доказательство. Пусть Г — сильно регулярный граф с наименьшим собственным значением —т. По лемме 1 число т — 1 делит 60, поэтому тройка (т, п, ц) совпадает с (6, 17, 22), (7, 16, 25), (13, 17, 36) или с (16, 19, 40). Поскольку ц де-
Повторив это рассуждение несколько раз, получим, что к3 < 21.
Если Г3(и) = Й, то А = Г2(и) п Г2^) — регулярный граф степени 44 на 152 вершинах. В этом случае антиподальное частное графа Г — сильно регулярный граф с параметрами (165, 88, 49, 44), противоречие с тем, что (49 — 44)2 + 176 не является квадратом.
Лемма 8. Если ц = 24, то к2 = 220 и 2 < к3 < 14.
Доказательство. Пусть ц = 24. Тогда к2 = = 220 и ввиду леммы 3 каждая вершина из Г2(и) смежна не более чем с 5 вершинами из Г3(и). По-220 • 5
этому к3 < ——— и к3 < 45. Отсюда степень каждой
220 • 5
вершины в Г3(и) не больше 44 и к3 < = 25.
Повторив это рассуждение несколько раз, получим, что к3 < 14.
Если Г3(
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.