Сильно регулярный граф — вариация понятия регулярный граф.
Определение
Пусть — регулярный граф с вершинами и степенью . Говорят, что является сильно регулярным, если существуют целые и такие, что:
Любые две смежные вершины имеют общих соседей.
Любые две несмежные вершины имеют общих соседей.
Замечания
Графы описанного типа иногда обозначаются как .
Некоторые авторы исключают графы, которые удовлетворяют условиям тривиально, а именно графы, являющиеся несвязным объединением одного или более полных графов одного размера , и их дополнения, графы Турана.
Свойства
Сильно регулярный граф является дистанционно-регулярным с диаметром , только в том случае, когда .
Четыре параметра в не являются независимыми и должны удовлетворять следующему условию:
Это условие можно получить очень просто, если подсчитать аргументы следующим образом:
Представим вершины графа лежащими на трёх уровнях. Выберем любую вершину как корень, уровень . Тогда её соседних вершин лежат на уровне , а все оставшиеся лежат на уровне . Вершины уровня связаны непосредственно с корнем, а потому они должны иметь других соседей, являющихся соседями корня, и эти соседи должны также лежать на уровне . Поскольку каждая вершина имеет степень , имеется рёбер, соединяющих каждую вершину уровня с уровнем . Вершины уровня не связаны непосредственно с корнем, а потому они должны иметь общих соседей с корнем, и все эти соседи должны лежать на уровне . Таким образом, вершин уровня связаны с каждой вершиной уровня и каждая из вершин на уровне 1 связана с вершин на уровне . Получаем, что число вершин на уровне равно . Полное число вершин на всех трёх уровнях, таким образом, равно и после преобразования, получим .
Пусть обозначает единичную матрицу (порядка ) и пусть обозначает матрицу, все элементы которой равны . Матрица смежности сильно регулярного графа имеет следующие свойства: (Это тривиальное перефразирование требования равенства степени вершин числу ). (Первый член, , даёт число двухшаговых путей из любой вершины ко всем вершинам. Второй член, , соответствует непосредственно связанным рёбрам. Третий член,, соответствует тривиальным парам, когда вершины в паре те же самые).
Граф имеет в точности три собственных значения: , которого равна 1 , кратность которого равна , кратность которого равна
Сильно регулярные графы, для которых , называются конференсными ввиду их связи с симметричными конференсными матрицами. Число независимых параметров этих графов сокращается до одного — .
Сильно регулярные графы, для которых , имеют целочисленные собственные значения с неравными кратностями.
Дополнение также сильно регулярно — это .
Примеры — Цикл длины 5; — Граф Петерсена; — Граф Клебша; — Граф Шрикханде , который не является дистанционно-транзитивным; — Рёберный граф обобщённого четырёхугольника ; — Граф Шлефли ; — Графы Чана; — Граф Хоффмана-Синглтона; — Граф Гевирца; — Граф M22; — Граф Брауэра — Хемерса; — Граф Хигмана — Симса; — ; — Граф Пэли порядка ; — квадратный ладейный граф .
Сильно регулярный граф называется простым, если и граф, и его дополнение связны. Все вышеприведённые графы просты, так как в противном случае или .
Графы Мура Сильно регулярные графы с не содержат треугольников. Кроме полных графов с числом вершин меньше 3 и всех полных двудольных графов семь приведённых выше — это все известные графы этого вида. Сильно регулярные графы с и являются графами Мура с обхватом 5. Опять, три графа, приведённые выше, с параметрами , и , являются единственными известными графами этого вида. Единственное другое возможное множество параметров, соответствующее графам Мура — это . Неизвестно, существует ли такой граф, и если существует, единственный ли он.
См. также
Примечания
Литература
Ссылки Eric W. Weisstein, Статья Mathworld с большим числом примеров. , Список больших графов и семейств. , Параметры сильно регулярных графов. , Коллекция графов. Ted Spence, Strongly regular graphs on at most 64 vertices.
Категория:Алгебраическая теория графов Категория:Семейства графов Категория:Регулярные графы