Локальное строение графов и их автоморфизмы тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

На правах рукописи

ПАДУЧИХ Дмитрий Викторович

003169140 Локальное строение графов и их автоморфизмы

(01.01.06 — математическая логика, алгебра и теория чисел)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

1 5 МЙ

Екатеринбург - 2008

003169140

Работа выполнена в отделе алгебры и топологии Института математики и механики УрО РАН

Научный консультант:

доктор физ -мат. наук, член-корр РАН МАХНБВ А А Официальные оппоненты:

доктор физ.-мат наук, профессор БАРАНСКИЙ В А доктор физ -мат наук, профессор КАЗАРИН Л С доктор физ -мат наук, профессор РОЖКОВ А В

Ведущая организация.

Институт математики и механики СО РАН

Защита состоится . 2008 г. в 15 ч 30 м на заседании диссертационного совета

Д 004 006 03 по защите диссертаций на соискание ученой степени доктора наук при Институте математики и механики Уральского отделения РАН по адресу 620219, Екатеринбург, ул Софьи Ковалевской, д 16

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН

Автореферат разослан

Ой 0^ 2008 г

Ученый секретарь

диссертационного совета доктор физ -мат наук

КАБАНОВ В В

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию Например, класс билдингов Титса характеризует группы лиевского типа [1] Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [2]

Пусть С? — транзитивная группа подстановок на множестве П Если подгруппа Ср группы б, состоящая из всех подстановок, фиксирующих точку р е П, имеет г орбит, то говорят, что (? является группой ранга г Пусть г = 3 и соответствующие 3 орбиты — это {р}, Л(р), Г(р) Тогда по группе <? удается построить сильно регулярный граф Г, множество вершин которого — Г2 и две вершины р, д смежны в Г, если р € Д(д)

Д Хигман (см [3], [4]) развил теорию групп ранга 3 Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множестве вершин и ребер, так и на множестве пар различных несмежных вершин Такие графы являются дистанционно транзитивными графами диаметра 2

В диссертации рассматриваются неориентированные графы без петель и кратных ребер

Граф Г диаметра <1 называется дистанционно транзитивным, если для любого г € {О, , й} и для любых вершин и, V, х, у, таких что <1(и, и) = (1{х, у) = г, существует автоморфизм д графа Г (и, V)3 = (х, у) Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3[5]

Если вершины и, то находятся на расстоянии г в Г, то через Ь,(и,ю) (через с,(и, ги)) обозначим число вершин в пересечении Гг+1(«) (в пересечении Г,^](и)) с [ад] Дистанционно регулярным графом называется граф, в котором параметры Ь,(и, хи) и с,(«, и>) не зависят от вершин и, и>, а зависят только от расстояния на котором эти вершины находятся в графе Г

Поскольку каждый дистанционно регулярный граф является вполне регулярным графом (в частности, реберно регулярным графом), то некоторые результаты об этих классах графов могут быть использованы в теории дистанционно регулярных графов

Цель работы В диссертации исследуются классы графов с различными условиями регулярности и наборами запрещенных подграфов, некоторые локально ^-графы и автоморфизмы графов

Методы исследований Основными методами исследования являются теоретико-графовые методы и методы теории конечных групп, в частности метод Хигмана приложения теории характеров к выяснению порядков автоморфизмов дистанционно регулярных графов и подграфов неподвижных точек этих автоморфизмов

Научная новизна Все основные результаты диссертации являются новыми

Теоретическая и практическая ценность. Работа носит теоретический характер Бе результаты могут быть использованы в теории групп и теории графов

Апробация работы Основные результаты диссертации неоднократно докладывались и обсуждались на алгебраическом семинаре отдела алгебры и топологии ИММ УрО РАН, а также были представлены на следующих конференциях Международная алгебраическая конференция, посвященная 100-летию со дня рождения П Г Конторовича и 70-летию Л Н Шеврина, Международная конференция «Алгебра и ее приложения», Красноярск 2002 и 2007 гг, Международная конференция «Алгебра, логика и кибернетика», Иркутск

2004, Региональная молодежная конференция ИММ УрО РАН, Екатеринбург 2002, 2005 и 2008, Международная алгебраическая конференция «Классы групп и алгебр», Гомель

2005, Международная алгебраическая конференция, посвященная 100-летию со дня рождения Фаддеева Д К , Санкт-Петербург 2007

Публикации Материал диссертации был опубликован в цикле работ, состоящем из 9 статей (все опубликованы в журналах из списка ВАК), и 12 тезисов докладов Из 9 статей 2 написаны без соавторов, 3 - тремя авторами (Кабанов В В , Махнев А А , Падучих Д В ), еще 1 - тремя авторами (Зюляркина Н Д, Махнев А А , Падучих Д В ), остальные 3 в соавторстве с Махневым А А Все совместные работы написаны в нераздельном соавторстве

Структура и объем работы. Диссертация состоит из введения, 4 глав и списка литературы, содержащего 60 названий Общий объем диссертации составляет 203 страниц

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении даны основные определения и обозначения, используемые в диссертации, обсуждается общая мотивировка решаемых задач В главе 1 получена новая оценка для числа вершин в реберно регулярных графах, улучшающая оценку из главы 1 [2] В главе 2 изучаются графы без тп-корон графы, в которых окрестности вершин — кликовые расширения решеток, графы без корон с регулярными /¿-подграфами, локальное строение графов без 3-корон с реберно регулярными ^-подграфами В главе 3 получено описание кореберно регулярных графов, в которых А принимает два значения В главе 4 с помощью метода Г Хигмана и результатов главы 3 исследуются группы автоморфизмов графа Ашбахера (графа Мура с к = 57) и сильно регулярного графа с параметрами (85,14,3,2)

Мы рассматриваем неориентированные графы без петель и кратных ребер Если а, Ь — вершины графа Г, то через й{а,Ъ) обозначается расстояние между а и 6, а через Г, (а) — подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии г от вершины а Подграф Г1(а) называется окрестностью вершины а и обозначается через [а] Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а

Регулярным графом степени к называется Граф Г, такой что для любой вершины и 6 Г выполняется |Г(и)| = к Реберно регулярным графом с параметрами (и, к, А) называется регулярный граф степени к на и вершинах, любое ребро которого лежит точно в А дреушлышках Вполне регулярным графом с параметрами {и,к,Х,ц) называется реберно регулярный граф с параметрами (у, к, А), в котором любые две вершины и, и) 6 Г на расстоянии 2 имеют ровно /х общих соседей Сильно регулярным графом с параметрами (у, к, А, ц) называется реберно регулярный граф с параметрами (и, к, А), в котором любые две несмежные вершины и, ад е Г имеют ровно ц общих соседей

В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии, и геометрии этого класса можно классифицировать Например, класс билдингов Титса характеризует группы Лиевского типа [1]

Пусть в — транзитивная группа подстановок на множестве П Если стабилизатор Ср точки р £ О имеет г орбит, то говорят, что (?—группа ранга г П>сть г = 3 и соответствующие 3 орбиты—это {р}, Г\(р), Гг(р) Если Г^р) и Г2(р) содержат разное число элементов, то на множестве О можно построить сильно регулярный граф Г Для этого положим, что точка р смежна со всеми точками из Г^), и для каждого д € (7 точка р5 смежна со всеми точками из Г1(р)9 Если вместо Г:(р) здесь взять Г2(р), то мы получим дополнительный сильно регулярный граф

Д Хигман (см [3], [4]) развил теорию групп ранга 3 Эти группы являются группами автоморфизмов сильно регулярных графов и дейсгвуют транзитивно на множестве {(и, ад) | и, VI е Г и (¿(и, и)) = г} для любого г < 2 То есть, такие графы являются дистанционно транзитивными графами диаметра 2

Граф Г диаметра <1 называется дистанционно транзитивным, если для любого г € {О, , й} группа Аи1;Г действует транзитивно на {(и, ад) | и, ад е Г и <1(и, ы) = г}

Дистанционно регулярным графом с массивом пересечений (¡>о, , С1, , с^) называется граф диаметра Л, в котором для любых вершин и, ад 6 Г, находящихся на расстоянии г, подграф Г(ги) содержит ровно Ь, вершин, находящихся на расстоянии г + 1 от и, и ровно с, вершин, находящихся на расстоянии г — 1 от и Легко понять, что условие дистанционной транзитивности влечет дистанционную регулярность графа Таким образом, результаты, полученные для дистанционно регулярных графов, применимы и к дистанционно транзитивным графам

Заметим, что сильно регулярный граф с ц > 0 является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с ё > 2—вполне регулярным графом с к = Ь0, А = & — ¿1— 1и// = сг

Пусть задан класс графов Т Мы скажем, что граф Г является локально Т-графом, если для любой вершины а е Г имеем Г(а) € Т Тогда можно поставить задачу описания локально .Г-графов Если граф Г вершинно транзитивен, то окрестности всех его вершин изоморфны, и граф Г является локально Т графом, где Т состоит из графов, изоморфных некоторому графу А В этом случае назовем Г локально А-графом В более общем случае Т может быть классом графов, удовлетворяющих некоторым условиям Например, класс связных, реберно регулярных графов—это в точности класс связных, локально регулярных графов

Определим несколько сильно регулярных графов, которые будут фигурировать в диссертации, а также являются примерами локально Л графов

Пусть M и N—конечные множества порядка тип, соответственно Два элемента из M х N будем считать смежными, если они различаются точно в одной координате Полученный граф называется m х п-решеткой, при m = п он сильно регулярен с параметрами (п2,2(п — 1),п — 2,2)

Треугольным графом Т(п) называется граф 2-подмножеств множества порядка п, в котором две вершины смежны тогда и только тогда, когда они пересекаются в точности по одной точке Граф Т(п) также сильно регулярен и имеет параметры (п(п - 1)/2,2(п — 2),п — 2,4) Окрестность каждой вершины в Г(п) изоморфна 2 х (п — 2)-решетке, те Т(п)~локально 2 х (п — 2)-решетка

Единственный сильно регулярный граф с параметрами (27,16,10,8) называется графом Шлефли Единственный сильно регулярный граф с параметрами (16,10,6,6) называется графом Клебша Граф Шлефли является локально графом Клебша

В главе 1 получена новая оценка для числа вершин в реберно регулярных графах В книге Броувера, Коэна, Ноймайера [2] доказано, что если Г — связный неполный реберно регулярный граф с параметрами (v,k,X), в котором к > 3Ьх, то диаметр Г равен 2 и выполняется неравенство

kh > (u-Jfc-l)(A-2bi + l)

Полученные в главе 1 результаты позволяют уточнить эту оценку

Пусть а, Ь — вершины графа Г Число вершин в [о] П [6] обозначим через А (а, Ь) (через ц(а,Ь)), если d(a,b) — 1 (если d(a,b) = 2), а соответствующий подграф назовем А-подграфом (¡/.-подграфом)

Пусть Г — реберно регулярный граф с параметрами (v, к, X) a bi = к — А — 1 Пара вершин и, w называется хорошей (почти хорошей), если d(u, w) = 2 и /¿(u, w) равно fc — 2&! -f 1 (равно А; — 2^ +- 2) Тройка вершин (ti, u>,z) называется хорошей (почти хорошей), если ш,г£ Г2(и) и //(it, w) + ц(и, z) не больше 2к — 4^+3 (равно 2к — 46j + 4)

Через А"ть )т„ обозначим полный n-дольный граф, с долями порядков Шь ,тп Если rrii — — шп — тп, то соответствующий граф обозначается через Кпхт Граф К\>3 называется 3-лапой

Если вершины u,w находятся на расстоянии г в Г, то через Ь,(и, w) (через с,(u, tu)) обозначим число вершин в пересечении r,+i(u) (пересечении r,_i(u)) с [гу] Заметим, что в реберно регулярном графе с параметрами (v,k, А) значение bi(u,w) не зависит от выбора ребра {и, tu} и равно к - А - 1

Теорема 1.1 Пусть Г — связный неполный реберно регулярный граф с параметрами (v, к, А) u к > 3&1 - 2 Тогда выполняется одно из следующих утверждений

(1) для любой вершины w верно неравенство |Г2(ад)|(& — 2bj + 2) < kb\;

(2) для любой вершины w верно неравенство (r2(M>)|(/;-2bi-l-2) > kbi и либо Г является реберным графом тривалентного графа без треугольников (те к = 4, \ — 1) и диаметр графа Г больше 2, либо Г является п-уголъншом, п > 5, или графом икосаэдра,

(3) Г является полным многодольным графом КГХг, 3x3 решеткой, треугольным графом Т(т), m <7, графом Клебша или графом Шлефли и для любой вершины w верно равенство |Г2(го)|(А; - 2i>i + 2) = kb\

Доказательство утверждения (2) теоремы из [16] некорректно (не доказано утверждение (3) из [16, лемма 3 3]) Следующий результат уточняет данное утверждение

Предложение 1 1 Пусть Г — гвяяниИ ррбгрио рггул?.р".ь.й сраф «иол^п^ 2 ъ лири-метрами (и, к, \) и к = ЗЬ\ + 5, 5 > —2 Тогда выполняются следующие утверждения

(1) если Г содержит такую 3-коклику Д, что любые ее две вершины образуют хорошие пары, то 5 = — 1 и Г является шестиугольником, графом икосаэдра или реберным графом тривалентного графа без треугольников, имеющим диаметр больше 2,

(2) если 5 > 0 и для некоторой вер шины ад подграф Гг(ги) содержит две вершины, образующие хорошие пары с xv, то 6 < Ь^/2 — 2,

(3) если для некоторой вершины и1 подграф Гг(ш) содержит три вершины /, и, г, образующие хорошие пары си), то 6 — —2, у — к — 1 = 2^ + 2, 6х (61 — 1) делится на 3, подграф {/, и, г} является кликой, для х 6 {/, и, г} подграф Гг(ш)ПГ2(х) содержит две вершины х', х", для различных вершин х, у £ {/, и, г) подграф [ш] П [х] П [у] содержит единственную вершину ху, граф {/и, иг, /г) является кликой и |[и)] — ([/] и [и] и [<?])| = 4,

(4) если для некоторой вершины гл подграф Г2(ш) содержит четыре вершины {и, г, /,д}, образующие хорошие пары сы, тоЬ\ =6, к = 16, А = 9, V = 31, подграф {и, г, /, <?} является кликой и р{ш,у) > 7 для любой вершины у из Гг(ш) — {и, г, /, д}

Следующий пример показывает, что для графа Г с к < 36] —3 и его вершины ш подграф Г2(ш) может содержать к вершин, образующих хорошие пары с и

Пример Пусть Дп — граф, вершинами которого являются 4-циклы из 5„ и два цикла а, Ь смежны тогда и только тогда, когда аЪ является 5-циклом Тогда Д5 является реберно регулярным графом диаметра 3 с параметрами (30,12,6) и каждая вершина из [(1432)] образует хорошую пару с (1234)

Имеется немного результатов о единственности сильно регулярного графа с данными параметрами (у, к, А, В качестве следствия теоремы 11 получена единственность некоторых реберно регулярных графов с данными параметрами (и, к, А)

Следствие 1.1. Пусть Г — реберно регулярный граф, имеющий те же параметры (у, к, А), что и один из следующих графов полный многодольный граф КГХ1, 3x3 решетка, треугольный граф Т(т), т < 7, граф Клебша или граф Шлефли Тогда Г изоморфен соответствующему графу

Глава 2 посвящена изучению графов без т-корон

Граф К^ д(з с т долями порядка 1 называется т-короной При тп — 1 и т — 2 будем называть т-корону Ъ-лапой и короной, соответственно Понятно, что т-корона получается из (т.—1)-короны добавлением одной вершины, смежной со всеми остальными вершинами Поэтому граф без т-корон—это в точности граф локально без (т — 1)-корон

Пусть V является п-мерным векторным пространством над полем С^(^) Два т-мерных подпространства из V будем считать смежными, если они пересекаются по (т— 1)-мерночу подпространству Граф на множестве всех т-мерных подпространств V с такой смежностью называется графом Грассмана и обозначается через т) При т = 2 граф Грассмана сильно регулярен Граф Грассмана т) не содержит (индуцированных) корон

В параграфе 2 1 изучаются сильно регулярные графы, у которых окрестность каждой вершины является кликовым /3-расширением р х д-решетки Интерес к таким графам был

вызван тем, что при изучении графов без корон, в которых подграфы являются регулярными графами заданной положительной степени (см. [7], [21]) наибольшие трудности вызвал случай, когда окрестность каждой вершины является кликовым ^-расширением р х д-решетки

Теорема 2.1. Пусть Г — сильно регулярный граф с отрицательным собственным значением —га, в котором окрестность каждой вершины является кликовым 0-расширением р х q-решетки, 2 < р < q Тогда выполняются следующие утверждения

(1) число вершин в максимальной клике L графа Г равно 1 + pq или 1 -f рр, и (L, В) является (v, b, г, к, Х)-схемой, где В — множество сингулярных прямых графа Г, лежащих в L, к — р 4- 1, А = 1, и тройка (v,b,r) равна (1 + Pq, (1 + Pq)q/{Р + 1), g) или (1+/?р, (1+Pp)p/(P+I),p), соответственно, в частности, Р+1 делитр(р — 1) uq(q — 1),

(2) если р < q, то число (1 + Pq)-MUK в графе Г равно pv/(l + Pq), и 1 + pq делит р(р—l)(/i-p+l), а число (1+Рр)-клик равно qv/(l + fip), и 1+Рр делит q(q — l)(/i — <Z + 1), если p = q, mol + f!p делит 2(р - t)(p — 1,Р + 1)(р + 1, /? - 1),

(3) для двух несмежных вершин а, Ь любая строка (любой столбец) решетки, отвечающей [а], содержит 0 или Р + 1 вершин из [Ь], и ц — t(p + 1), где Р + 1 < t < р,

(4) если t = Р + 1, то [а] П [Ь] является t х t-решеткой, и Г является треугольным графом Т(т) (т > А), графом J(10,5) или графом Гроссмана Jt-i(n, 2), n > 4,

(5) если т = р — и, то t < р — и, причем равенство достигается лишь при и = 0, в частности, t ф р — 1, и если t = р - 2, то т = р — 1, (2(3 + 1)(р - 2) = P(q - 1), и 0 + 1 делит 2(р — 1, q),

(6) если t — p, то т= р, и

(г) Г является псевдогеометрическим графом для pGp+\{Pq,p — 1), и (pq + р — /3 —

1)08 + 1) делит р(р - 1 )Pq{Pq + 1),

(гг) если р < q, то Г является геометрическим графом, и каждый fi-подграф в графе прямых данной геометрии является объединением непересекающихся (Р + 1) х (/? + 1)-решеток, /9 + 1 делит q — 1, ирр+1 делит q(q — l)(Pq + 1), (ггг) если р = q, то (Р + I)2 делит р2{рР + 1)

Заметим, что если Г — псевдогеометрический граф для рОг{р,р - 1), являющийся локально р х р-графом, то Г — дополнительный граф для 4 х 4-решетки в случае р = 3 и граф J(8,4) в случае р = 4 (отсюда следует изоморфизм 7(8,4) и дополнительного графа для графа Грассмана J2(4,2))

В теореме 2 из [8] была получена классификация сильно регулярных локально р х q-графов с2<р<9ир<б Следующая теорема распространяет этот результат на графы, в которых окрестности вершин являются кликовыми расширениями р х q-решетки

Теорема 2 2 Пусть Г — сильно регулярный граф, в котором окрестность каждой вершины является кликовым Р-расширением р х q-решетки, 2 < р < q Если р < 6, то выполняется одно из следующих утверждений

(1) Р = р — 1, и Г является графом Грассмана Jp_i(n,2),

(2) р = р — 2, и либо Г имеет параметры второй окрестности вершины в графе Грассмана 7p_i(4,2), либо является точечным графом частичной геометрии pGp-i((p —

2)q,p~ 1), р - 1 делит q — 1,

(3) Р = 2, и Г является псевдогеометрическим графом для частичной геометрии рСз(12,5),

(4) 0 = 1, и Г является либо треугольным графом 7'(<у + 2), ли5о дополнительным графом дляАхА-решетки, графом ,7(8,4) или /(10,5), либо псевдогеометрическим графом для частичном грпиегпгнт г»/?2''6,

В параграфе 2 2 изучаются графы Тервиллигера без корон и графы без 3-коклик с регулярными /¿-подграфами (см также [21])

Пусть ах — шар радиуса 1 с центром а Для подграфа А графа Г через Ах обозначим С\аел Граф Г назовем слабо редуцированным, если из равенства а1- = Ьх следует а — Ъ Граф Г назовем редуцированным, если из включения а-1 С 6х следует а = 6 Через Гх обозначим подграф на множестве всех вершин а таких, что ах = Г

М Нумата [9) получил классификацию графов без корон, в которых /¿-подграфы являются изоморфными реберно регулярными графами диаметра 2 (естественно, не имеющими 3-лап) В связи с этим результатом представляет интерес изучение графов, в которых каждый /¿-подграф является реберно регулярным графом без 3-лап с заданными параметрами К*', А')

В статье В В Кабанова [7] было получено следующее обобщение результата Нуматы, опирающееся на более ранние работы А А Махнева и В В Кабанова

Связный редуцированный граф без корон, содержащий 3-коклику, в котором ¡¿-подграфы регулярны заданной степени а > 0 и имеют диаметр 2, является графом Грассмана, графом Джонсона или его частным, локально треугольным графом или графом Госсета

Важным этапом в доказательстве этого результата стала лемма 2 1 [7], в которой доказано, что слабо редуцированный граф без 3-лап, содержащий 3-коклику, в котором ц-подграфы регулярны заданной положительной степени, является редуцированным

Предложение 2.1 Если Г — связный слабо редуцированный граф без 3-коклик, в котором ¡¿-подграфы регулярны степени а > О, то Г является редуцированным графом или пятиугольной пирамидой

В статье А А Махнева и В В Кабанова [10] было доказано, что если Г—связный граф Тервиллигера без 3-лап, то либо Г является кликовым расширением графа икосаэдра, либо подграф, индуцированный на множестве всех вершин из Г — Гх с некликовыми окрестностями, является кликовым расширением пустого графа, клики или графа с ц = 1

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

(1) Г не содержит 3-коклик и является кликовым расширением 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды,

(2) Г не содержит 3-лап, но содержит 3-коклику, диаметр Г больше 2, и либо (г) Г является кликовым расширением графа икосаэдра, либо

(и) Г' является кликой, и Г является кликовым расширением графа А, где Д содержит 5-клику и 5 или <5-1 вершин степени 1, смежных с различными вершинами клики, либо

(ш) Г' является кликовым расширением графа с ц, = 1,

(3) Г содержит 3-лапу, р. = 1, и окрестность любой вершины из Г состоит из изолированных клик

Следствие 2 1. Пусть Г — связный граф, в котором окрестности вершин являются регулярными графами Тервиллигера диаметра 2 Если окрестность некоторой вершины не содержит корон и 5-коклик, то либо Г является кликовым расширением пяти-уголъника или графа икосаэдра, либо Г — локально граф Петерсена, т е граф Т(7), граф Конвея-Смитп на 63 вершинах диаметра 4 (это антиподалъное 3-накрытие Т(7)) или граф Доро на 65 вершинах диаметра 3

Следующая теорема является аналогом результата, полученного в статье В В Кабанова [7] для редуцированных графов без 3-коклик

Теорема 2.4 Пусть Г — связный редуцированный граф без 3-коклик, в котором каждый ц-подграф регулярен заданной степени а > 0 Тогда Г сильно регулярен, или степень любой вершины из Г равна к или к — 1, подграф Г' на вершинах степени к является октаэдром, подграф на Г — Г' является 6-кликой и каждая вершина из Г — Г' смежна с 3-кликой из Г'

Обратно, если Г — сильно регулярный граф без 3-коклик с параметрами (и, к, А, ¡л), то каждый /¿-подграф регулярен степени а = 2А + 2 - к

Следствие 2 2 Пусть Г — связный редуцированный граф без корон, в котором каждый ц-подграф реберно регулярен с заданными параметрами (и', к', А') и имеет диаметр 2 Тогда выполняется одно из следующих утверждений

(1) А' = 0, и Г совпадает с октаэдром или треугольным графом Т(5),

(2) А' > О, Г не содержит 3-коклик и является сильно регулярным графом с параметрами ((я2 + З*)2, («2 + 2$- 1)(з2 + Зз + 1), (в + 2)(в3 + 2в2 - 1), (з2 + 2в)(з2 + 2з- 1)),

(3) А' > О, Г содержит 3-коклику и является графом Грассмана, графом Джонсона или его частным, локально треугольным графом или графом Госсета

В параграфе 2 3 изучаются Графы без 3-корон с реберно регулярными /¿-подграфами А именно, с помощью классификации графов без корон с регулярными /¿-подграфами диаметра 2 степени а > О (см выше) в статье [32] были получены следующие две теоремы

Теорема 2.5 Пусть Г — связный граф без 3-корон, в котором любой ц-подграф А состоит из у' > 1 вершин, и |Д(:г) П Д(у)| = А' > 0 для любых смежных вершин х,у 6 Д Если окрестность некоторой вершины из Г является графом Тервиллигера, то Г является либо кликовым (А'+ 2)-расширением т х п-решетки, либо графом Тервиллигера одного из следующих типов

(1) кликовое расширение 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды,

(2) кликовое расширение графа Д, где А является объединением ¿-клики и 6 или й — 1 вершин степени 1, смежных с различными вершинами этой клики,

(3) кликовое расширение графа икосаэдра или графа без 3-лап с ц — 1

Теорема 2 6 Пусть Г — сеязпъш граф без 3-корон, в котором каждый ц-подграф А является реберно регулярным графом с параметрами (г/, к', А') и окрестностями вершин диаметра 2 Если 0 < А' < к' — 1, то либо окрестности вершин в Г являются сильно регулярными графами без 3-коклик, либо Г — локально А-граф, где А — один из следующих графов

(1) треугольный граф Т(п) (п > 6) или граф Шлефли,

(2) частное графа Джонсона J(10,5) или половинный граф свернутого 10-куба,

(3) граф Грассмана J2• (п, 2), где п > 4

D параграфах 2 4 и 2 5 доказано несуществование локально орграфов и графов, являющихся локально половинным графом свернутого 10-куба (см [31], [35]) Таким образом, можно исключить случай (2) из теоремы 2 6

В параграфе 2 6 доказано, что связные компоненты /¿-подграфов в локально JQ(n, 2) графах являются графами Джонсона J(6, 3) или дополнительными графами к 4 х 4-решетке В частности, q = 2 См также [32]

Графы знакопеременных и квадратичных форм над полем порядка 2 являются вполне регулярными локально Грассмановыми графами с ¡J, = 20 (см [11])

В параграфе 2 7 доказано, что если Г — вполне регулярный локально ^(п, 2) граф с ц = 16, то п = 4 и |Г| = 72 (см [33])

Следствие 2 4 Пусть Г — связный граф без 3-корон, в котором каждый ц-подграф Д является связным реберно регулярным графом с параметрами (г/, к', А') и окрестностями вершин диаметра 2 Если 0 < Л' < к' — 1, то выполняется одно из следующих утверждений _

(1) либо Г является графом Шлефли или графом Госсета, либо граф Г имеет параметры ((г2 -f Зг)2, г3 + Зг2 + г, 0, г2 + г) для некоторого г > 1,

(2) каждый fi-подграф является октаэдром, и Г — половинный граф ректаграфа с Сз = 3, являющийся локально треугольным графом,

(3) Г является локально Грассмановым графом, и либо

(г) ц = 16, п = 4, и Г — антиподальный граф диаметра 3 на 72 вершинах, либо (гг) ц = 20, и если для любой вершины а графа Г граф Г ¡(а) является регулярным степени 15 2"'1 — 105, то Г имеет накрытие, являющееся графом Alt(n, 2) знакопеременных форм или графом Quad(n — 1,2) квадратичных форм

В параграфе 2 8 получено описание вполне регулярных локально GQ(4,2) графов См статью [17]

Обобщенным четырехугольником порядка (s, t) называется частичная геометрия pG\{s, í) То есть, каждая прямая содержит s + 1 точку, каждая точка лежит на t +1 прямой, и для любой прямой L и точки х £ L существует единственная точка у € L, коллинеарная с х Обобщенный четырехугольник порядка (s, t) обозначается через GQ(s, t) Геометрия GQ(s, t) однозначно восстанавливается по своему точечному графу Мы будем обозначать точечный граф обобщенного четырехугольника порядка (s, t) также через GQ(s, t)

Нетрудно понять, что граф GQ(s,t) не содержит корон Следовательно, локально GQ(s, t) графы не содержат 3-корон Так как /i-подграфы в GQ(s, t) являются (í + 1)-кокликами, то в локально GQ(s,t) графах /¿-подграфы не содержат треугольников и, следовательно, не удовлетворяют условиям теорем 2 5 и 2 6 Следующая теорема дает описание вполне регулярных локально GQ(4,2) графов

Теорема 2.11 Вполне регулярный локально СС}(4,2)-граф является одним из следующих графов

(1) единственный сильно регулярный локально GQ{4,2)-граф с параметрами (126,45,12, 18),

(2) единственный дистанционно регулярный локально GQ(4,2)-граф на 378 вершинах с массивом пересечений (45,32,12,1,1,6,32,45) (это i-накрытие графа из пункта (1)^

В главе 3 изучаются кореберно регулярные графы с ц — 2, у которых каждое ребро содержится в Ai или Л2 треугольниках. Сделаны уточнения результатов [12] См работу [26]

Подграфы неподвижных точек автоморфизмов сильно регулярного графа с малыми значениями параметров Аид имеют жестко заданное строение Так, непустой подграф неподвижных точек автоморфизма графа Мура сам является графом Мура или звездой (см лемму 1 из [13]) Для изучения подграфов неподвижных точек автоморфизмов сильно регулярных графов с ц = 2 может быть полезна следующая теорема

Теорема 3 1 Пусть Д — граф, в котором каждое ребро содержится в Ai или А2 треугольниках, и подграф [и] П [ш] является 2-кокликой для любых двух несмежных вершин и, w Тогда либо Д — сильно регулярный граф, либо выполняются следующие утверждения

(1) граф Д регулярен степени к, окрестность любой вершины в Д является объединением х изолированных (Ai + 1)-клик и у изолированных (Л2 + 1)-клик, число (Á¡ + 2)-клик в Д равно

v(2 (у -k-l)-k(k~Á2~ 1)) (Ai + l)(AI + 2)(Aa-A1) '

(2) для связной компоненты Е графа Л1, определенного на множестве вершин графа Д, в котором вершины а,Ь смежны, только если они смежны в А и |[в] П [Ь]| = Ai, выполняются утверждения.

(г) если х > 1, то Е является вполне регулярным графом с параметрами (vj¡, + l),Ai,2),

(и) если Е содержит геодезический A-путь abcde, то х > 4, и для и 6 ЕЛ[а]—Е(а) имеем dz(a, и) > 4,

(ггг) если х = 2, то Е является (Ai + 2) х (Ai + 2)-решеткой, а если х = 3, то Е является графом диаметра 3,

(гу) если Е — сильно регулярный граф, то любая связная компонента графа Л1 изоморфна Е, граф Д*, определенный на множестве {Еь , Е,} связных компонент графа Л1, s = v/v-£, в котором вершины Е, и Ej смежны, если j ф г, и некоторая вершина из Е, смежна с единственной вершиной из £j, является сильно регулярным с параметрами (в, у{А2 + 1), А2 + 2(vz - ks - 1), 2ve),

(3) если у — то либо i=l иД является (At + 2) х (А2 + 2)-решеткой, либо х > 1 и выполняются утверждения

(г) множество вершин графа Д можно представить в виде разбиения на t клик Ci, ,Ct порядка А2 + 2, где t = и/(Аг + 2), и граф Д°, определенный на множестве {Сь , Ct}, в котором клики С, и С, смежны, если j ф г и некоторая вершина из С, смежна с вершиной из С}, является частичным четырехугольником с параметрами (í,fc-A2-l,Ab2A2 + 4),

(гг) граф Л1 является дистанционно регулярным графом диаметра 4 с массивом пересечений {x(Ai + 1), (ж - l)(Ai + 1),2(А2 + 1), 1,1,2, (х - l)(Ai + l),x(Ai + 1)}, и если Ai > 0, то Aj -I- 4x(Ai + 1) является квадратом

Заметим, что для связной компоненты Q графа Л2, определенного на множестве вершин графа Д, в котором вершины а, Ъ смежны, только если они смежны в Д и |[a]fl[¿]| = Л2,

выполняются утверждения, аналогичные сформулированным в теореме В случае х = 1 выполняется аналог утверждения (3), полученный заменой Л2) на (х, Ai) и обратно

Для четного натуоального числам) чррез MP(ui\ обгинячим клягг прбрпнп пргуттяпныг графов Г с параметрами &i = Зш/2 — 3, к = w2 - Зш/2, А = w2 - 3oj4-2, v = cj2, содержащих пару непересекающихся подграфов Hi и Пг, изоморфных Кшхш/2, причем любая вершина из fij (из Пг) несмежна с единственной вершиной в каждой доле из ГЬ (из fii), и для любого ребра {d, е} из подграф Г — (d1- U ех) является ребром из П2 Любой граф из МР{2) состоит из двух изолированных ребер, а граф из МР(4) изоморфен графу Клебша (сильно регулярному графу с параметрами (16,10,6,6)) По аналогии с листом Мебиуса, т-трапом Мебиуса назовем граф, полученный из графа вершин и ребер боковой поверхности m-призмы, разрезанием по боковому ребру, переворачиванием правой стороны на 180° и склеивания

В теореме 14 3 из (2] доказано, что если Г — связный реберно регулярный граф с параметрами (v, к, А), в котором А > к +1/2 — у/2к + 2 (равносильно к > fci(i>i + 3)/2 + 1), то Г — дополнительный граф для сильно регулярного графа с р < 2 В следствии 2 из [12) (опирающемся на теорему 2 [12]) получено описание связных, реберно регулярных графов с к > bi(bi + 3)/2 - 2 Однако, доказательство теоремы 2 в ¡12) некорректно (ошибка в доказательстве леммы 27), поэтому теорема 2 и следствие 2 из [12] нуждаются в уточнении Скорректированная формулировка теоремы 2 из ¡12] имеет вид

Теорема 3 2 Пусть Г — связный реберно регулярный граф с параметрами (v,k, А), в котором ß(u, tu) = А или к — 7 для любых вершин и, w с d(u, w) = 2 Если для каждого ребра {a, b} подграф Г — (a1 U 6х) состоит из двух смежных вершин, то выполняется одно из следующих утверждений

(1) диаметр Г больше 2, и Г получается удалением из полного двудольного графа Kk+i,fc+i максимального паросочетания,

(2) граф Г сильно регулярен,

(3) для вершины и 6 Г подграф {w 6 Гг(и) | ß{u,w) = к — 7} является полным многодольным графом Kyxs, s = bi + 2 — 7, 1 < 7 < bi, и для графа Л1, определенного на множестве вершин графа Г, е котором две вершины а, Ь смежны, только если они несмежны в Г и д(а, Ь) = А, верны утверждения

(г) если у = 1, то Л1 является дистанционно регулярным графом диаметра 4 с массивом пересечений {x,x~l,2s,l,l,2,x — l,x}, где х = + 2 — ys, множество вершин графа Г можно представить в виде разбиения на t ко клик Си , Ct (антиподальных классов) порядка s+1, где t = и/(s-|-l), и антиподалъное частное Г' является частичным четырехугольником с параметрами (t, bt + 2 — s, 0,2s + 2),

(11) если Л1 имеет связную компоненту диаметра 2, то каждая связная компонента графа Ai является сильно регулярным графом с параметрами ((х2 + х + 2)/2, х, 0,2), где х = 61 +2—ys = i2 + l для некоторого t не кратного 4, и граф Г*, определенный на множестве {Si, , £;} связных компонент графа Л1,1 = 2v/(x2+x+2), в котором вершины Е, и Sj, смежны, если j ф г и некоторая вершина из Е, смежна с единственной вершиной из £j, является сильно регулярным с параметрами (l,rs, s — 1 + х(х — 1)/2, х2 + х + 2)

Если выполняется утверждение (3i) и Г' является полным двудольным графом, то Г е МР{ш), и > 6, bi = Зш/2 - 3, k = ш2 - Зш/2, s = ш/2 - 1 и v = w2 Скорректированная формулировка следствия 2 из [12J имеет вид

Следствие 3.1 Пусть Г — неполный связный реберно регулярный граф с параметрами (и, к, А) Если А > к 4-1/2 — \/2к + 8 (равносильно 2к > 6f + 3&i — 4), то

(1) граф Г является п-уголъником, п>6, тривалентным графом без треугольников, реберным графом тривалентного графа без треугольников, графом икосаэдра, треугольным графом Т(6) или графом Клебша (во всех этих графах Ьг < 3), или

(2) граф Г является дополнительным к сильно регулярному графу с р. <2, или

(3) либо граф Г принадлежит МР(ш), и — 6,8, либо для графа Д = Г выполняется одно из следующих утверждений

(г) граф Д разбивается дополнительными графами для А-трапов Мебиуса Фь , ФГ) где г — v/S и граф А* на множестве вершин {Фъ , Фг}, 0 котором вершины Ф, и Ф_, смежны, если некоторая вершина из Ф, смежна с вершиной из Ф3 в графе А, является сильно регулярным с параметрами [v/S, t2 — 9,6,16), ut = \2 или 36,

(и) граф А можно представить в виде разбиения на 3 х 3-решеток Hi, , ils, где s = ti/9, и граф А° на множестве вершин {Hi, , f!s}, в котором вершины Г2, и Qj смежны, если некоторая вершина из flt смежна с вершиной из в графе А, является сильно регулярным с параметрами (w/9, t2 — 7,8,18), и t = 7,14 или 28,

(ш) граф Л на множестве вершин графа А, в котором вершины и, w смежны, если они смежны в А и |Д(м) П Д(м)| = 0, — дистанционно регулярный граф диаметра 4 либо имеющий массив пересечений {136,135,6,1,1,

2,135,136} и являющийся антиподальным 4-накрытием сильно регулярного графа с параметрами (2432,136,0,8), либо имеющий массив пересечений {х,х — 1,4,1,1,2,х — 1,®} и являющийся антиподальным 3-накрытием сильно регулярного графа с параметрами ((ж + 2) (х + 3)/6, х, 0,6)

В случае k = (i>f+3f>i)/2 в заключении следствия остаются n-угольник, граф икосаэдра, граф из МР(6) и дистанционно регулярный граф диаметра 4 с массивом пересечений {х, х — 1,4,1,1,2, х - 1, х}, являющийся антиподальным 3-накрытием сильно регулярного графа с параметрами ((х + 2){х 4- 3)/6,х,0,6), подтверждающие точность границы к > bi(bi 4- 3)/2, дающей сильную регулярность графа

Глава 4 посвящена изучению автоморфизмов дистанционно регулярных графов В монографии П Камерона [14] представлен метод Г Хигмана, который дает необходимое условие существования автоморфизма дистанционно регулярного графа

Пусть Г — дистанционно регулярный граф диаметра d Подстановочное представление группы G = Aut Г на вершинах графа Г дает матричное представление ф группы G в GL(v, С) Пространство С является ортогональной прямой суммой собственных подпространств Wo © • © Wd матрицы смежности А графа Г Для любого g 6 G матрица ф(д) перестановочна с А, поэтому подпространство Wt является ^(С)-инвариантным Пусть х.~характер представления, полученного ограничением тр на W, Тогда

i

Хг(д) = ]С<2.л(э)>

j=0

где aj(ff)—число вершин х из Г, таких что d(x,xs) — j, a Qt] зависят от параметров Г

Поскольку значения характеров — целые алгебраические числа, то в случае, когда значения QtJ рациональны, хЛв) является целым числом Отсюда получаем условие дели-

мости для а:(д), j = 1, ,d С помощью этого условия были получены новые ограничения для групп автоморфизмов сильно регулярных графов с параметрами (85,14,3,2) (см |36]) и (3250, 57,0,1) (см |29П Эти результаты являются чагткю грпии nafinr mv«m»«-ных изучению групп автоморфизмов сильно регулярных графов с малыми значениями А и ¡i

В параграфе 4 1 получены результаты о группе автоморфизмов сильно регулярного графа с параметрами (85,14,3,2)

Наименьшим примером сильно регулярного графа с параметрами (t),fc,3,2) является 5 х 5-решетка, имеющая параметры (25,8,3,2) Следующим набором параметров с А = 3 и (I = 2, для которого возможно существование сильно регулярного графа, является (85,14,3,2)

Теорема 4 1 Пусть Г—сильно регулярный граф с параметрами (85,14,3,2) Тогда для любого автоморфизма g из Aut Г простого порядка р выполняется одно из следующих утверждений

(1) р € {5,17} и Fix g— пустой граф,

(2) р = 7 и Fix g является l-ыикой, или р = 5 u Fix g является 5-кликой,

(3) р — 3, Fix j является четырехугольником или2х5-решеткой, и в последнем случае для шести вершин из Fixg их окрестности содержат точно две максимальных S-клики,

(4) р = 2, окрестность каждой вершины из Fixg связна, Fixg является объединением ip изолированных вершин и ф изолированных треугольников, причем либо ф = 1 и ip & {4,6}, либо ф = 0 и ~ 5

В параграфе 4 2 изучается группа автоморфизмов графа Мура степени 57 (графа Ашбахера)

Для регулярного графа степени к и диаметра d ua v вершинах выполняется неравенство

u<l + fc + fc(fc-l) + + k(k-l)d~1

Графы, для которых достигается равенство, называются графами Мура Простейшим примером графа Мура служит (2d + 1)-угольник

Дамерелл в [6] доказал, что граф Мура степени к > 3 имеет диаметр 2 В этом случае v = fc2 +1, граф сильно регулярен сА = 0и/х = 1, а степень к равна 3 {граф Петерсена), 7 (граф Хофмана-Синглтона) или 57 Существование графа Мура степени fc = 57 неизвестно Ашбахер в статье [15] показал, что граф Мура с fc = 57 не является графом ранга 3 Мы будем называть граф Мура с fc = 57 графом Ашбахера

Пусть Г—граф Ашбахера, G = Aut Г Ранее в работе [13| было доказано, что если G содержит инволюцию t, то G = 0(G)(t), и Fixi является 56-звездой Приведенная ниже теорема не делает предположений о существовании инволюции

Теорема 4.2 Пусть Г— граф Ашбахера и G = Aut Г Тогда либо

(1) G содержит инволюцию t, и либо 0(G) = Р -силовская Ь-подгруппа из G порядка 125, |[Р, i]| = 25, Z(P) действует полурегулярно на Г, Fix(CP(t))— граф Хофмана-Синглтона, и Р содержит 25 подгрупп U, порядка 5, имеющих пятиугольник в качестве подграфа неподвижных точек, либо G = Y{t) х X, Y—циклическая группа, инвертируемая t, |У| делит 7,19,55, |АГ| делит 7,25,27 или 55, и если X ф 1, то верно одно из утверждений

(г) FiхХ-звезда, |Х| = 7«Г=1,

(и) FixX— пятиугольник, [У| делит 5, либо Fixх—граф Хофмана-Синглтона для некоторого элемента х порядка 5 из X и \Х (ж)| е {5,11}, либо Fix ж = FixX для любого неединичного элемента х из X и [Х( делит 55,

(иг) FixX —граф Петерсена, делит 27, |У| делит 5 и если Y ф \, то FixY является пустым графом,

(iv) FixX —граф Хофмана-Синглтона, |ЛГ| делит 25, )У| делит 5 или 7, и если |У| = 5, то Fix У является пустым графом или пятиугольником, а если |У] = 7, то Fix У является звездой на 51 или на 16 вершинах либо

(2) |<2| нечетен и верно одно из утверждений (г) 19 делит \G\, G = Ga для некоторой вершины а, и G— подгруппа из группы Фробениуса порядка 3219,

(гг) 13 делит |G|, либо G—подгруппа из циклической группы порядка 65 и каждый неединичный элемент из G действует без неподвижных точек на Г, либо G— группа Фробениуса порядка 39,

(ггг) 11 делит |G|, G—расширение циклической группы порядка 11 с помощью элементарной абелевой группы U порядка, делящего 25,

(гг>) 7 делит |G|, либо G—подгруппа прямого произведения циклической группы порядка 7 и элементарной абелевой группы U порядка, делящего 25, в случае U ф\ подграф Fix U является графом Хофмана-Синглтона, либо G—группа Фробениуса порядка 21,

(v) ж(G) С {3,5}, либо |G| делит 54, либо G—подгруппа из прямого произведения группы порядка 5 и группы порядка 27, либо G—группа Фробениуса порядка 75 или 543, либо \Z(G)I = 5 и G/Z(G)—группа Фробениуса порядка 75

Непустой подграф неподвижных точек подгруппы из группы автоморфизмов графа Мура является графом Мура или звездой При доказательстве теоремы 4 2 используется следующий результат о подграфах неподвижных точек автоморфизмов графа Ашбахера

Предложение 4 1 Пусть Г—граф Ашбахера, д— автоморфизм простого порядка р графа Г, П = Fixp Тогда выполняется одно из утверждений

(1) П— пустой граф и р 6 {5,13},

(2) fi—звезда на ш вершинах и либо w — 1 и р = 19, либо ы = 56 и р = 2, либо w = 58 — 7у для некоторого у < 8 и р = 7,

(3) П— пятиугольник и р G {5,11},

(4) О,—граф Петерсена up-- Ъ,

(5) О,—граф Хофмана-Синглтона и р = 5

ЛИТЕРАТУРА

1 Ti«> J Buildings ш Spherical Туре <ш<1 iiuue BN-pdiib, Spimgei Leciute Nuira ш Mathematics, v 386

2 Brouwer A E , Cohen A M , Neumaier A Distance-regular graphs // Berlm etc SpringerVerlag - 1989

3 Higman D G Finite permutation groups of rank 3 // Math Z , 1964, v 86, 145-156

4 Higman D G Primitive rank 3 groups with a prime subdegree // Math Z , 1966, v 91, 70-86

5 Präger С Б , Solcher L H Low rank representations and graphs for sporadic groups Lecture senes 8 Cambridge, University press, 1997

6 Damerell R M On Moore graphs // Math Proc Cambr Phil Soc , 74(1973), 227-236

7 Кабанов В В О графах без корон с регулярными /¿-подграфами // Матем заметки, 2000, т 67, №, 874-881

8 Зюляркина Н Д , Махнев А А О сильно регулярных локально решетчатых графах // Дискрет матем 1993, т 5, 145-150

9 Numata М A characterization of Grassman and Johnson graphs //J Comb Theory, Ser B, 1990, v 48, 178-190

10 Кабанов В В , Махнев А А Графы без 3-лап с равномощными /¿-подграфами // Изв Урал гос ун-та, Математика и механика, 1998, №10, 44-68

11 Munemasa А , Pasechnik D V , Shpectorov S V A local characterization of the graphs of alternating forms and the graphs of quadratic forms over GF(2) // Finite Geometry and Comb London Math Soc Lecture Note Senes 191 Cambr Univ Press 1993, 303-317

12 Махнев А А О сильной регулярности некоторых реберно регулярных графов // Известия РАН, серия матем 2004, т 68, JV4, 159-172

13 Махнев А А , Падучих Д В Об автоморфизмах графа Ашбахера // Алгебра и логика 2001, т 40, №2, 125-134

14 Cameron Р Permutation Groups, London Math Soc Student Texts 45, Cambridge Umv Press -1999

15 Aschbacher M The nonexistence of rank three permutation groups of degree 3250 and subdegree 57 // J Algebra 1971, v 19, №3, 538-540

16 Махнев A A , Веденев A A , Кузнецов A H , Носов В В О хороших парах в реберно регулярных графах // Дискрет матем 2003, т 15, 77-97

Работы автора по теме диссертации

17 Махнев А А , Падучих Д В Расширения GQ(4,2), вполне регулярный случай // Дискрет матем 2001, т 13, №3, 91-109

18 Paduchikh D V Non-existence of locally 7(10,5)-graphs // Укр матем конгресс 2001 Тез докл Киев, секция 1, с 40

19 Кабанов В В , Махнев А А , Падучих Д В О графах без корон с регулярными fi-подграфами // Труды 33-й молодежной конф ИММ УрО РАН Екатеринбург 2002, 25-28

20 Кабанов В В , Махнев А А , Падучих Д В Локальное строение графов без 3-корон с реберно регулярными /(-подграфами // Международная конф Алгебра и ее приложения, Красноярск 2002, 55-57

21 Кабанов В В , Махнев А А , Падучих Д В О графах без корон с регулярными /1-подграфами, II // Матем заметки 2003, т 74, 396-406

22 Кабанов В В , Махнев А А , Падучих Д В О локально решетчатых подграфах в графах Грассмана // Алгебра, логика и кибернетика Тез докл Иркутск 2004, 149-151

23 Махнев А А , Падучих Д В О сильной регулярности некоторых реберно регулярных графов // Алгебра, логика и кибернетика Тез докл Иркутск 2004, 181-183

24 Махнев А А , Падучих Д В Новая оценка для числа вершин реберно регулярных графов // Труды 36-й молодежной конф ИММ УрО РАН Екатеринбург 2005, 52-54

25 Зюляркина Н Д , Махнев А А , Падучих Д В О графах, в которых окрестности вершин являются кликовыми расширениями решеток // Межд алгебр конф Тез докл Екатеринбург, изд-во Урал ун-та 2005, 178-179

26 Махнев А А , Падучих Д В Об одном классе кореберно регулярных графов // Известия РАН, сер матем 2005, т 69, №6, 95-114

27 Падучих Д В Об автоморфизмах сильно регулярного графа с параметрами (85,14,3,2) // Межд алгебр конф Классы групп и алгебр Тез докл , Гомель 2005, 85-87

28 Махнев А А , Падучих Д В Новая оценка для числа вершин реберно регулярных графов // Сибирский матем журнал 2007, т 48, №4, 817-832

29 Махнев А А , Падучих Д В О группе автоморфизмов графа Ашбахера // Алгебра и ее приложения, Красноярск 2007 Тез докл 93-94

30 Махнев А А, Падучих ДВ О локально грассмановых графах // Межд алгебр конф Санкт-Петербург 2007 Тез докл , 54-55

31 Paduchikh D V Non-existence of locally /(10,5)-graphs // Proceedings of the Steklov Inst of Math 2007, SuppI 1, 155-163

32 Кабанов В В , Махнев А А , Падучих Д В Характеризации некоторых дистанционно регулярных графов запрещенными подграфами // Доклады Академии Наук 2007, т 414, №5, 583-586

33 Махнев А А , Падучих Д В О локально грассмановых графах // Доклады Академии Наук 2007, т 415, №4, 450-454

34 Зюляркина Н Д, Махнев А А , Падучих Д В О графах, в которых окрестности вершин являются кликовыми расширениями решеток // Доклады Академии Наук 2007, т 416, №5, 735-739

35 Махнев А А , Падучих Д В О графах, в которых окрестности вершин изоморфны половинному графу свернутого 10-куба // Труды 39-ой молодежной конф ИММ УрО РАН Екатеринбург 2008

36 Падучих Д В Об автоморфизмах сильно регулярного графа с параметрами (85,14,3,2) // Труды 39-ой молодежной конф ИММ УрО РАН Екатеринбург 2008

37 Падучих Д В. Об автоморфизмах сильно регулярного графа с параметрами (85,14,3,2) // Дискрет матем 2008, т 20

Подписано в печать 18 04 2008 Формат 60x84/16 Уел печ л 1,1 Тираж 100 экз Заказ 143

«Уральский центр академического обслуживания» 620219, г Екатеринбург, ул Первомайская, 91

1 Оценка для числа вершин в реберно регулярных графах

1.0.1 Предварительные результаты.

1.0.2 Хорошие пары в графах с к > ЗЬ\ — 2.

1.0.3 Доказательство теоремы 1.1 и следствия 1.1.

2 Графы без т-корон

2.1 Окрестности вершин — кликовые расширения решеток

2.1.1 Общие результаты.

2.1.2 Доказательство теоремы 2.2.

2.2 Графы без корон с регулярными //-подграфами.

2.2.1 Вспомогательные результаты.

2.2.2 Доказательство предложения 2.

2.2.3 Графы Тервиллигера без корон.

2.2.4 Редуцированные графы без 3-коклик.

2.3 Графы без 3-корон с реберно регулярными /х-подграфами

2.3.1 Вспомогательные результаты.

2.3.2 Доказательство теоремы 2.5 и предложения 2.

2.3.3 Локальная характеризация графов без 3-корон

2.3.4 Восстановление окрестностей

2.4 Несуществование локально /(10,5) графов.

2.4.1 Предварительные результаты.

2.4.2 Локально /(10,5) графы.

2.5 Окрестности вершин изоморфны половинному свернутому 10-кубу.

2.5.1 Предварительные результаты.

2.5.2 Доказательство теоремы 2.8.

2.6 //-подграфы в локально графах Грассмана.

2.6.1 Вспомогательные результаты.

2.6.2 Локально (д + 1)хт подграфы в графах Грассмана ^(4, 2).

2.6.3 Локально (q + 1) х (q + 1)-подграфы в графах Грассмана Jq(n, 2).

2.7 Вполне регулярный локально J2(n, 2) граф с ß =

2.8 Вполне регулярные расширения GQ(4,2).

2.8.1 Случай ц = 8.

2.8.2 Случай ц = 16.

2.8.3 О вполне регулярных антиподальных накрытиях клик

2.8.4 Случай ц = 12.

3 Кореберно регулярные графы с двумя значениями Л

3.1 Предварительные результаты

3.2 Графы с двумя значениями Л, в которых /х-подграфы являются 2-кокликами.

3.3 Графы с Ai = 0.

4 Автоморфизмы дистанционно регулярных графов

4.1 Автоморфизмы сильно регулярного графа с параметрами (85,14,3,2).

4.1.1 Предварительные результаты.

4.1.2 Характеры групп и автоморфизмы графов.

4.1.3 Инволюхивные автоморфизмы графа с параметрами (85,14,3, 2)

4.1.4 Группа автоморфизмов графа с параметрами (85,14,3,2).

4.2 Автоморфизмы графа Ашбахера

4.2.1 Предварительные результаты

4.2.2 Неподвижные точки автоморфизмов графа Ашбахера.

4.2.3 Группа автоморфизмов графа Ашбахера, четный случай

4.2.4 Группа автоморфизмов графа Ашбахера, нечетный случай.

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

Регулярным графом степени к называется Граф Г, такой что для любой вершины и £ Г выполняется |Г(и)| = к. Реберно регулярным графом с параметрами (г), к, Л) называется регулярный граф степени к на и вершинах, любое ребро которого лежит точно в Л треугольниках. Вполне регулярным графом с параметрами (г>, к, А, /и,) называется реберно регулярный граф с параметрами (ь,к,Х), в котором любые две вершины и, ъи € Г на расстоянии 2 имеют ровно ц общих соседей. Сильно регулярным графом с параметрами (и, А,называется реберно регулярный граф с параметрами (у, к,Х), в котором любые две несмежные вершины и,гп € Г имеют ровно ц общих соседей.

В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии, и геометрии этого класса можно классифицировать. Например, класс билдингов Титса характеризует группы Лиевского типа [1].

Пусть С? — транзитивная группа подстановок на множестве О. Если стабилизатор (?р точки р 6 П имеет г орбит, то говорят, что С—группа ранга г. Пусть г = 3 и соответствующие 3 орбиты—это {р}, Г^р), Гг(р). Если Г1!(р) и Гг(р) содержат разное число элементов, то на множестве П можно построить сильно регулярный граф Г. Для этого положим, что точка р смежна со всеми точками из Г1 (р), и для каждого д € точка р9 смежна со всеми точками из Г^р)3. Если вместо Г^р) здесь взять Г2(р), то мы получим дополнительный сильно регулярный граф.

Д. Хигман (см. [2, 3]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов и действуют транзитивно на множестве {(и, w) | и, w Е Г и d(u, w) — г} для любого г < 2. То есть, такие графы являются дистанционно транзитивными графами диаметра 2.

Граф Г диаметра d называется дистанционно транзитивным, если для любого г е {0,., d} группа Aut Г действует транзитивно на {(u, w) | и, w € Г и d(u, w) = г}.

Дистанционно регулярным графом с массивом пересечений (Ъц, . , ci,., со) называется граф диаметра d, в котором для любых вершин u,w G Г, находящихся на расстоянии г, подграф T(w) содержит ровно bi вершин, находящихся на расстоянии г + 1 от и, и ровно сг- вершин, находящихся на расстоянии г — 1 от гг. Легко понять, что условие дистанционной транзитивности влечет дистанционную регулярность графа. Таким образом, результаты, полученные для дистанционно регулярных графов, применимы pi к дистанционно транзитивным графам.

Заметим, что сильно регулярный граф с ц > 0 является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с d > 2—вполне регулярным графом с к = bo, X — к — b\ — 1 и /j, — С2

Пусть задан класс графов Т. Мы скажем, что граф Г является локально Т-графом, если для любой вершины a G Г имеем Г(а) £ Т. Тогда можно поставить задачу описания локально JF-графов. Если граф Г вершинно транзитивен, то окрестности всех его вершин изоморфны, и граф Г является локально Т графом, где Т состоит из графов, изоморфных некоторому графу Д. В этом случае назовем Г локально А-графом. В более общем случае J- может быть классом графов, удовлетворяющих некоторым условиям. Например, класс связных, реберно регулярных графов—это в точности класс связных, локально регулярных графов.

Определим несколько сильно регулярных графов, которые будут фигурировать в диссертации, а также являются примерами локально А графов.

Пусть М и N—конечные множества порядка тип, соответственно. Два элемента из М х N будем считать смежными, если они различаются точно в одной координате. Полученный граф называется тп х тг-решеткощ при т — п он сильно регулярен с параметрами (п2, 2(п — 1),п-2,2).

Треугольным графом Т(п) называется граф 2-подмножеств множества порядка п, в котором две вершины смежны тогда и только тогда, когда они пересекаются в точности по одной точке. Граф Т(п) также сильно регулярен и имеет параметры (п(п—1)/2,2(77.-2), п—2,4). Окрестность каждой вершины в Т(п) изоморфна 2 х (п — 2)-решетке, т.е. Т(п)— локально 2х(и- 2)-решетка.

Единственный сильно регулярный граф с параметрами (27,16,10,8) называется графом Шлефли. Единственный сильно регулярный граф с параметрами (16,10, 6, 6) называется графом Клебша. Граф Шлефли является локально графом Клебша.

В главе 1 (см. также [51]) получена новая оценка для числа вершин в реберно регулярных графах. В [12, лемма 4.2.1] доказано, что если Г — связный неполный реберно регулярный граф с параметрами (v,k,X), в котором k > 3&i, то диаметр Г равен 2 и выполняется неравенство kb! > (у- к-1)(к-2Ьг + 1).

Полученные в главе 1 результаты позволяют уточнить эту оценку.

Пусть а, b — вершины графа Г. Число вершин в [а] П [Ь] обозначим через Х(а,Ь) (через ß(a,b)), если d(a,b) = 1 (если d(a,b) = 2), а соответствующий подграф назовем Х-подграфом (/i-подграфом).

Пусть Г — реберно регулярный граф с параметрами (v,k,X) и Ь\ — к — X — 1. Пара вершин и, w называется хорошей (почти хорошей), если d(u, w) = 2 и w) равно к — 2b\ + 1 (равно к — 2bi + 2). Тройка вершин (u;w,z) называется хорошей (почти хорошей), если w,z е Г2(и) и fi(u, w) + ß(u, z) не больше 2к — АЬ\ + 3 (равно 2к — 4Ь\ + 4).

Через Кти.,т„ обозначим полный п-дольный граф, с долями порядков mi,., mn. Если mi — . = тп = т, то соответствующий граф обозначается через Кпхт■ Граф называется 3-лапой.

Если вершины u,w находятся на расстоянии г в Г, то через bi(u,w) (через Ci(u,w)) обозначим число вершин в пересечении Г^+1(гг) (пересечении rji(w)) с [ги]. Заметим, что в реберно регулярном графе с параметрами (v,k, А) значение bi(u,w) не зависит от выбора ребра {и, w} и равно к — X — 1.

Теорема 1.1. Пусть Г — связный неполный реберно регулярный граф с параметрами (v, Ar, Л) и к > 3&i — 2. Тогда выполняется одно из следующих утверждений:

1) для любой вершины w верно неравенство \T2(w)\(k — 2bi+2) < kb\;

2) для любой вершины w верно неравенство j (/с — Ч- 2) > kb\ и либо Г является реберным графом тривалентного графа без треугольников (т.е. к = 4, Л = 1) и диаметр графа Г больше 2, либо Г является п-уголъником, п > о, или графом икосаэдра;

3) Г является полным многодольным графом Кгх2, 3x3 решеткой, треугольным графом Т(т), т <7, графом Клебша или графом Шлефли и для любой вершины т верно равенство |Г2(и;)|(А; — 2Ь\ + 2) = кЬ\.

Доказательство утверждения (2) теоремы из [33] некорректно (не доказано утверждение (3) из [33, лемма 3.3]). Следующий результат уточняет данное утверждение.

Предложение 1.1. Пусть Г — связный реберно регулярный граф диаметра 2 с параметрами (у, к,Х) и к — 3+ 3, 5 > —2. Тогда выполняются следующие утверждения:

1) если Г содержит такую 3-коклику Д, что любые ее две вершины образуют хорошие пары, то 8 = — 1 и Г является шестиугольником, графом икосаэдра или реберным графом тривалентного графа без треугольников, имеющим диаметр больше 2;

2) если 5 > 0 и для некоторой вершины т подграф Г2(гу) содержит две вершины, образующие хорошие пары с ии, то 5 < Ьу/2 — 2;

3) если для некоторой вершины ги подграф Г2(гу) содержит три вершины образующие хорошие пары с ъи, то 5 = —2, у — к — 1 = 26, + 2, ¿>1 (¿»1 — 1) делится на 3, подграф {/,и,г} является кликой, для х & {/, и, г} подграф Г2(го) П Г2(ж) содержит две вершины х',х", для различных вершин х, у € •{/, и, г) подграф [ги] П [ж] П [у] содержит единственную вергиину ху, граф {/и, иг, ¡г} является кликой и | [ги] — ([/] и [и] и = 4;

4) если для некоторой вершины т подграф Г2(ги) содержит четыре вершины {и, г, /, д}, образующие хорошие пары с ги, то Ь\ — 6, к = 16, Л = 9, у = 31, подграф {и, г, /, д} является кликой и ¿¿(ги, у) > 7 для любой вершины у из Г2(гу) — {и, г, /, д}.

Имеется немного результатов о единственности сильно регулярного графа с данными параметрами (у, к, А, у). В качестве следствия теоремы 1.1 получена единственность некоторых реберно регулярных графов с данными параметрами (у,к,Х).

Следствие 1.1. Пусть Г — реберно регулярный граф, имеющий те о/се параметры (у,к,Х), что и один из следующих графов: полный многодольный граф КГХз, 3x3 решетка, треугольный граф Т{т), т < 7, граф Клебша или граф Шлефли. Тогда Г изоморфен соответствующему графу.

Глава 2 посвящена изучению графов без т-корон.

Граф К с т долями порядка 1 называется т-короной. При т ~ 1 и т = 2 будем называть т-корону 3-лапой и короной, соответственно. Понятно, что т-корона получается из (тп — 1)-короны добавлением одной вершины, смежной со всеми остальными вершинами. Поэтому граф без т-корон—это в точности граф локально без (т — 1)-корон.

Пусть V является п-мерным векторным пространством над полем Два т-мерных подпространства из V будем считать смежными, если они пересекаются по (то — 1)-мерному подпространству. Граф на множестве всех то-мерных подпространств V с такой смежностью называется графом Грассмана и обозначается через Jq{n, т). При т — 2 граф Грассмана сильно регулярен. Граф Грассмана ^(п,т) не содержит (индуцированных) корон.

В параграфе 2.1 изучаются сильно регулярные графы, у которых окрестность каждой вершины является кликовым /3-расширением рхд-решетки. Интерес к таким графам был вызван тем, что при изучении графов без корон, в которых //-подграфы являются регулярными графами заданной положительной степени (см. [28, 43]) наибольшие трудности вызвал случай, когда окрестность каждой вершины является кликовым /3-расширением р х (/-решетки.

Теорема 2.1. Пусть Г — сильно регулярный граф с отрицательным собственным значением —т, в котором окрестность каждой вершины является кликовым (3-расширением р х д-решетпки, 2 < р < д. Тогда выполняются следующие утверждения:

1) число вершин в максимальной клике Ь графа Г равно 1 + Рд или 1 + /Зр, и (Ь,В) является (ь,Ь,г, к, \)-схемой, где В — множество сингулярных прямых графа Г, лежащих в Ь, к = ¡3 + 1, Л = 1, и тройка (<V, Ь, г) равна {1+Рд,(1 + рд)д/(р +1), д) или (1 + /Зр, (1 + /Зр)р/ЦЗ +1), р), соответственно; в частности, /3 + 1 делит р(р — 1) и д(д — 1);

2) если р < д, то число (1 + Рд)-клик в графе Г равно ри/( 1 + Рд), и 1 + Рд делит р[р — 1)(/л — р+ 1), а число (1 + /Зр)-клик равно дь/(1 + /Зр), и 1 + /Зр делит — 1)((1 — д + 1), если р = д, то 1 + /Зр делит 2(р — г)(р-1,Р + 1)(р+1,Р-1);

3) для двух несмежных вершин а, Ь любая строка (любой столбец) решетки, отвечающей [а], содержит 0 или /3 + 1 вершин из [Ь], и ц = г{/3 + 1), где/3 + 1 <t <р;

4) если Ь = /3 + 1, то [а] П [6] является £ х решеткой, и Г является треугольным графом Т(т) (т > 4), графом 7(10,5) или графом Грассмана Л1(п, 2), п > 4;

5) если тп = р — и, то I < р — и, причем равенство достигается лишь при и = 0; в частности, Ь ф р — 1, и если £ = р — 2, то т = р — 1, (2/3 + 1 ){р - 2) = Р(д - 1), и Р + 1 делит 2(р - 1, д);

6) если £ = р, то т = р, и г) Г является псевдогеометрическим графом для рСр+1(Рд,р—1), и (рч + р-р- 1){Р + 1) делит р(р- 1)/Зд(/Зд + 1), гг) если р < д, то Г является геометрическим графом, и каждый ц-подграф в графе прямых данной геометрии является объединением непересекающихся (/3 + 1) х (¡3 +1 )-решеток, (3 + 1 делит <7 — 1, и р(3 +1 делит д(д — 1)(/?д + 1); ггг) если р = д, то (¡3 + I)2 делит р2(р{3 + 1).

Заметим, что если Г — псевдогеометрический граф для 1)) являющийся локально р х р-графом, то Г — дополнительный граф для 4 х 4-решетки в случае р = 3 и граф ,7(8,4) в случае р = 4 (отсюда следует изоморфизм 7(8,4) и дополнительного графа для графа Грассмана

М 4,2)).

В теореме 2 из [17] была получена классификация сильно регулярных локально р х д-граф о в с 2 < р < г/ и < 6. Следующая теорема распространяет этот результат на графы, в которых окрестности вершин являются кликовыми расширениями р х ^-решетки.

Теорема 2.2. Пусть Г — сильно регулярный граф, в котором окрестность каэ/сдой вершины является кликовым 0-расширениемру.д-решетки, 2 < р < д- Если р < 6, то выполняется одно из следующих утверждений:

1) /3 = р — 1, иТ является графом Грассмана </р1 (п, 2);

2) ¡3 — р — 2, и либо Г имеет параметры второй окрестности вершины в графе Грассмана ,/р1(4,2), либо является точечным графом частичной геометрии рОр-\((р — 2)д,р — 1), р — 1 делит д — 1;

3) (3 = 2, и Г является псевдогеометрическим графом для частичной геометрии рСз( 12, 5);

4) /3 = 1, и Г является либо треугольным графом Т(д + 2), либо дополнительным графом для 4 х 4-решетки, графом 1(8,4) или <7(10, 5), либо псевдогеометрическим графом для частичной геометрии рй<¿(6, 5).

В параграфе 2.2 изучаются графы Тервиллигера без корон и графы без 3-коклик с регулярными /¿-подграфами (см. также [43]).

Пусть а1- — шар радиуса 1 с центром а. Для подграфа А графа Г через А1- обозначим Паела±- Граф Г назовем слабо редуцированным, если из равенства а1 = Ь1- следует а — Ь. Граф Г назовем редуцированным, если из включения а1- С следует а = Ь. Через Гх обозначим подграф на множестве всех вершин а таких, что а1- = Г.

М. Нумата [14] получил классификацию графов без корон, в которых /¿-подграфы являются изоморфными реберно регулярными графами диаметра 2 (естественно, не имеющими 3-лап). В связи с этим результатом представляет интерес изучение графов, в которых каждый //-подграф является реберно регулярным графом без 3-лап с заданными параметрами (v',k', А').

В статье В.В.Кабанова [28] было получено следующее обобщение результата Нуматы, опирающееся на более ранние работы A.A. Махнева и В.В. Кабанова:

Связный редуцированный граф без корон, содержащий 3-коклику, в котором ß-подграфы регулярны заданной степени а > 0 и имеют диаметр 2, является графом Грассмана, графом Джонсона или его частным, локально треугольным графом или графом Госсета.

Важным этапом в доказательстве этого результата стала лемма 2.1 [28], в которой доказано, что слабо редуцированный граф без 3-лап, содержащий 3-коклику, в котором /¿-подграфы регулярны заданной положительной степени, является редуцированным.

Предложение 2.1. Если Г — связный слабо редуцированный граф без 3-коклик, в котором ß-подграфы регулярны степени а > 0, то Г является редуцированным графом или пятиугольной пирамидой.

В статье A.A. Махнева и В.В. Кабанова [25] было доказано, что если Г—связный граф Тервиллигера без 3-лап, то либо Г является кликовым расширением графа икосаэдра, либо подграф, индуцированный на множестве всех вершин из Г — Г-1 с некликовыми окрестностями, является кликовым расширением пустого графа, клики или графа с ß = 1.

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

1) Г не содержит 3-коклик и является кликовым расширением 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды;

2) Г не содержит 3-лап, но содержит 3-коклику, диаметр Г больше 2, и либо г) Г является кликовым расширением графа икосаэдра, либо (гг) Г' является кликой, и Г является кликовым расширением графа А, где А содерэюит 8-клику и 8 или 5—1 вершин степени 1, смежных с различными вершинами клики, либо in) Г' является кликовым расширением графа с ß = 1;

3) Г содержит 3-лапу, ß = 1, и окрестность любой вершины из Г состоит из изолированных клик.

Следствие 2.1. Пусть Г — связный граф, в котором окрестности вершин являются регулярными графами Тервиллигера диаметра 2. Если окрестность некоторой вершины не содержит корон и Ъ-коклик, то либо Г является кликовым расширением пятиугольника или графа икосаэдра, либо Г — локально граф Петерсена, т.е. граф Т(7), граф Конвея-Смит на 63 вершинах диаметра 4 (это антиподальное 3-накрытие Т{7)) или граф Доро на 65 вершинах диаметра 3.

Следующая теорема является аналогом результата, полученного в статье В.В. Кабанова [28] для редуцированных графов без 3-коклик.

Теорема 2.4. Пусть Г — связный редуцированный граф без 3-коклик, в котором каждый ц-подграф регулярен заданной степени а > 0. Тогда Г сильно регулярен, или степень любой вершины из Г равна к или к — 1, подграф Г' на вершинах степени к является октаэдром, подграф на Г — Г' является 6-кликой и каждая вершина из Г — Г' смежна с 3-кликой из Г'.

Обратно, если Г — сильно регулярный граф без 3-коклик с параметрами (и, к, X, ц), то каждый //-подграф регулярен степени а = 2А + 2 — к.

Следствие 2.2. Пусть Г — связный редуцированный граф без корон, в котором каждый ц-подграф реберно регулярен с заданными параметрами (V', к', А') и имеет диаметр 2. Тогда выполняется одно из следующих утверждений:

1) А' = 0, и Г совпадает с октаэдром или треугольным графом Т(5);

2) А' > 0, Г не содержит 3-коклик и является сильно регулярным графом с параметрами ((я2 + Зя)2, (б-2 + 2й — 1)(з2 + Зя + 1), (я + 2)(з3 + 2*2 -1),(82 + 2з){З2 + 2.5-1));

3) А' > 0, Г содержит 3-коклику и является графом Грассмана, графом Дэюонсона или его частным, локально треугольным графом или графом Госсетпа.

В параграфе 2.3 изучаются Графы без 3-корон с реберно регулярными //-подграфами. А именно, с помощью классификации графов без корон с регулярными /х-подграфами диаметра 2 степени а > 0 (см. выше) в статье [55] были получены следующие две теоремы.

Теорема 2.5. Пусть Г — связный граф без 3-корон, в котором любой ц-подграф А состоит из у' > 1 вершин, и |Л(ж)пА(у)| = А' > 0 для любых смежных вершин х,у Е А. Если окрестность некоторой вершины из Г является графом Тервиллигера, то Г является либо кликовым (А' + 2)-расширением т х п-решетки, либо графом Тервиллигера одного из следующих типов:

1) клиповое расширение 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды;

2) кликовое расширение графа А, где А является объединением д-клики и 6 или <5 — 1 вершин степени 1, смежных с различными вершинами этой клики;

3) кликовое расширение графа икосаэдра или графа без 3-лап с ц = 1.

Теорема 2.6. Пусть Г — связный граф без 3-корон, в котором каждый у-подграф Д является реберно регулярным графом с параметрами (у1, к', А') и окрестностями вершин диаметра 2. Если 0 < Л' < к' — 1, то либо окрестности вершин в Г являются сильно регулярными графами без 3-коклик, либо Г — локально А-граф, где А — один из следующих графов:

1) треугольный граф Т(п) (п > 6) или граф Шлефли;

2) частное графа Джонсона .7(10, 5) или половинный граф свернутого 10-куба;

3) граф Грассмана ,/2з(п, 2), где п > 4.

В параграфах 2.4 и 2.5 доказано несуществование локально /(10, 5) графов и графов, являющихся локально половинным графом свернутого 10-куба (см. [40, 54, 58]). Таким образом, можно исключить случай (2) из теоремы 2.6.

В параграфе 2.6 доказано, что связные компоненты /¿-подграфов в локально ,/9(п, 2) графах являются графами Джонсона /(6,3) или дополнительными графами к 4 х 4-решетке. В частности, д = 2. См. также [55].

Графы знакопеременных и квадратичных форм над полем порядка 2 являются вполне регулярными локально Грассмановыми графами с ц = 20 (см. [16]).

В параграфе 2.7 доказано, что если Г — вполне регулярный локально </2(п, 2) граф с ц = 16, то п = 4 и |Г| = 72 (см. [56]).

Следствие 2.4. Пусть Г — связный граф без 3-корон, в котором каждый ц-подграф А является связным реберно регулярным графом с параметрами (у', к', Л') и окрестностями вершин диаметра 2. Если 0 < Л' < к' — 1, то выполняется одно из следующих утверждений:

1) либо Г является графом Шлефли или графом Госсета, либо граф Г имеет параметры ((г2+3г)2, г3+Зг2+г, 0, г2+г) для некоторого г > 1;

2) каждый ц-подграф является октаэдром, и Г — половинный граф ректаграфа с с-л - 3, являющийся локально треугольным графом;

3) Г является локально Грассмановым графом, и либо г) (л = 16, п = 4, и Г — антиподальный граф диаметра 3 на 72 вершинах, либо и) рь = 20, и если для любой вершины а графа Г граф Г2(а) является регулярным степени 15 ■2п~1 — 105, то Г имеет накрытие, являющееся графом АИ(п, 2) знакопеременных форм или графом С^иа(1(п — 1,2) квадратичных форм.

В параграфе 2.8 получено описание вполне регулярных локально 9(4,2) графов. См. статью [39].

Обобщенным четырехугольником порядка (б-, £) называется частичная геометрия рС?1 ($,£). То есть, каждая прямая содержит 5 + 1 точку, каждая точка лежит на £+1 прямой, и для любой прямой Ь и точки х £ Ь существует единственная точка у £ Ь, коллинеарная с х. Обобщенный четырехугольник порядка (в, £) обозначается через ОЦ(з^). Геометрия СС}(з,{) однозначно восстанавливается по своему точечному графу. Мы будем обозначать точечный граф обобщенного четырехугольника порядка £) также через

Нетрудно понять, что граф не содержит корон. Следовательно, локально графы не содержат 3-корон. Так как ^-подграфы в СС}(з^) являются (£ + 1)-кокликами, то в локально графах /хподграфы не содержат треугольников и, следовательно, не удовлетворяют условиям теорем 2.5 и 2.6. Следующая теорема дает описание вполне регулярных локально СС^(4, 2) графов.

Теорема 2.11. Вполне регулярный локально С(^(4, 2)-граф является одним из следующих графов:

1) единственный сильно регулярный локально 0(^(4, 2)-граф с параметрами (126,45,12,18);

2) единственный дистанционно регулярный локально Сф(4, 2)-граф на 378 вершинах с массивом пересечений (45,32,12,1; 1, 6,32,45) (это 3-накрытие графа из пункта (1)/

В главе 3 изучаются кореберно регулярные графы с [л = 2, у которых каждое ребро содержится в Ах или А2 треугольниках. Сделаны уточнения результатов [36]. См. работу [49].

Подграфы неподвижных точек автоморфизмов сильно регулярного графа с малыми значениями параметров А и ^ имеют жестко заданное строение. Так, непустой подграф неподвижных точек автоморфизма графа Мура сам является графом Мура или звездой (см. лемму 1 из [31]). Для изучения подграфов неподвижных точек автоморфизмов сильно регулярных графов с (1 — 2 может быть полезна следующая теорема.

Теорема 3.1. Пусть А — граф, в котором каждое ребро содержится в Х\ или А2 треугольниках, и подграф [и] П [го] является 2-кокликой для любых двух несмежных вершин и, т. Тогда либо Д — сильно регулярный граф, либо выполняются следующие утверждения:

1) граф Д регулярен степени к, окрестность любой вершины в А является объединением х изолированных (Ах + 1 )-клик и у изолированных (А2 + 1 )-клик, число (А1 + 2)-клик в А равно у(2(у -к- 1) - к(к - А2 - 1)) (А1 + 1)(А1 + 2)(А2-А1) 5

2) для связной компоненты £ графа Л1, определенного на множе-сгпве вершин графа А, в котором вершины а, Ь смежны, только если они смеэ/сны в Д и |[а] П [6]| = Ах, выполняются утверждения: г) если х > 1, то £ является вполне регулярным графом с параметрами (г>£,ж(Ах + 1), Ах, 2), п) если £ содержит геодезический 4-путь аЬсде, то х > 4, и для и е £ П [а] — £(а) имеем и) > 4, ш) если х — 2, то £ является (Ах + 2) х (Ах + 2)-решеткой, а если х = 3, то £ является графом диаметра 3, ги) если £ — сильно регулярный граф), то любая связная компонента графа Л1 изоморфна £, граф А*, определенный на множестве {£х, .,£,} связных компонент графа Л1, я = у/у^, в котором вершины £г- и £., смеэ/сны, если ] ф г, и некоторая вершина из £г смежна с единственной вершиной из является сильно регулярным с параметрами (в, у(А2 + 1),А2 + 2(г>£ — кя — 1), 2

3) если у = 1, то либо х = 1 и А является (Ах + 2) х (А2 + 2)-решеткой, либо х > 1 и выполняются утверждения: г) множество вершин графа А можно представить в виде разбиения на £ клик Си.,Сь порядка А2 + 2, где = у/(Х2 + 2), и граф А°, определенный на множестве {Сх,.,С^}, в котором клики С{ и С^ смеэ/сны, если ] Ф г и некоторая вершина из С\ смежна с вершиной из С^, является частичным четырехугольником с параметрами к- А2-1,АХ,2А2 + 4), гг) граф Л1 является дистанционно регулярным графом диаметра 4 с массивом пересечений {:г(А1 + 1), (х — 1)(Л1 +1), 2(А2 + 1), 1; 1, 2, (х — 1)(Ах+1), а;(А1+1)}, и если Ах > 0, то А^+4а;(Ах+1) является квадратом.

Заметим, что для связной компоненты П графа Л2, определенного на множестве вершин графа Д, в котором вершины а, Ь смежны, только если они смежны в Д и |[а] П [6]| = А2, выполняются утверждения, аналогичные сформулированным в теореме. В случае х = 1 выполняется аналог утверждения (3), полученный заменой (у, А2) на (х, Ах) и обратно.

Для четного натурального числа ш через МР(и>) обозначим класс ре-берно регулярных графов Г с параметрами 6х = Зш/2 — 3, к = ш2 — Зи/2,

Л = uj2 — Suj + 2, v = ш2, содержащих пару непересекающихся подграфов Qi и Г22, изоморфных КШХш/2, причем любая вершина из (из Г22) несмежна с единственной вершиной в каждой доле из Г22 (из fix), и для любого ребра {d, е} из fix подграф Г — (о?-1 U е1-) является ребром из Любой граф из МР{2) состоит из двух изолированных ребер, а граф из МР(4) изоморфен графу Клебша (сильно регулярному графу с параметрами (16,10,6,6)). По аналогии с листом Мебиуса, т-трапом Мебиуса назовем граф, полученный из графа вершин и ребер боковой поверхности m-призмы, разрезанием по боковому ребру, переворачиванием правой стороны на 180° и склеивания.

В теореме 1.4.3 из [12] доказано, что если Г — связный реберно регулярный граф с параметрами (v, А;, А), в котором А > к + 1/2 — у/2к + 2 (равносильно к > b\(b-[ + 3)/2 + 1), то Г — дополнительный граф для сильно регулярного графа с ц < 2. В следствии 2 из [36] (опирающемся на теорему 2 [36]) получено описание связных, реберно регулярных графов с к > b\(bi + 3)/2 — 2. Однако, доказательство теоремы 2 в [36] некорректно (ошибка в доказательстве леммы 27), поэтому теорема 2 и следствие 2 из [36] нуждаются в уточнении. Скорректированная формулировка теоремы 2 из [36] имеет вид

Теорема 3.2. Пусть Г — связный реберно регулярный граф с параметрами (v, к, А), в котором fi(u,w) = А или к — 7 для любых вершин u,w с d(u, w) = 2. Если для каэ/сдого ребра {a, b} подграф Г — (а1 U ¿г1) состоит из двух смежных вершин, то выполняется одно из следующих утверждений:

1) диаметр Г больше 2, и Г получается удалением из полного двудольного графа Kk+\,k+1 максимального паросочетания;

2) граф Г сильно регулярегь;

3) для вершины и 6 Г подграф {го 6 Г2(м) | ц(и, w) = к—7} является полным многодольным графом KyXs, s = ¿1 + 2 — 7, 1 < 7 < 61, и для графа Л1, определенного на множестве вершин графа Г, в котором две вершины a, b смежны, только если они несмежны в Г и ц(а, b) = А, верны утверждения: г) если у = 1, то Л1 является дистанционно регулярным графом диаметра 4 с массивом пересечений {ж, х — 1, 2s, 1; 1, 2, х — 1, х}, где х = Ь\ + 2 — ys, множество вершин графа Г можно представить в виде разбиения на t коклик Ci,. ,Ct (антиподальных классов) порядка s + l, где t = v/(s + 1), и антиподальное частное Г' является частичным четырехугольником с параметрами (t, b\ + 2 — s, 0, 2s + 2), гг) если Л1 имеет связную компоненту диаметра 2, то каждая связная компонента графа Лх является сильно регулярным графом с параметрами ((х2 + х + 2)/2, ж, 0, 2), где х = Ьг + 2 — ys = t2 + 1 для некоторого t не кратного 4, и граф Г*, определенный на множестве {Ei,., Е/} связных компонент графа Л1, I = 2v/(x2 + х + 2), в котором вершины Ej и Ej смежны, если j i и некоторая вершина из Е,-смежна с единственной вершиной из Еj, является сильно регулярным с параметрами (I, rs, s — 1 + х(х — 1)/2, х2 + х + 2).

Если выполняется утверждение (Зг) и Г' является полным двудольным графом, то Г б МР(ш), ш > 6, Ьх = Зш/2 — 3, к = и2 — Зи/2, s = üj/2 — \nv = и2.

Скорректированная формулировка следствия 2 из [36] имеет вид

Следствие 3.1. Пусть Г — неполный связный реберно регулярный граф с параметрами (v, к, Л). Если Л > к + 1/2-л/2к + 8 (равносильно 2к > b\ + 3Ö1 -4), то

1) граф Г является п-угольником, п > 6, тривалентным графом без треугольников, реберным графом тривалентного графа без треугольников, графом икосаэдра, треугольным графом Т(6) или графом Клебша (во всех этих графах bi < 3), или

2) граф Г является дополнительным к сильно регулярному графу с ß < 2, или

3) либо граф Г принадлежит МР(ш), ш = 6, 8, либо для графа А = Г выполняется одно из следующих утверждений: г) граф А разбивается дополнительными графами для 4-трапов Мебиуса <&i,., ФГ; где г = v/8 и граф А* на множестве вершин {Фь ., Фг}, в котором вершины Ф¿ и Фj смежны, если некоторая вершина из Фг смежна с вершиной из Фj в графе А, является сильно регулярным с параметрами (г>/8, t2 — 9,6,16), ut = 12 или 36, гг) граф А можно представить в виде разбиения наЗх 3-решеток Q].,., Г2.,, где s = v/9, и граф Д° на множестве вершин {füi,., в котором вершины Qj и Clj смежны, если некоторая вершина из Qi смежна с вершиной из Qj в графе А, является сильно регулярным с параметрами (и/9,t2 — 7,8,18), ut — 7,14 или 28, ш) граф Л на множестве вершин графа А, в котором вершины u,w смежны, если они смежны в А и |А(и) П Д(ги)| = 0, — дистанционно регулярный граф диаметра 4 либо имеющий массив пересечений {136,135, 6,1; 1,

2,135,136} и являющийся антиподальным 4-накрытием сильно регулярного графа с параметрами (2432,136,0,8), либо имеющий массив пересечений {х, х — 1,4,1; 1, 2, х — 1, х} и являющийся антиподальным 3-накрытием сильно регулярного графа с параметрами ((а;+2)(а;+3)/6, х, 0, 6).

В случае к = (й^+З&х)/2 в заключении следствия остаются п-угольник, граф икосаэдра, граф из МР(6) и дистанционно регулярный граф диаметра 4 с массивом пересечений {х,х — 1,4,1; 1,2, ж — 1,а;}, являющийся антиподальным 3-накрытием сильно регулярного графа с параметрами ((х -Ь 2)(а; + 3)/6,ж, 0, б), подтверждающие точность границы к > Ьу(Ь1 + 3)/2, дающей сильную регулярность графа.

Глава 4 посвящена изучению автоморфизмов дистанционно регулярных графов.

В монографии П. Камерона [27] представлен метод Г. Хигмана, который дает необходимое условие существования автоморфизма дистанционно регулярного графа.

Пусть Г — дистанционно регулярный граф диаметра й. Подстановочное представление группы (? = Аг^ Г на вершинах графа Г дает матричное представление ф группы С? в С). Пространство Си является ортогональной прямой суммой собственных подпространств И'оФ- - -ФИ^ матрицы смежности А графа Г. Для любого д Е С? матрица ф(д) перестановочна с А, поэтому подпространство И^- является 1/>(Сг)-инвариантным.

Пусть Хг~характер представления, полученного ограничением ф на IV,. Тогда г з=о где а^{д)—число вершин х из Г, таких что с1(х,х9) = ], а зависят от параметров Г.

Поскольку значения характеров — целые алгебраические числа, то в случае, когда значения С^^ рациональны, ХгО?) является целым числом. Отсюда получаем условие делимости для ] = 1,., с/. С помощью этого условия были получены новые ограничения для групп автоморфизмов сильно регулярных графов с параметрами (85,14,3, 2) (см. [60]) и (3250,57,0,1) (см. [52]). Эти результаты являются частью серии работ, посвященных изучению групп автоморфизмов сильно регулярных графов с малыми значениями Аид.

В параграфе 4.1 получены результаты о группе автоморфизмов сильно регулярного графа с параметрами (85,14,3,2).

Наименьшим примером сильно регулярного графа с параметрами (г*, к, 3, 2) является 5х5-решетка, имеющая параметры (25,8,3, 2). Следующим набором параметров сА = Зид = 2, для которого возможно существование сильно регулярного графа, является (85,14,3,2).

Теорема 4.1. Пусть V—сильно регулярный граф с параметрами (85,14,3,

2). Тогда для любого автоморфизма g из Aut Г простого порядка р выполняется одно из следующих утверждений:

1) р 6 {5,17} и Fix g— пустой граф;

2) р = 7 и Fix <7 является 1 -кликой, или р = 5 и Fixg является 5-кликой;

3) р — Ъ, Fix<7 является четырехугольником или 2x5-решеткой, и в последнем случае для шести вершин из Fi xg их окрестности содержат точно две максимальных Ъ-клики;

4) р = 2, окрестность каждой вергиины из Fixg связна, Fixg является объединением ip изолированных вершин и ф изолгьрованных треугольников, причем либо ф = 1 и <р G {4, 6}, либо ф — 0 и ip = 5.

В параграфе 4.2 изучается группа автоморфизмов графа Мура степени 57 (графа Ашбахера).

Для регулярного графа степени к и диаметра d на v вершинах выполняется неравенство: v < 1 + к + к(к - 1) + • • - + к(к - l)d1.

Графы, для которых достигается равенство, называются графами Мура. Простейшим примером графа Мура служит (2d + 1)-угольник.

Дамерелл в статье [5] доказал, что граф Мура степени к > 3 имеет диаметр 2. В этом случае v — к2 +1, граф сильно регулярен с А = 0 и ц, = 1, а степень к равна 3 (граф Петерсена), 7 (граф Хофмана-Синглтона) или 57. Существование графа Мура степени к = 57 неизвестно. Ашбахер в статье [4] показал, что граф Мура с к = 57 не является графом ранга 3. Мы будем называть грае}) Мура с к — 57 графом Ашбахера.

Пусть Г—граф Ашбахера, G = Aut Г. Ранее в работе [31] было доказано, что если G содержит инволюцию t, то G = 0(G)(t), и Fix t является 56-звездой. Приведенная ниже теорема не делает предположений о существовании инволюции.

Теорема 4.2. Пусть Т—граф Ашбахера и G = Aut Г. Тогда либо

1) G содержит инволюцию t, и либо 0(G) — Р—силовская Ъ-подгруп-па из G порядка 125, |[Р, i]| = 25, Z(P) действует полурегулярно на Г, Fix (Cp(t)) —граф Хофмана-Синглтона, и Р содержит 25 подгрупп Ui порядка 5, имеющих пятгщгольник в качестве подграфа неподвио>сных точек, либо G = Y(t) х X, Y—циклическая группа, инвертируемая t, |У| делит 7,19,55, делит 7,25,27 или 55, и если X ф 1, то верно одно из утверждений: г) FiхХ-звезда, |Х| = 7 и Y = 1, ii) ¥ixX—пятиугольник, делит 5, либо Fix ж— граф Хофмана-Синглтона для некоторого элемента х порядка 5 из X и \Х : (ж)| G

5,11}, либо Fix ж = FixX для любого неединичного элемента х из X и делит 55, in) FiъХ—граф Петерсена, \Х\ делит 27, |У| делит 5 и если У ф 1, то Fix У является пустым графом, iv) FiхХ—граф Хофмана-Синглтоиа, \Х\ делит 25, |У| делит 5 или 7, и если |У| = 5, то Fix У является пустым графом или пятиугольником, а если |У| = 7, то Fix У является звездой на 51 или на 16 вершинах либо

2) |G| нечетен и верно одно из утверэ1сдений: г) 19 делит \G\, G — Ga для некоторой вершины а, и G —подгруппа из группы Фробениуса порядка 3219, гг) 13 делит либо G—подгруппа из циклической группы порядка 65 и каждый неединичиый элемент из G действует без неподвижных точек на Г, либо G—группа Фробениуса порядка 39,

Иг) 11 делит |G|, G —расширение циклической группы порядка 11 с помощью элементарной абелевой группы U порядка, делящего 25, iv) 7 делит |G|, либо G—подгруппа прямого произведения циклической группы порядка 7 и элементарной абелевой группы U порядка, делящего 25, в случае U ф 1 подграф Fix U является графом Хофмана-Синглтона, либо G—группа Фробениуса порядка 21, v) 7r(G) С {3,5}, либо |G| делит 54, либо G—подгруппа из прямого произведения группы порядка 5 и группы порядка 27, либо G—группа Фробениуса порядка 75 или 543, либо \Z(G)\ — Ь и G/Z(G) —группа Фробениуса порядка 75.

Непустой подграф неподвижных точек подгруппы из группы автоморфизмов графа Мура является графом Мура или звездой. При доказательстве теоремы 4.2 используется следующий результат о подграфах неподвижных точек автоморфизмов графа Ашбахера.

Предложение 4.1. Пусть Т—граф Ашбахера, д— автоморфизм простого порядка р графа Г, Q = Fix«?. Тогда выполняется одно из утверждений:

1) £1—пустой граф и р G {5,13};

2) Q—звезда на и вершинах и либо ш = 1 up— 19, либо ш — 56 и р — 2, либо ш — 58 — 7у для некоторого у < 8 и р = 7;

3) Q— пятиугольник и р & {5,11};

4) О,—граф Петерсена и р = 3;

5) О,—граф Хофмана-Синглтона и р = 5.

1. Pain S., Thas J.A. Finite Generalized Quadrangles. Boston: Pitman, 1984.

2. Caldebrank R., Kantor W.M. The geometry of two weight codes // Bull. London Math. Soc. 1986, v. 18, 97-122.

3. Blokhuis A., Brouwer A.E. On locally 4-by-4 grid graphs //J. Graph Theory, 1989, v. 13, №2, p. 229-244.

4. Махнев A.A. Об одном классе графов без 3-лап // Матем. заметки, 1998, т. 63, №3, 407-413.

5. Cameron P. Permutation Groups, London Math. Soc. Student Texts 45, Cambridge Univ. Press. 1999.

6. Кабанов B.B. О графах без корон с регулярными /i-подграфами // Матем. заметки, 2000, т. 67, №6, 874-881.

7. Махнев A.A., Минакова И.М. Об одном классе реберно регулярных графов // Известия Гомельского госуниверситета, Вопросы алгебры 2000, т. 3 (16), 145-154.

8. Makhnev A.A. On the graphs with //-subgraphs isomorphic to Kux2 // Proc. Steklov Inst. Math., Suppl. 2, 2001, p. 169-178.

9. Махнев A.A., Падучих Д.В. Об автоморфизмах графа Ашбахера // Алгебра и логика 2001, т. 40, №2, 125-134.

10. Зарипов С.Р., Махнев A.A., Яблонко И.П. О сильно регулярных графах без треугольников // Алгебра и линейная оптимизация. Труды межд. семинара, посвященного 90-летию С.Н.Черникова, Екатеринбург 2002, 117-121.

11. Махнев A.A., Веденев A.A., Кузнецов А.Н., Носов В.В. О хороших парах в реберно регулярных графах // Дискрет, матем. 2003, т. 15, 77-97.

12. Зарипов С.Р., Махнев A.A., Яблонко И.П. Реберно регулярные графы диаметра 2сА>2&/3 — 2// Труды Украинского матем. конгресса, Киев 2001, секция 1: Алгебра и теория чисел, Институт математики HAH Украины, Киев 2003, 46-61.

13. Белоусов И.Н., Гурский Е.И., Дергач A.C., Махнев A.A. О почти хороших парах в реберно регулярных графах // Проблемы теор. и приклад, матем. Труды молодежной школы-конфер. Екатеринбург 2004, 9-11.

14. Махнев A.A. О сильной регулярности некоторых реберно регулярных графов // Известия РАН, серия матем. 2004, т. 68, №1, 159-172.

15. Махнев A.A., Минакова И.М. Об автоморфизмах графов с А = 1, ц = 2 // Дискрет, матем. 2004, т. 16, №1, 95-104.

16. Махнев A.A., Носов B.B. Об автоморфизмах сильно регулярных графов с Л = 0, р = 2 // Матем. сборник 2004, т. 185, №3, 47-68.

17. Белоусов И.Н., Махнев A.A. О почти хороших парах вершин в ре-берно регулярных графах // Изв. Урал. гос. ун-та, 2005, т. 36, №3, с. 35-48.Публикации

18. Махнев A.A., Падучих Д.В. Расширения GQ(4,2), вполне регулярный случай // Дискрет, матем. 2001, т. 13, №3, с. 91-109.

19. Paduchikh D.V. Non-existence of locally .7(10,5)-graphs // Укр. матем. конгресс 2001. Тез. докл. Киев, секция 1, с. 40.

20. Кабанов В.В., Махнев A.A., Падучих Д.В. О графах без корон с регулярными /¿-подграфами // Труды 33-й молодежной конф. ИММ УрО РАН. Екатеринбург 2002, с. 25-28.

21. Кабанов В.В., Махнев A.A., Падучих Д.В. Локальное строение графов без 3-корон с реберно регулярными //-подграфами // Международная конф. Алгебра и ее приложения, Красноярск 2002, с. 55-57.

22. Кабанов В.В., Махнев A.A., Падучих Д.В. О графах без корой с регулярными //-подграфами, II // Матем. заметки 2003, т. 74, с. 396406.

23. Кабанов В.В. , Махнев A.A., Падучих Д.В. О локально решетчатых подграфах в графах Грассмана // Алгебра, логика и кибернетика. Тез. докл. Иркутск 2004, с. 149-151.

24. Махнев A.A., Падучих Д.В. О сильной регулярности некоторых реберно регулярных графов // Алгебра, логика и кибернетика. Тез. докл. Иркутск 2004, с. 181-183.

25. Махнев A.A., Падучих Д.В. Новая оценка для числа вершин реберно регулярных графов // Труды 36-й молодежной конф. ИММ УрО РАН. Екатеринбург 2005, с. 52-54.

26. Падучих Д.В. Об автоморфизмах сильно регулярного графа с параметрами (85,14,3,2) // Дискрет, матем. 2008, т. 20.