Локальные подграфы и автоморфизмы графов тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Ефимов, Константин Сергеевич
- Специальность ВАК РФ01.01.06
- Количество страниц 85
Оглавление диссертации кандидат физико-математических наук Ефимов, Константин Сергеевич
Введение
1 Вполне регулярные графы с //, < А' — 261 +
1.1 Предварительные результаты.
1.2 Доказа гельство теоремы 1.
1.3 Доказательство предложения.
1.4 Доказательство теоремы 2 и следствия
2 Вполне регулярные графы с Ь\ —
2.1 Предварительные результаты.
2.2 Реберно регулярные графы больших степеней с bi = 6.
2.3 Графы с bi = 6, /х-подграфы большие или коклпковые.
2.4 Графы с bi = 6, //-подграфы малые, по не все кокликовые
2.5 Вполне регулярные графы с к = 10, Л = 3.
3 Автоморфизмы сильно регулярного графа с параметрами (75,32,10,16)
3.1 Предварительные результаты.
3.2 Автоморфизмы графа с параметрами (75,32,10,16)
3.3 Автоморфизмы точечного графа частичной геометрии pGг(4, 7)
Рекомендованный список диссертаций по специальности «Математическая логика, алгебра и теория чисел», 01.01.06 шифр ВАК
Локальное строение графов и их автоморфизмы2008 год, доктор физико-математических наук Падучих, Дмитрий Викторович
Хорошие пары вершин в реберно регулярных графах и автоморфизмы графов2009 год, кандидат физико-математических наук Чуксина, Наталия Владимировна
Конечные геометрии, графы, их расширения и автоморфизмы2015 год, кандидат наук Нирова, Марина Сефовна
Расширения обобщенных четырехугольников и их автоморфизмы2015 год, доктор наук Нирова Марина Сефовна
Комбинаторно симметричные графы и их автоморфизмы2006 год, кандидат физико-математических наук Казарина, Вероника Игоревна
Введение диссертации (часть автореферата) на тему «Локальные подграфы и автоморфизмы графов»
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрии, что каждая конечная простая группа дейс твует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию ([!()]-] 13|, [29], [28]). Например, класс билдингов Титса характеризует группы лиева типа (см. [32]). Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов (см. [10]).
Пусть G — транзитивная группа подстановок на множестве Если стабилизатор Gp точки р £ Г2, имеет г орбит на то говорят, что G имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г = 3 и соответствующие три орбиты — это {р\. Д(р), Г(р). Тогда по группе G удастся построить сильно регулярный граф Г, множество вершин которого О, и две вершины p,q смежны в Г, если q Е Г(р) (см. [17]).
Д. Хигман ([17|-[23]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзнтивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности. Оказалось, что в некоторых случаях комбинаторная симметричность графа влечет его дистанционную транзитивность.
Первые результаты о комбинаторно симметричных графах были получепы в пятидесятых годах. Пусть L(Kn) — реберный граф полного графа Кп па и вершинах или в других обозначениях треугольный граф Т(п). Этот грае}) является сильно регулярным графом с параметрами — 2), п — 2,4).
В работах 1959-60 годов Л. Чан г ([16]) и А. Хоффман ([24], [25)) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п — 8 было показано, что кроме треугольного графа Т{8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году (см.[15]).
Реберный граф L(Knhn) полного многодольного графа К7щп является ко-реберно регулярным графом с параметрами (mn,m + п — 2,2). Граф К1Г, -п называют m х п решеткой. При m = п решетчатый граф является сильно регулярным графом с параметрами (п2, 2т? — 2, п — 2,2). С. Шрикхандс в [31 ] показал, что граф, имеющий параметры п х п решетки является либо решеткой, либо графом Шрикханде (д, = 4).
Результаты Л. Чанга и С. Шрикханде были объединены Дж. Зейделем ([30]), который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдсль показал, что кроме треугольных графов Т(п) и решетчатых п х тг-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.
Для изучения реберно регулярных графов полезным оказался метод хороших пар и его обобщения.
Рассматриваются неориентированные графы без петель и кратных ребер. Если га, Ъ - вершины графа Г, то через d(a, b) обозначается расстояние между а и 6, а через ГДга) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Г] (а) называется окрестностью в ерш mm, a, и обозначается через [а]. Окрестность вершины называется локальным подграфом. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярны и графом степени к, если [а,] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберпо регулярным графом е паральетралш (v,k, Л), если Г содержит v вершин, является регулярным степени к. и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным графом с параметрами (v, к. А, /г), если Г реберно регулярен с соответствующими параметрами и под гриф [с/]П[6] содержит /1 вершин в случае d(a, Ъ) = 2. Вполне регулярный граф диаметра 2 называется силы/о регулярным графом.
Число вершин в [а] П [Ь] обозначим через Л(а, 6), если d(a,h) = 1, а соответствующий подграф назовем Х-подгрпфо и.
Если d(a,b) = 2, то число вершин в [а] П [Ъ] обозначим через //(а, 6), a соответствующий подграф назовем fj-подграфом.
Если вершины и, w находятся на расстоянии г в Г, то через bj(u, w) (через Cj(u:w)) обозначим число вершин в пересечении Гг-+х(и)
Рг-1 (гг)) с Г(?и). Заметим, что в реберно регулярном графе число bi(u,w) не зависит от выбора смежных вершин n,w и обозначается через бьГраф Г диаметра d называется дистанционно регулярным с массивом пересечений {bo, bd-ъ съ ■ • • • cd}, если значения bi(u. w) и с-,(и, w) не зависят от выбора вершин u,w на расстоянии i в Г для любого ? = 0,d.
Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом,, если [а] лежит и Т для любой вершины а графа Г. Если при этом класс F состоит из графов, изоморфных некоторому графу Д, то граф Г назовем локально А-графом.
Пусть Г - реберно регулярный граф с параметрами (г;, к, Л) и Ь\ = А*—Л—1. Пара вернтин u,w называется (почти) хорошей, если d(u,w) = 2 и ц(и.?п) равно к — 26i + 1 (равно к — 2Ь[ + 2). Тройка вершин (u,w,z) называется почти) хорошей, если ш, z Е Г2(11) и w) + /1(1/,, z) не больше 2к — 4/д + 3 (равно 2к - Щ + 4).
Если jj,(u,w) = к — 2b\ + 1, то подграф [и] П [?<;] является кликой и [d\ С и1 U wA для любой вершины d Е [и] Г) [wj.
Если Г содержит хорошую тройку (u,w,z). то подграф [г/,] П [ги] П [z] содержит не более одной вершины.
Аналогичный результат для почти хороших троек был получен А.А. Мах-невым и его учениками:
Пусть Г — связный реберно регулярный граф с параметрами (г>, к. Л), к = З61+7 и 7 > —2. Если (it, w, z) — почти хорошая тройка и Д = [it] П[ги]П[г] — непустой граф, то вершины w. z смежны и выполняется одно из следующих утверждений:
1) |Л| < 2 н 7 < —1;
2) подграф А является 3-кликой, bi = 6, к — 16 и v = 31;
3) подграф Л является 3-кликой, Ъ\ = 3 и Г — граф Клебша;
4) подграф Д является 4-кликой, Ь\ = 5 и Г - граф Шлефли.
С помощью этого результа та были получены новые верхние границы для числа вершин графов с к > ?>Ъ\ — 2. Теория хороших пар используется в диссертации при изучении графов с ц < к — 2Ь\ 3 и графов с Ь\ = 6.
Целыо диссертации является решение следующих задач:
1) изучить вполне регулярные графы с //. < к — 2Ь\ + 3;
2) изучить вполне регулярные графы с Ъ\ = 6;
3) найти возможные автоморфизмы сильно регулярного графа с параметрами (75,32,10,16).
Основными методами исследования являются методы теории конечных групп, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Основные результаты, полученные в работе, являются новыми. Выделим из них следующие.
1. Исследованы вполне регулярные графы с параметрами (v, к, А) и /1 < к -26) +3.
2. Исследованы вполне регулярные графы с = 6.
3. Выяснены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (75,32, 10,16) и ) точ-пепо строение группы автоморфизмов указанного графа, в случае, когда он является точечным графом частичной геометрии р(?2(4, 7). Рассмотрение данного случая завершает изучение автоморфизмов частичных геометрий pG2(4,t).
Работа носит теоретический характер. Результаты продолжают изучение реберно регулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения алгебраических структур подобного типа.
Результаты диссертации докладывались на международной алгебраической конференции в Санкт-Петербурге (2007 г.), VII международной школе-конференции по теории групп (Челябинск, 2008 г.), международной школе-конференции по теории групп, посвященной 80-летию со дня рождения Л.И.Коетрига (Нальчик, 2009 г.), и на 39-й, 40-й и 41-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2008-2010 гг.).
Результаты работы докладывались и обсуждались на алгебраических семинарах IIMM УрО РАН.
Основные результаты диссертации опубликованы в работах [33]-[41]. Работы |33]-|40] выполнены в нераздельном соавторстве с А.А. Махнсвым.
Работа состоит из введения, трех глав и списка цитированной литера туры, содержащего 39 наименований.
Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются вполне регулярные графы с ji < к — 2Ь\ + 3. Во второй главе работы исследуются вполне регулярные графы с b 1 = 6. В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (75,32,10,16).
Приведем основные результаты диссертации.
Пусть Г — сильно регулярный граф с параметрами (v, к, Л, д), Ь\ = к — Х — 1 и д = к — 261 + х. Если Г имеет целое собственное значение — т и т > 1, то х = in + b\(m — 2)/(m — l). Легко понять, что х — 1 (каждая пара несмежных вершин в силыю регулярном графе является хорошей) тогда и только тогда, когда. Г является пятиугольником.
Если Г — полный многодольный граф, то к = (п — l)(b\ +1) = д, поэтому х = 2Ь\. Таким образом для любого четного х имеется бесконечное семейство полных многодольиых графов с долями порядка х/2 -flu //, — к — 2Ь\ + х.
Если Г — граф с параметрами (4д + 1, 2д, // — 1, //,), то Ь\ = ц = х и 4х + 1 — сумма квадратов двух целых чисел. Значит, для нечетного х такого, что 4ж+1 не является суммой квадратов двух целых чисел, не существуют сильно регулярные графы с ц = к — 2Ъ\ + х и параметрами (4.x + 1, 2.r, х — 1, х).
Пример 1. Если + 1 = рп, р - простое число, то граф Пэли Р(р"), вершинами которого являются элементы поля F порядка рп и две вершины смежны тогда и только тогда, когда их разность является ненулевым квадратом в F, является сильно регулярным графом с параметрами (4.x + 1,2а;, ж — 1,ж).
Наименьшее нечетное х такое, что Ах + 1 не является суммой квадратов двух целых чисел, равно 5.
Если Г — псевдогеометрический граф для pGa(s,t). то к = s(t + 1). b\ = t(s -cv + 1). /i = a(t + 1) и x = (t - l)(s - a) + 21.
В случае x = 5 можно взять t = 2, s — a ~ 1. Таким образом, для графа
GQ(2, 2) имеем x = 5.
Теперь можно сформулировать ряд предположений.
Проблема А. Верно ли, что для любого натурального числа х существует сильно регулярный граф с ц = к — 2Ъ\ + х У
Проблема D. Верно ли. что для любого нечетного числа х существует лишь конечное число сильно регулярных графов с р = к — 2Ь\ + х?
Проблема С. Для каких четных чисел х существуют, бесконечные серии сильно регулярных грифов с ц = к — 2Ь\ + х и к > ц?
Первая глава направлена на изучение этих проблем.
Пусть Г является связным реберно регулярным графом с параметрами (г>, /с, Л) и Ь[ = к — Л — 1. Тогда для любых вершин u,w с d(u, w) — 2 имеем p(u,w) = к — 2Ъ\ + ж, где 1 < х < 2Ь\. В работе классифицированы вполне регулярные графы с х < 3.
Следующие результаты является основными в главе I.
Теорема 1 Пусть х натуральное число. Тогда выполняются следующие утверждения:
1) если х нечетно, то существует, сильно регулярный граф с // = к — 2Ъ\ + х;
2) если х > 3, 7по существует, лишь конечное число сильно регулярных графов ск>р,иц = к — 2Ь\ + х.
Предложение 1 Пусть Г — сильно регулярный граф) с параметрами (v, к, Л, ц), рь = к — 2Ь\ +х < к и 3 < х < 10. Если Г имеет целое собственное з?ш-чение —т, то х — т + Ь\{т — 2)/(т — 1) и выполняется одно их следующих утверждений:
1) х 6 {3,4} и Г — граф Пэли с параметрами (4х + 1, 2х, х — 1, х);
2) х = 5 и Г является дополнительным графом к 4 х -{-решетке, треугольному граф) у Г (С)) или графу Клебша;
3) х — б и Г является одним из следующих графов: (г) граф) 11 эли с параметрами (25,12, 5, 6). гг) граф Хофмана-Сипглтона или его дополнение,
Ш) граф с параметрами (26. 10.3,4) или его дополнение;
4) х = 7 и Г ябляется одним из следующих графов: (г) граф Пэли с параметрами (29.14, 6, 7), гг) псевдогеометрический граф) для GQ(4,2), £>С?2(5,2). рСз(6, 2) или pG4( 7,2), дополнительный граф для псевдогеометрического графа, обобщенного четырехугольника GQ(3.3) или для графа Гевиртца;
5) х = 8 и Г является одним из следуют,их графов: г) граф с параметрам/и (85,14,3,2), (49,18,7,6) или (49,32,21,20), (гг) дополнительный граф для 5 х Ъ-решетки или для треугольного графа Т( 7);
6) х = 9 и Г является одним из следующих графов: (г) граф с ■параметрами (37,18, 8, 9) или (69, 20, 7, 5), гг) псевдогеометрический графом для, pG-)(7.i 2) шш Л/г л рСз(8, 2), (///) дополнительный граф для псевдогеометрического графа обобщенного четырехугольника, GQ(3,5) или для граф>а с параметрами (77,16,0,6);
7) ж = 10 и Г является одним из следующих графов: г) граф) с параметрами (41, 20, 9,10) или граф Гевиртца с параметрами (56,10,0,2), гг) псевдогеометрический граф для р(?2(8, 2), pG-j(9,2), pGo(8,3), pG3(5,3), рС2(4,3) или для GQ(3,3), ггг) дополнительный граф для графа с параметрами (81,20,1,6) или для псевдогеометричсского графа геометрwu pG^(7, 2), iu) 6 х 6-решетка. треугольный граф Т(8), граф Шлефли ил,и один из трех графов Чанга.
В теореме Ливиигегона-Тэйлора, (теорема 1.3.3 из [10]) доказано, что во вполне регулярном графе выполняется неравенство /i > к — 2&1 + 1 и описаны графы с fj = A; —26i + l. Белоусов И.Н. и Махнев А.А. ([8]) классифицировали вполне регулярные графы с //, = & — 2Ь[ + 2. В диссертации рассматривается следующий случай.
Теорема 2 Пусть Г - вполне регулярный граф с параметрами (г>, к, А,//) и fj, = к - 2Ь\ 4-х', ж < 3. Тогда выполняется одно из следующих утверждений:
1) .г = 1 и Г — граф икосаэдра или граф прямых регулярного графа без треугольников, имеющего обхват, больший 4;
2) х = 2 и Г — граф Зейделя или тривалентный граф без треугольников диа метра, большего 2, с /х = 1:
3) х — 3 и Г один из следующих графов: граф Пэли с параметрами (13,6,2,3). куб или граф Клейна,
И) граф Тэйлора с параметрами (&Ь\ — 4,3/^ — 3, 2&i — 4, Ъ\) и Ъ\ £ {4,6,10}, ггг) регулярный граф без треугольников стен сии 4 или граф с Ь\ = 4, к = 6 и А = 1.
Для дистанционно регулярных графов получаем
Следствие 1 Пусть Г — дистанционно регулярный граф диаметра, большего 2, с // = к — 2Ь\ + х и х < 3. Тогда выполи,ж тся одно из следующих утверждений:
1) х = 1 и Г — граф икосаэдра, п-угольник, п > 6; реберный граф графа Мура или флаг-граф регулярного обобщенного п-уголышка, п £ {3,4,б}; порядка (s, s) для некоторого s;
2) .г = 2 и Г - додекаэдр, граф Хивуда, Паппа. Кокстера, Дсзарга, Бигза-Сим,са, Фостера или т-клетка Татта, т Е {8,12};
3) х = 3 и Г - один из следующих графов: г) куб или граф Клейна, а) граф Т.) и лора с параметрами (66i — 4, 3fri — 3, 2b\ — 4, 61) и 1ц G {4,6,10}. in) нечетный граф О4, его двудольное удвоение, граф инцидентности PG(2, 3), AG{'2, 3) с удаленным классом параллельных прямых, GQ(3, 3) или GH( 3,3).
При изучении реберно регулярных графов с k > f(b\) для некоторых функции / удаетея установить оценку v < g(k) (или получить описание графов, для которых не выполняется оценка v < g(k)). Так, в [10, лемма 1.4.2] доказано, что если Г — связный неполный реберпо регулярный граф с параметрами (и, к, А), в котором к > ЗЬ\, то диаметр Г равен 2 и v < 2к — 2. Фактически доказано, что v < к — 2 + З61 + S/(b\ + 1), it уточнение границы для числа вершин потребует описания графов с малыми значениями Ь\ и графов, насыщенных хорошими парами вершин.
В монографии Броувера, Коэна и Ноймайера доказано, что связный реберно регулярный граф с b\ = 1 является многоугольником или полным мпо-годольпым с долями порядка 2. Кроме гого, ранее исследовались реберно регулярные графы с Ъ\ < 5 (|9|, [5]). В данной работе изучаются вполне регулярные графы с Ь\ = 6.
Основным результатом второй главы являются
Теорема 3 Пусть Г — связный реберно регулярный граф с параметрами (v, к, А). Если Ъ\ = 6 и к > 22; то Г полный многодолъный граф Кгх7, г > 5 или граф из МР(6).
Теорема 4 Пусть Г — связный вполне регулярный граф) с параметрами (v, /с, А, //) и Ь\ = 6. Тогда Г является одним из следующих графов:
1) полный многодольный граф Krxj, граф с параметрами (25,12, 5, 6). 7х 7-решетка, треугольный граф Т(9). дополнительный граф к 5 х Ъ-решетке или к треугольному графу Т(7), граф Хофмапа-Синглтона или его дополнение, граф с параметрами (26,10.3,4) или его дополнение;
2) полный двудольный граф Kgs с удалелтым максимальным пар о сочетанием, граф Тэйлора с параметрам.и (28,13,6,6), в котором окрестности вершин изоморфны графу Поли Р( 13) или граф Тойлора, с параметрам,и (32.15,8,6), в котором, окрестности вершин изоморфны треугольному граФУ Т(6);
3) fj = 4, к = 12, сз(и,у) > 6 для любых вершин и, у с d(u,y) = 3 и диаметр Г равен 3;
4)/i, = 3u9<K 12;
5) ц, = 2 и 7 < к < 11;
6) jj, = 1 и окрестность каждой вершины является 7-кокликои, объединением, изолированны г п-клик для п = 2, 3 или 6.
Таким образом, изучение вполне регулярных графов с Ь\ = 6 редуцируется к случаю к = 10, Л = 3.
Теорема 5 Пусть Г -- связный вполне регулярный -граф с параметрами (г, 10,3,/х). Тогда выполняется одно из следующих утверждений:
1) диаметр Г равен 2 иТ является дополнительным графом к треугольному графу Т(7) или одним из десяти графов с параметрами (28,10,3,4);
2) /л = 3 диаметр Г равен 3 и 34 < v < 37;
3) ц = 2 и Г является графом Конвея-Смита или графом Доро.
Рассматривая дистанционно регулярные графы, получаем
Следствие 2 Пусть Г — дистанционно регулярный граф с к = 10, Л = 3. Тогда выполняется одно из следующих утверждений:
1) диаметр Г равен 2 и Г является дополнительным графом к треугольному графу Т(7) или одним из десяти графов с параметрами (28,10,3,4);
2) // = 2 и Г является графом Конвея-Смита или графом Доро.
В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (75. 32,10,16) и уточняется строение группы автоморфизмов указанного графа, в случае, когда он является точечным графом частичной геометрии pG2(4.7).
Для изучения возможных порядков и подграфов неподвижных точек автоморфизмов дистанционно регулярных графов Г. Хигмен предложил оригинальный метод, использующий теорию характеров конечных групп. Этот метод изложен в монографии П. Камерона (см.[14]), причем он применялся только к изучению инволютивиых автоморфизмов сильно регулярного графа с параметрами (3250,57,0,1). Позднее, в работах [2]-[3] изучаиись автоморфизмы сильно регулярных графов с малыми числами пересечений. В данной работе л тот метод применяется для изучения автоморфизмов сильно регулярного графа с параметрами (75,32,10,16).
Основными результатами третьей главы являются следующие теорема и следствие.
Теорема 6 Пусть Г — сильно регулярный граф с пара метрами (75, 32,10,16), д элемент простого порядка р из Ant(r) и Q, = Fix(g). Тогда верно одно из утверждений:
1) Г2 — пустой граф, р = 3 и n\(g) е {0, 30,60} или р — 5 и а\(д) делится на 50;
2) Q является п-кликой, и либо п = 3, р = 3 и ос\{д) — 6 делится на 30, либо п = 5, р — 7 и о>\(д) = 0;
3) Q является т-кокликой, р = 2, m нечетно, 3 < т < 15, o;i(/;) — 2т делится па 10, и в случае т— 15 пара (О, Г — является (15, 60, 32, 8,16)-схемои;
4) содержит 2-лапу, р = 2 и либо г) О объединение изолированной вершины и октаэдра, либо и) Q — объединение 'изолированной вершины и подграфа, либо (in) |Q| = 2t + 1. 4 < t < 15 или t = 17.
Следствие 3 Пусть Г - точечный граф частичной геометрии pG^^, 7), G - группа автоморф) из мое графа Г, g - элемент простого порядка р из G и Q = Vix(g). Тогда |G| делит 21 • 3 • 52 и верно одно из утверждений: ■
1) Q — пустой граф, либо р = 3 и а \(д) € {0,30,60}, либо р = 5 и ai(g) G {0,50}:
2) р = 2 и либо г) gl\ (д) = 0; О, — треугольный граф Т(6), каждая точка из Г — Q смслсна с 6 точками из Q или Q является rn-кокликой и т £.{5,15}, либо (ii) а\ (д) ф 0; Q,.- объединение октаэдра и I изолированных точек. 1 < I < 11, I нечетно или О — объединение изолированной точки и точечного графа для pG-2(2,3).
Похожие диссертационные работы по специальности «Математическая логика, алгебра и теория чисел», 01.01.06 шифр ВАК
Реберно регулярные графы и их автоморфизмы2007 год, кандидат физико-математических наук Белоусов, Иван Николаевич
Сильно регулярные графы с собственным значением 3, их расширения и автоморфизмы2015 год, кандидат наук Кагазежева, Алена Мухамедовна
Границы для числа вершин в графах и автоморфизмы графов2010 год, кандидат физико-математических наук Исакова, Мариана Малиловна
Расширения обобщенных четырехугольников и их автоморфизмы2014 год, кандидат наук Хамгокова, Мадина Мухадиновна
Почти хорошие тройки вершин в графах и автоморфизмы графов2010 год, кандидат физико-математических наук Токбаева, Альбина Аниуаровна
Список литературы диссертационного исследования кандидат физико-математических наук Ефимов, Константин Сергеевич, 2010 год
1. Махнев, А.Л. Об одном классе реберно регулярных графов/ А. А. Махнсв, И.М. Мннакова// Известия Гомельского гос. ун-та- 2000.- Т.З.- 0.115-154.
2. Махиев, А.А. Об автоморфизмах сильно регулярных графов с Л = О, li = 2 А.А. Махиев, В.В. Носов// Мат. сб.- 2004.- Т. 185, №3,- С.47-68.
3. Махнев, А.А. О сильной регулярности некоторых реберно регулярных графов/ А.А. Махнев// Известия РАН, сер. матем,- 2001,- Т.68.- С.159-172.
4. Махнев, А.А. О псевдогеометрических графах некоторых частичных геометрий/ А.А. Махнев // Вопросы алгебры. Выпуск 11. Гомель: Изд-во Гомельского ун-та. 1997. С. 60-67.
5. Казарина, В.И. О реберно регулярных графах с Ъ\ = 5/ В.И. Казарина, А.А. Махнев // Межд. конф. "Алгебра, логика и кибернетика". Тез. докл. Иркутск 2001, 159-161.
6. Brouwer, A.E. Distance-regular graphs/ A.E. Brouwer, A.M. Cohen, A. Neumaier// Berlin etc: Springer-Verlag- 1989,- 495 c.
7. Brouwer, A.E. The Gewirtz graph: an exercize in the theory of graph spectra/ A.E. Brouwer, W.H. Haemers// Euiop. J. Comb.- 1993,- Vol.14.- P.397-407.
8. Buekenhout, F. Foundations of incidence geometry , F. Buekenhout 1 / Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsevcr Science. Amsterdam.- 1995.- P.63-107.
9. Higman, D.G. Finite permutation groups of rank 3/ D.G. Higman// Math. Z- 1964,- Vol.86.- P. 145-156.18| Higman, D.G. On finite affine planes of rank 3/ D.G. Higman// Math. Z.-1968,- Vol.104.- P. 147-149.
10. Higman. D.G. A survey of some questions and resalts about rank 3 permutation groups/ D.G. Higman// Actcs, Cjngrcs Int. Math. Rome.- 1970.-Vol.l.- P.361^365.
11. Higman, D.G. Characterization of families of rank 3 permutation groups by the subdegrees I, II/ D.G. Higman/ ' Arth. Math.- 1970,- Vol.21.- P.151-156; 353-361.
12. Higman, D.G. Coherent configurations/ D.G. Higman// Rend. Sem. Mat.Univ. Padova.- 1970.- Vol.44.- P. 1-26.
13. Hoffman, A.J. On the uniqueness of the triangular association scheme/ A.J. Hoffman// Ann. Math. Stat.- I960,- Vol.31.- P.492-497.
14. Hoffman, A.J. On the cxceptioal case in a characterization of the arcs of complete graphs/A.J. Hoffman// IBM J. Res. Develop.- I960.- Vol.4.- P.487-496.
15. Hoffman, A.J. On the line-graphs of the complete bipartite, graph/ A.J. Hoffman// Ann. Math. Stat.- 1964,- Vol.35.- P.883-885.
16. Macay M. Search for properties of the missing Moore graph/ Macay M. Siran J. // Linear Algebra and its Appl. 2009.
17. Numata, M. On a characterization of a class of regular graphs/ AI. Numata// Osaka J. Math.- 1974,- Vol.11.- P.389-100.
18. Prager, C.E. Low rank representations and graphs for sporadic groups/ C.E. Prager, L.H. Soicher Lecture series 8.- Cambridge: University press.-1997.
19. Seidel, J.J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3/ J.J. Seidel// Linear Algebra and Appl 1968 - Vol.1.- P.281-298.
20. Shrickhande, S.S. The uniqueness of the association scheme/ S.S. Shrickhandc// Ann. Math. Stat.- 1959,- Vol.30.- P.781-798.
21. Tils, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.386.Работы автора по теме диссертации
22. Ефимов, К.С. О сильно регулярных графах с /1 = к — 2Ъ{ + х / К.С Ефимов, А.А. Махнев // Классы групп, алгебр и пх приложения, Гомель2007.- Тез. докл. С. 68-69
23. Ефимов, К.С. Вполне регулярные графы с ц < к — 2&1 + 3 К.С. Ефимов, А.А. Ма,хпев // Межд. алгебр, коне]). Санкт-Петербург 2007.- Тез. докл. С. 29-31.
24. Ефимов, К.С. Вполне регулярные графы с Ъ\ = 6 / К.С. Ефимов, А.А. Махнев // Труды 39-й Всеросе. молод, конф. Изд-во 11 ММ УрО РАН, Екатеринбург 2008. С. 16-18.
25. Ефимов, К.С. Вполне регулярные графы с ц < к~2^+3 / К.С. Ефимов, А.А. Махнев // Труды Института математики НАН Беларуси 2008.- Т. 16, N 1. О. 28-39.
26. Ефимов, К.С. О реберно регулярных графах с Ъ\ = 6 / К.С. Ефимов, А. А. Махнев // VII Международная школа конференция по теории групп2008,- Тез. докл. С. 48-51.
27. Ефимов, К.С. Вполне регулярные графы с Ь\ = 6 / К.С. Ефимов, А.А. Махнев /', Журнал Сибирского Федерального ун-та 2009.- Т. 2, N 1. С. 63 77.
28. Ефимов, К.С. Об автоморфизмах графа с параметрами (75,32,10,16) / К.С. Ефимов // Сибирские Электронные Математические известия2010.- Т. 7. С. 1-13.
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.