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

Граф Пэли 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 )\neq 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).
• Граф Пэли порядка 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.