Сильно регулярный граф

Граф Пейли 13-го порядка, сильно регулярный граф с параметрами srg(13,6,2,3).

В теории графов сильно регулярным графом называется граф, обладающий следующими свойствами.

Пусть G = (V,E) — регулярный граф с v вершинами и степенью k. Говорят, что G является сильно регулярным, если существуют целые λ и μ такие, что:

• Любые две смежные вершины имеют λ общих соседей.

• Любые две несмежные вершин имеют μ общих соседей.

Графы такого вида иногда обозначаются как srg(v,k,λ,μ).

Некоторые авторы исключают графы, которые удовлетворяют условиям тривиально, а именно, графы, являющиеся несвязным объединением одного или более полных графов одного размера,, и их дополнения, графы Турана.

Сильно регулярный граф является дистанционно-регулярным с диаметром 2, но только в том случае, когда μ не равно нулю.

Свойства

• Четыре параметра в srg(v,k,λ,μ) не являются независимыми и должны удовлетворять следующему условию:

$(v-k-1)\mu = k(k-\lambda-1)$

Это условие можно получить очень просто, если подсчитать аргументы следующим образом:

• • Представим вершины графа лежащими на трёх уровнях. Выберем любую вершину как корень, уровень 0. Тогда её k соседних вершин лежат на уровне 1, а все оставшиеся лежат на уровне 2.
  • Вершины уровня 1 связаны непосредственно с корнем, а потому они должны иметь $\lambda$ других соседей, являющихся соседями корня, и эти соседи должны также лежать на уровне 1. Поскольку каждая вершина имеет степень k, имеется $k-\lambda-1$ рёбер, соединяющих каждую вершину уровня 1 с уровнем 2.
  • Вершины уровня 2 не связаны непосредственно с корнем, а потому они должны иметь $\mu$ общих соседей с корнем, и все эти соседи должны лежать на уровне 1. Таким образом, $\mu$ вершин уровня 1 связаны с каждой вершиной уровня 2 и каждая из k вершин на уровне 1 связана с $k-\lambda-1$ вершин на уровне 2. Получаем, что число вершин на уровне 2 равно $k(k-\lambda-1)/\mu$.
  • Полное число вершин на всех трёх уровнях, таким образом, равно $v = 1 + k + k(k-\lambda-1)/\mu$ и после преобразования, получим $(v-k-1)\mu = k(k-\lambda-1)$.

• Пусть I обозначает единичную матрицу (порядка v) и пусть J обозначает матрицу, все элементы которой равны 1. Матрица смежности A сильно регулярного графа имеет следующие свойства:
  • $AJ = kJ$
    (Это тривиальное перефразирование требования равенства степени вершин числу k).
  • ${A}^{2} + (\mu-\lambda){A} + (\mu-k){I} = \mu {J}$
    (Первый член, ${A}^{2}$, даёт число двухшаговых путей из любой вершины ко всем вершинам. Второй член,$(\mu-\lambda){A}$, соответствует непосредственно связанным рёбрам. Третий член,$(\mu-k){I}$, соответствует тривиальным парам, когда вершины в паре те же самые).

• Граф имеет в точности три собственных значения:
  • $k$, кратность которого равна 1
  • $\frac{1}{2}\left[(\lambda-\mu)+\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right]$, кратность которого равна $\frac{1}{2} \left[(v-1)-\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]$
  • $\frac{1}{2}\left[(\lambda-\mu)-\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right]$, кратность которого равна $\frac{1}{2} \left[(v-1)+\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]$

• Сильно регулярные графы, для которых $2k+(v-1)(\lambda-\mu) = 0$, называются конференсными ввиду их связи с симметричными конференсными матрицами. Число независимых параметров этих графов сокращается до одного — $srg\left(v, \frac{v-1}{2}, \frac{v-5}{4}, \frac{v-1}{4}\right)$.

• Сильно регулярные графы, для которых $2k+(v-1)(\lambda-\mu) \ne 0$, имеют целочисленные собственные значения с неравными кратностями.

• Дополнение srg(v,k,λ,μ) также сильно регулярно — это srg(v, v−k−1, v−2−2k+μ, v−2k+λ).

Примеры

• Цикл длины 5 — это srg(5,2,0,1).
• Граф Петерсена — это srg(10,3,0,1).
• Граф Клебша — это srg(16,5,0,2).
• Граф Шрикханде — это srg(16,6,2,2), который не является дистанционно-транзитивным.
• Рёберный граф обобщённого четырёхугольника GQ(2,4) — это srg(27,10,1,5).
• Граф Шлефли — это srg(27,16,10,8).
• Графы Чанга — это srg(28,12,6,4).
• Граф Хофмана–Синглтона — это srg(50,7,0,1).
• Граф Симса–Гевиртца — это (56,10,0,2).
• Граф M22 — это srg(77,16,0,4).
• Граф Браувера–Хамерса — это srg(81,20,1,6).
• Граф Хигмана–Симса — это srg(100,22,0,6).
• Локальный граф МакЛафлина — это srg(162,56,10,24).
• Граф Пейли of order q — это srg(q, (q − 1)/2, (q − 5)/4, (q − 1)/4).
• n × n квадратный ладейный граф — это srg(n², 2n − 2, n − 2, 2).

Сильно регулярный граф называется простым, если и граф, и его дополнение связны. Все вышеприведённые графы просты, так как в противном случае μ=0 или μ=k.

Графы Мура

Сильно регулярные графы с λ=0 не содержат треугольников. Кроме полных графов с числом вершин меньше 3 и всех полных двудольных графов семь приведённых выше — это все известные графы этого вида. Сильно регулярные графы с λ=0 и μ=1 являются графами Мура с обхватом 5. Опять, три графа, приведённые выше, с параметрами (5,2,0,1), (10,3,0,1) и (50,7,0,1), являются единственными известными графами этого вида. Единственное другое возможное множество параметров, соответствующее графам Мура — это (3250,57,0,1). Неизвестно, существует ли такой граф, и если существует, единственный ли он.

Смотрите также

• Матрица смежности Зайделя

Ссылки

• A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5
• Chris Godsil and Gordon Royle (2004), Algebraic Graph Theory. New York: Springer-Verlag. ISBN 0-387-95241-1

Внешние ссылки

• Эрик В. Вайсштайн, Статья Mathworld с большим числом примеров.
• Гордон Ройл, Список больших графов и семейств.
• Andries E. Brouwer, Параметры сильно регулярных графов.
• Brendan McKay, Коллекция графов.
• Ted Spence, Strongly regular graphs on at most 64 vertices.