Содержание к диссертации
Введение
1 Определения, обозначения и предварительные результаты 21
1.1 Сильно регулярные и дистанционно регулярные графы 22
1.2 Схемы отношений 25
1.3 Графы Деза 33
2 Об изоморфизме между дистанционно-регулярными графами 35
2.1 Предварительные определения и результаты 35
2.2 Графы Мэтона M(2,q) и графы Мухаметьянова Гв и Tj . 35
2.3 Гд о± M(2,q) 40
2.4 T'j ~ M(2,q) 44
3 О вершинной связности одного класса графов Деза 49
3.1 Вспомогательные результаты 50
3.2 Вершинная связность графов Деза из класса Т> 52
3.2.1 Сведение задачи к трем случаям 52
3.2.2 Графы Деза, полученные из графов п х п-решетки . 55
3.2.3 Графы Деза, полученные из Т(п) 59
3.2.4 Графы Деза, полученные из спорадических графов Зей-
3.2.5 Доказательство теоремы 63
3.3 Заключение 63
4 Точные графы Деза, имеющие 14, 15 и 16 вершин 65
4.1 Отбор допустимых наборов параметров 65
4.2 Перебор матриц смежности 67
4.3 Отбор попарно неизоморфных графов 68
4.4 Поиск конструкций для найденных графов Деза 75
4.5 Заключение 76
5 Кэли-Деза графы, имеющие менее 60 вершин 77
5.1 Вспомогательные результаты 77
5.2 Описание алгоритма 78
5.2.1 Получение вспомогательной информации из системы GAP 78
5.2.2 Нумерация подмножеств элементов групп 79
5.2.3 Построение дерева перебора 79
5.3 Результаты 82
Список литературы
- Схемы отношений
- Графы Мэтона M(2,q) и графы Мухаметьянова Гв и Tj .
- Графы Деза, полученные из графов п х п-решетки
- Нумерация подмножеств элементов групп
Схемы отношений
Ключевым моментом в доказательстве указанной теоремы является тот факт, что все рассматриваемые графы (Гв, T J, Г" и M(2,q)) являются вершинно транзитивными. При этом напоминаем, что любой вершинно транзитивный граф может быть представлен в виде графа, вершинами которого являются смежные классы произвольной транзитивно действующей подгруппы группы автомофизмов графа по стабилизатору некоторой вершины в указанной подгруппе.
Графы Деза В 1994 г. в работе [15] М. Деза, изучая некоторые геометрические объекты, рассмотрел класс регулярных графов, в которых число общих соседей любой пары различных вершин принимает одно из двух возможных значений, но не определяется в общем случае смежностью этих вершин. Такие графы естественно рассматривать как обобщения (за счет релаксации комбинаторной симметрии) сильно регулярных графов.
Систематическое изучение свойств таких графов было начато в работе [42] в 1998 г., кроме того, в этой же работе предложены некоторые конструкции графов Деза: из сильно регулярных графов с помощью инволюции (автоморфизма порядка 2), переставляющей только несмежные вершины, с помощью разностных множеств в группе (конструкция графов Кэли, которые являются графами Деза), склеиванием классов в схемах отношений. В той же работе были перечислены все неизоморфные графы Деза, имеющие не более 13 вершин.
Далее в работах Ермаковой и Кабанова 2006-2009 гг. [27-31] изучались графы Деза без 3-коклик.
В работах Шалагинова и Кабанова [44-46] изучались точные графы Деза, полученные с помощью автоморфизма порядка 2 из треугольных графов и дополнительным к ним, из решетчатых графов и дополнительных к ним. В частности, доказано, что графы Деза, полученные из треугольных графов и дополнительных к ним графов, с помощью этих автоморфизмов, однозначно определяются по своим параметрам и строению окрестностей;
доказано, что точные графы Деза, полученные из решетчатых графов с помощью симметрии относительно главной диагонали, однозначно определяются по своим параметрам и строению окрестностей;
доказано, что точные графы Деза, полученные из дополнения к решетке с помощью автоморфизма, переставляющего пару строк, однозначно определяются по своим параметрам и строению окрестностей.
Фундаментальным подклассом вершинно-транзитивных графов являются графы Кэли. В работах [33-36] были исследованы дистанционно-регулярные и сильно регулярные графы, являющиеся графами Кэли. В частности, получена классификация сильно регулярных графов Кэли циклических и диэд-ральных групп.
Напомним конструкцию графов Деза, которые являются неориентированными графами Кэли.
Теорема 0.5 (Proposition 2.1, [42]). Пусть D — подмножество элементов группы G такое, что (i) \G\ = п и \D\ = к; (ii) единица е группы G не содержится в D; (iii) D l = D;
(iv) 3 такие натуральные a}b и к, что DD l = аА+ЪВ+ке, где множества А, В и {е} образуют разбиение G;
(v) Пусть Г — граф, вершинами которого являются все элементы группы G, и вершины и и v смежны тогда и только тогда, когда v lu Є D. Тогда Г — граф Деза с параметрами (п, к, 6, а), где Ъ а.
Граф Деза Г может быть получен с помощью указанной теоремы тогда и только тогда, когда существует подгруппа группы автоморфизмов графа Г, действующая регулярно на вершинах Г.
Пусть Гі и Г2 — графы. Композицией Гі[Г2] графов Г і и Г2 называется граф с множеством вершин 1 (Гі) х У(Г2), и вершины (щ щ) и (г і,г 2) смежны тогда и только тогда, когда либо щ смежна с г і, либо щ = fi, и щ смежна с г 2, см. [43].
Теорема 0.6 (Proposition 2.3, [42]). Если Г і — сильно регулярный граф с параметрами (П,А;,Л,/І) и G 2 - граф Деза с параметрами (п;, к , Ь,а), то Гі[Гг] — регулярный граф степени {к + кп!) на пп! вершинах. Этот граф является графом Деза тогда и только тогда, когда
{а + кп , Ъ + кп , fin , \п! + 2к } \ 2.
Пример 0.1 (Example 2.4, [42]). Если Г і = Кх (полный граф на х вершинах) и Г2 = уК2 (у копий К і), тогда граф Г і [Г2] является графом Деза с параметрами (2ху, 1 + 2у(х — 1),2у(х — 1),2 + 2у(х — 2)).
Пример 0.2 ( Example 2.5, [42]). Если Г і — (n, &,А) граф (сильно регулярный граф с \і = X) и Г2 = ІІГП/ (вполне несвязный граф), тогда Г і [Г2] — граф Деза с параметрами (nn ,kn ,kn ,Xn ). Эти графы однозначно определяются своими параметрами, что видно из следующей теоремы. Теорема 0.7 (Theorem 2.6, [42]). Пусть Г граф Деза с параметрами (п, к, 6, а). Тогда к = b в том и только том случае, если Г изоморфен Гі[Г2]; где Г і — (пі, &і, Лі) и Г2 = іГП2 для некоторых щ, щ, /сі, Лі. При этом его параметры равны
п = щщ, к = Ъ = к\П2і а = Мщ Пусть Гі и Г2 — графы. Произведением Г і х Г2 называется граф на множестве вершин 1 (Гі) х У(Г2), в котором вершины (щ щ) и (fi,f2) смежны тогда и только тогда, когда либо щ = V\ и щ смежна с г 2, либо it2 = г 2 и it і смежна с г і, см. [43]. Будем называть произведение нетривиальным, если оба графа Гі и Г2 имеют хотя бы по 2 вершины. Заметим, что Г і х Г2 — Г2 х Гі, поэтому ниже в теореме порядок сомножителей не играет роли.
Теорема 0.8 (Theorem 2.8, [42]). Нетривиальное произведение графов Г і хГ2 является графом Деза тогда и только тогда, когда выполняется одно из следующих условий:
1. Т\ хГ2 = КпхКп, п 2, в этом случае Т\ хГ2 — это сильно регулярный граф с параметрами (п2, 2п — 2, п — 2, 2);
2. Т\ х Г2 = Кп х К ,п 2, в этом случае Г і х Г2 — это граф Деза с параметрами (4п, 2п + 2, п — 2, 2);
5. Гі = ІІГП; n 2, и Г2 — граф Деза с параметрами (п , &,&, 0), в этом случае Гі х Г2 —это граф Деза с параметрами (пп! , /с, 6,0);
. Гі — град5 Деза с параметрами (п, &, 2, 0) и Г2 — град5 Деза с параметрами (п , А; , 2,0); в этом случае Г і х Г2 — это град5 Деза с параметрами (пп , к + А/, 2, 0).
Пусть Г — граф Деза (не обязательно точный) с матрицей смежности М. Если перестановкой строк матрицы М мы можем получить симметричную матрицу М , то М2 = МТМ = М тМ = М 2. Следовательно М также представляет граф Деза, имеющий те же параметры, что и граф Г. Используя эту идею, можно получать точные графы Деза из сильно регулярных графов.
Теорема 0.9 (Theorem 3.1, [42]). Пусть Г — сильно регулярный граф с параметрами (п, к, Л,/І) с к ф [і, \ф /І и с матрицей смежности М. Пусть Р — перестановочная матрица размера v х v, тогда РМ — матрица смежности графа Деза А с параметрами (п, к, тах{Л, /І}, тіп{А, /І}) тогда и только тогда, когда Р задает инволютивный автоморфизм графа Г, переставляющий только несмежные вершины. Кроме того А — точный граф Деза в том и только том случае, если Р ф I, Л О и /І ф 0.
Напомним определение схемы отношений Пусть X множество с п элементами и До, Ri, Rd — бинарные отношения, определенные на X. Пусть Ao,Ai,... , Ad — (0,1) матрицы соответствующие этим отношениям, то есть (ж, у) принимает значение 1 в матрице АІ, тогда и только тогда, когда (ж, у) Є Rj. Тогда (X, {Ri}f=o) называется симметричной схемой отношений с d классами, если
Пример 0.3. Дистанционно регулярный граф является графом Деза, если и только если выполняется одно из следующих условий: (i) d = 2 (граф сильно регулярный); (п) Л = 0 (гиперкубы и обобщения нечетных графов); (Ш) Л = /І (обобщенные многоугольники с реберным размером 3 и реберный граф графа Петерсена).
Теорема 0.10 (Theorem 4.2, [42]). Пусть (X, {Ri}f=0) — симметричная схема отношений иFc{l,2,...,(f}. Граф Г с матрицей смежности fep Af является графом Деза тогда и только тогда, когда сумма принимает не более двух значений при к, пробегающем {1, 2,..., d}.
Пример 0.4 (Example 4.3, [42]). В случае схемы отношений с тремя классами необходимо выполнение только одного условия, чтобы Г был графом Деза. Учитывая результаты Ван Дама [14], видим, что это довольно частый случай. В этом случае Г иногда сильно регулярный или дистанционно-регулярный граф диаметра 3 (что легко проверить), но в остальных случаях Г — точный граф Деза. Для примера рассмотрим псевдоциклическую схему отношений с тремя классами. Псевдоциклические схемы на 28 точках (существует две такие схемы, найденные Мэтоном и Холманом) дают точные графа Деза с параметрами (28,9,4,2) и (28,18,12,10), псевдоциклическая схема на 13 точках дает граф Деза с параметрами (13,8,5,4). В последнем примере псевдоциклическая схема в действительности циклическая, и поэтому граф может быть также получен как граф Кэли с помощью теоремы 0.5. Еще один пример можно получить из треугольного графа Т(8) с правильной раскраской Хоффмана, при этом вершины покрашены в семь цветов. Здесь объединение двух классов дает точный граф Деза с параметрами (28,15, 8,6).
Графы Мэтона M(2,q) и графы Мухаметьянова Гв и Tj .
Под графом Г мы понимаем пару (V, Е1), состоящую из конечного множества V = V(T), называемого множеством вершин (соответственно, элементы из V называются вершинами), и множества ребер Е = Е(Г) неупорядоченных пар вершин (называемых ребрами).
Таким образом, все графы, рассматриваемые в данной работе, являются неориентированными, конечными, без петель и кратных ребер. Последние два свойства означают, что в множестве Е отсутствуют пары вида {ж, ж}, где х Є У, и все элементы в множестве Е попарно различны.
Вершины ж, у называется смежными (соединенными ребром), если {ж, у} Є Е. В этом случае также вершина х называется соседом вершины у (и наоборот). Для указания смежности вершин ж, у мы пишем х у.
Под подграфом в графе мы понимаем вершинно-порожденный подграф, т.е. граф, множеством вершин которого является подмножество множества вершин исходного графа, при этом вершины в подграфе смежны, тогда и только тогда, когда они смежны в исходном графе.
В дальнейшем, если это не вызывает недоразумений, мы отождествляем обозначение графа и множества его вершин. Таким образом, выражение «х Є Г», где х — вершина, Г — граф, эквивалентно х Є 1 (Г).
Путём (или цепью) в графе называют конечную последовательность вершин жі, #2,... , ж/, в которой ХІ ХІ+І для всех і = 1,... , / — 1. Расстоянием между вершинами ж, у графа Г называется наименьшая длина пути, соединяющего ж, у в Г. Обозначим через d(x,y) = dr{x,y) расстояние между вершинами ж, у графа Г (положим d(x,y) = оо, если вершины ж, у принадлежат различным связным компонентам графа Г). Диаметр графа — это максимальное расстояние между парой вершин, возникающее в графе.
Для вершины х графа Г через ТІ(Х) обозначается подграф на множестве всех вершин, которые находятся на расстоянии і от вершины х. Подграф ТІ(Х) называется также г-той окрестностью вершины х в графе Г или сферой радиуса і с центром в х. Через Г(ж) обозначим Т\{х) (этот подграф называется окрестностью вершины ж в Г).
Граф называется полным, если любые две его вершины соединены ребром. Любой подграф графа Г, являющийся полным (и содержащий точно / вершин), называется кликой (/-кликой). Любой непустой подграф графа Г, не содержащий ребер (и содержащий точно с вершин), называется кокликой (с-кокликой).
Граф nxm-решетки определяется как граф с множеством вершин {(i, j) 1 і n, 1 j m}, в котором различные вершины (ii,ji) и (І2,Іг) смежны тогда и только тогда, когда і\ = і і или j\ = J2.
Матрицей смежности А = А(Т) графа Г на -и вершинах называется v х v матрица А = (a j), строки и колонки которой занумерованы вершинами графа Г, причем aij = 1, если г, j - смежные вершины и aij = 0, если г, j — несмежные вершины графа Г. Собственными значениями графа Г называются собственные значения его матрицы смежности А(Г).
Граф называется регулярными степени (валентности) к, если каждая его вершина имеет в точности к соседей, т.е. Уж Є Г имеем Г(ж) = к.
Граф называется сильно регулярным с параметрами если он содержит v вершин, является регулярным степени к, любая пара его смежных (соответственно, несмежных) вершин имеет точно А (соответственно, /І) общих соседей.
Очевидно, что при /І 0 диаметр сильно регулярного графа равен 2 (случай /І = 0 тривиален и далее не рассматривается). Существует множество необходимых ограничений на параметры сильно регулярного графа, см. [4]. Одно из самых простых получается следующим образом. В сильно регулярном графе зафиксируем вершину х и подсчитаем число ребер {у, z} таких, что х у и х ф z. Существует к способов выбрать вершину у, смежную с х. Теперь в качестве вершины z нам подходят все смежные с у вершины, кроме самой ж и Л вершин, смежных с х. Т.е. число таких ребер равно к (к — Л — 1). С другой стороны существует v — k — 1 способов выбрать вершину z, не смежную с х. Для несмежных вершин х и z существует /І вершин, смежных и с ж, исг. Таким образом, это же число ребер равно (v — к — 1)/І. Т.е. справедливо равенство:
Пусть А\ — матрица смежности сильно регулярного графа с параметрами (г , к, А, /І) при некоторой нумерации его вершин. Обозначим через Ач матрицу смежности дополнительного графа. Тогда A i = J—А\ — I. Из определения сильно регулярного графа имеем также следующие соотношения:
Данные матричные соотношения позволяют вычислить спектр матрицы А\, см. [3].
Теорема 1.1. Спектр сильно регулярного графа с параметрами (г ,&,А,/і) состоит из числа к (кратности 1) и чисел г, s (с кратностями /, д, соответственно), которые являются корнями квадратного уравнения х2 — (Л — fi)x — (k—fi) = 0. Кратности f,g вычисляются из соотношений l-\-f-\-g = v и k + rf + sg = 0. Доказательство. Подставив выражение для А% в уравнение для ( 4i)2, получим (А\) = (к — fi)I + (Л — fi)A\ + fiJ. (1) Хорошо известно, что валентность регулярного связного графа является его собственным значением с кратностью 1 и собственным вектором jv. Пусть v — собственный вектор А\, отвечающий собственному значению в фк. Тогда v_Ljw, поэтому Jv = 0. Умножив v на (1), получим квадратное уравнение из утверждения леммы. Теперь если r\s — корни этого уравнения, то Tr(Ai) = к + fr + sg = 0 и 1 + f + д = v, где f,g — кратности собственных значений г и s соответственно.й
Графы Деза, полученные из графов п х п-решетки
В этой главе мы изучаем вершинную связность (или, более точно, число вершинной связности) графов Деза. Вершинная связность графа является одной из его характеристик, интересных и с практической, и с теоретической точек зрения. Для отдельных классов графов известны оценки и точные результаты: например, вершинная связность / -регулярного графа Кэли не меньше (& + 1) (см. [39]), а вершинная связность дистанционно регулярного графа равна его валентности, как следует из работы Браувера и Кулена [40] (для сильно регулярных графов аналогичное утверждение доказано Браувером и Меснером в [41]).
Мы ограничимся рассмотрением одного класса графов Деза, которые могут быть получены из сильно регулярных графов с помощью конструкции, описанной в теореме 0.9). Естественно было бы ожидать, что вершинная связность графов Деза также равна их валентности. Основным результатом главы является следующая теорема.
Теорема 3.1. Пусть А — граф Деза, полученный из сильно регулярного графа Г с помощью теоремы 0.9. Пусть Г имеет неглавные собственные значения г, s. Тогда имеет место один из следующих трех случаев:
В отличие от дистанционно или сильно регулярных графов для графов Деза невозможно в общем случае вычислить спектр их матриц смежности (т. е. выразить собственные значения как функции от параметров графа). Данное обстоятельство существенно усложняет исследование этого класса графов. Для графов Деза, полученных из сильно регулярных графов, мы можем определить некоторую информацию о спектре, что позволяет частично использовать рассуждения из работы [41].
Глава организована следующим образом. В разделе 3.1 мы напоминаем необходимые определения и вспомогательные результаты. В разд. 3.2 приведено доказательство теоремы. В заключении главы обсуждается случай (3) из теоремы.
Вспомогательные результаты Для графа Г и произвольной его вершины х определим обозначим х1- := {х} U Г(ж), где Г(ж) — окрестность вершины х. Вершинной связностью к(Г) графа Г называется наименьшее число вершин, после удаления которых граф Г становится несвязным. Легко понять, что в регулярном валентности к графе Г число к(Г) не превосходит к. Утверждение 3.1 ( [3, теорема 1.3.1]). Пусть Г - нетривиальный (т.е. неполный и связный) сильно регулярный граф с параметрами (-и, к, А, /І). Тогда (1) Граф Г имеет три различных собственных значения к г 0 s, последние два из которых удовлетворяют квадратному уравнению х2 + (р — Х)х + (/І — к) = 0. (2) Если собственные значения г и s имеют одинаковые кратности, то г, s = (—1 ± Л/У)/2. В противном случае числа г, s целые. (3) Верны равенства /І = k + rs А = /І + г + s. В данной главе мы изучим вершинную связность графов Деза, способ получения которых из сильно регулярных графов описан в теореме 0.9. Обозна чим рассматриваемый в этой теореме класс графов Деза через Т . Множество графов Деза, полученных с помощью автоморфизма порядка 2 из сильно регулярного графа Г, обозначим через Т {Г).
Таким образом, мы рассматриваем графы Деза, получаемые из сильно регулярных графов с помощью автоморфизма порядка 2.
Замечание 2. Окрестности вершин в графе А Є Т (Т) (в обозначениях теоремы 0.9) как множества вершин устроены следующим образом. Если вершина ж Є Г сдвигается под действием автоморфизма Р и хр — ее образ, то А(х) = Т(хр), т. е. вершина х смежна со всеми вершинами из окрестности своего образа. Если же х = хр, то А(х) = Г(ж).
Нам понадобятся два следующих хорошо известных результата из теории графов. Утверждение 3.2 ( [3, теорема 3.12.4]). Сильно регулярный граф с наименьшим собственным значением —2 является одним из следующих графов: (1) полный многодольный граф с долями порядка 2; (2) граф п х п-решетки с параметрами (п2, 2(п — 1),п — 2, 2); (3) треугольный графТ{п) с параметрами (п(п —1)/2,2(п —2),п —2,4); (4) граф Шрикханде с параметрами 4 х 4-решетки; (5) один из трех графов Чанга с параметрами Т(8); (6) граф Петерсена с параметрами (10,3,0,1); (7) граф Клебша с параметрами (16,10,6,6); (8) граф Шлефли с параметрами (27,16,10,8); Пусть ж, у — две различные вершины связного графа Г. Две простые цепи, соединяющие х и у, называются непересекающимися, если у них нет общин вершин, отличных от ж, у. Множество S вершин разделяет х и у, если х и у принадлежат различным компонентам связности графа \S. Следующий результат известен как теорема Менгера.
Утверждение 3.3 (Теорема 5.9, [43]). Минимальная мощность множества, разделящего несмежные вершины х и у, равна наибольшему количеству непересекающихся цепей, соединяющих эти вершины.
Вершинная связность графов Деза из класса V 3.2.1 Сведение задачи к трем случаям В этом разделе мы покажем, что за исключением трех случаев, которые потребуют отдельного изучения (см. пункты 3.2.2, 3.2.3 и 3.2.4), вершинная связность графов Деза из класса Т равна их валентности.
Доказательство следующего предложения аналогично доказательству теоремы Браувера и Меснера (см. [41]) и существенно использует возможность вычисления собственных значений графа Деза из V.
Утверждение 3.4. Пусть Є Т () — связный граф Деза, а сильно регулярный граф имеет неглавные собственные значения г, s, где г 0 и s 0. Тогда имеет место по крайней мере один из следующих двух случаев: (1) вершинная связность равна его валентности, а наименьшее разделяющее множество является окрестностью какой-либо вершины; (2) s = —2 или г 2.
Доказательство. Мы придерживаемся обозначений из теоремы 0.9. Поскольку матрица М смежности сильно регулярного графа имеет три различных собственных значения Й 0 Г А;и М2 = D2, где D — матрица смежности графа , то D может иметь собственные значения лишь из множества {±k,±r,±s}.
Графы и связны и регулярны валентности к, поэтому матрицы М и D имеют собственное значение к кратности 1. Отсюда —к не является собствен ным значением D (так как сумма размерностей собственных подпространств с собственными значениями к и —к матрицы D равна размерности собственного подпространства с собственным значением к матрицы М).
Пусть S — наименьшее разделяющее множество графа А, т. е. \S\ = к(Д) к, А и В — компоненты связности, остающиеся после удаления S. Допустим, что \А\ 1 и \В\ 1, т. е. S не является окрестностью некоторой вершины. Поскольку спектр несвязного графа является объединением спектров компонент связности, то спектр $i 02 ... 0v-\s\ графа A\J В будет объединением спектров о"1 о"2 ... (J\A\ и 6o i бо 2 ш\в\ графов А и В соответственно.
Граф A U В является индуцированным подграфом графа А, и по теореме о переплетении спектров [3, Теорема 3.3.1] второе по величине собственное значение 02 графа A U В не превосходит второго по величине собственного значения графа А, т. е. числа/; = max(r, —s). Очевидно, что 02 min{a"i,6o i}. Поскольку наибольшее собственное значение в любом графе больше или равно средней степени вершины [3, лемма 3.2.1], то, не теряя общности, можно считать, что в графе В средняя степень вершины не превосходит t.
Нумерация подмножеств элементов групп
Среди найденных наборов параметров, для двух существуют сильно регулярные графы с такими наборами параметров. (15,6,3,1) — параметры дополнения к треугольному графу Т(6), (16,9,6,4) — параметры дополнения к решетке Ь(4), значит, можно получить точные графы Деза из этих сильно регулярных графов, пользуясь теоремой 0.9. Для графа Т(6), с точностью до нумерации вершин, существует единственный автоморфизм, и с помощью этого автоморфизма можно получить найденный нами с помощью программы точный граф Деза. Для L(4), с точностью до нумерации вершин, существуют (см. [46]) два автоморфизма, и с их помощью, используя теорему 0.9, можно построить оба точных графа Деза, найденных программным путем.
Утверждение 0.6 дает простой критерий существования графов с наборами параметров определенного вида. В частности, если существуют х и у, такие, что параметры графа (2ху, 1 + 2у(х — 1), 2у(х — 1), 2у(х — 2) + 2), то существует единственный (с точностью до изоморфизма) граф Деза с такими параметрами, и его строение описано в примере 0.1. Из найденных нами наборов параметров под это условие подходят только два: (16,9,8,2) (х = 2, у = 4) и (16,13,12,10) (х = 4,у = 2).
Для построения графов с использованием теоремы 0.5 (т.е. как графов Кэли некоторой группы) была написана программа, перебирающая системы образующих.
Ниже используются следующие обозначения групп: С\ — циклическая группа порядка 16, D\ — группа диэдра порядка 16, С4 х С4 — прямое про изведение двух циклических, QD\Q — полудиэдральная группа порядка 16. Следующая таблица содержит описание того, какие из найденных точных графов Деза являются графами Кэли.
В данной главе с помощью компьютерного перебора были найдены матрицы смежности всех попарно неизоморфных точных графов Деза, имеющих 14, 15 или 16 вершин. Более того, все найденные точные графы Деза удалось построить с использованием теоретических конструкций, заметим что для этого оказалось достаточно конструкций 0.5 и 0.9. Отметим, что при дальнейшем увеличении числа вершин сложность перебора значительно возрастает. Также отметим, что большинство найденных графов являются графами Кэли. В следующей главе, развивая результаты данной главы, мы сузим класс точных графов Деза и сосредоточимся на изучении точных графов Деза, которые являются графами Кэли. 5 Кэли-Деза графы, имеющие менее 60 вершин
В этой главе мы начинаем изучение графов Деза, которые являются графами Кэли. В работах [33-36] были исследованы некоторые свойства дистанционно-регулярных и сильно регулярных графов, которые являются графами Кэли. В частности, получена классификация сильно регулярных графов Кэли циклических и диэдральных групп.
В данной главе с помощью компьютерного перебора найдены все точные графы Деза, являющиеся графами Кэли и имеющие менее 60 вершин.
Глава организована следующим образом. В разделе 5.1 мы напоминаем основные определения и результаты. В разделе 5.2 мы описываем алгоритм работы программы и обосновываем его корректность. В разделе 5.3 приводятся результаты работы программы. Данные организованы в виде двух таблиц. В первой таблице для каждой группы порядка менее 60 указан список неизоморфных Кэли-Деза графов этой группы. Во второй таблице для каждого Кэли-Деза графа с числом вершин менее 60 указан список групп, графом Кэли которых он является.
Пусть G — группа и D С G. Определим D l как множество {d l : d Є D}. Пусть Г — граф, множество вершин которого — все элементы группы G, и вершины и и v смежны тогда и только тогда, когда v lu Є D. Если единица группы G не содержится в D и D l = D, то Г называется графом Кэли группы G по системе образующих D и обозначается Cay(G,D).
Подмножества элементов D и D группы G называются изоморфными, если найдется ф Є Aut(G), что ф{р) = D . Если подмножества D и D изоморфны, то изоморфны и графы Cay(G,D) и Cay(G,D ). Заметим, что обратное не верно, т.е. из двух неизоморфных систем образующих могут быть получе ны изоморфные графы Кэли. Группы, для которых из изоморфизма графов Кэли следует изоморфизм их систем образующих, называются СI-группами. Вопросы изоморфизма графов Кэли обсуждаются в [37], [38].
Графом Кэли-Деза будем называть граф Кэли, являющийся графом Деза. В данной главе с помощью компьютерного перебора получены все неизоморфные Кэли-Деза графы диаметра 2, имеющие менее 60 вершин. Поиск осуществлялся следующим образом: были найдены все неизоморфные системы образующих, для каждой из которой проверялось условие теоремы 5.1. Ввиду замечания о С/-группах среди полученных графов могут оставаться изоморфные, поэтому все полученные Кэли-Деза графы с одинаковыми параметрами были проверены на изоморфизм. Таким образом, в результате работы получен список всех неизоморфных Кэли-Деза графов, имеющих менее 60 вершин.
На первом шаге с помощью системы компьютерной алгебры GAP [50] получены все таблицы Кэли групп, имеющих порядок менее 60. Для каждой группы вычисляется группа автоморфизмов, которая представлена в виде перестановок на множестве элементов исходной группы. 5.2.2 Нумерация подмножеств элементов групп
Пусть G - группа, элементы которой занумерованы так же, как в системе GAP. Для произвольного элемента д Є G обозначим через пит(д) номер элемента д в нумерации GAP.
Сопоставим каждому подмножеству элементов группы G двоичное число по следующему правилу: г-й разряд двоичного числа равен 1, если элемент группы с номером і входит в подмножество; и равен 0 в противном случае. Теперь на семействе подмножеств элементов группы G естественным образом возникает отношение порядка(при сравнении двух подмножеств сравниваются соответствующие им числа).
Для каждой системы образующих D С G определим множество D следующим образом: элемент х Є D лежит в D тогда и только тогда, когда номер элемента х больше либо равен номеру элемента ж-1, т.е. пит(х) пит{х 1).
Доказательство. Пусть х — элемент с наименьшим номером, который лежит в D\ и не лежит в D2. Тогда пит{х 1) пит{х). Следовательно, х Є D\ и х ф D2. Каждый элемент с номером, большим чем у элемента ж, лежит или не лежит в множествах D\ и D2 одновременно,
Процесс перебора является рекурсивным. Основным шагом перебора является формирование новой системы образующих из уже построенной с помощью добавления к ней элемента группы (вместе с обратным), при этом номер добавляемого элемента меньше наименьшего из номеров уже присутствующих элементов. В качестве базовой системы порождающих выберем пустое множество. Очевидно, что если мы будем всевозможным образом расширять это множество, то общность перебора будет достигнута. Мы строим корневое дерево, вершинами которого являются все неизоморфные системы образующих, максимальные в своих орбитах под действием группы автоморфизмов. Слой дерева с номером і состоит из упорядоченных по возрастанию систем образующих Dij таких, что \Dij\ = і (j обозначает порядковый номер). Корню дерева соответствует пустая система образующих. Определим для каждой системы образующих D подмножество I(Dij) элементов группы, обладающее следующими свойствами:
