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

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

Сильно регулярный граф — вариация понятия регулярный граф.

Определение

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

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

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

Замечания

• Графы описанного типа иногда обозначаются как $srg(v,k,\lambda ,\mu )$.

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

Свойства

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

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

$(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)$.

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

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

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

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

• Дополнение $srg(v,k,\lambda ,\mu )$ также сильно регулярно — это $srg(v,v-k-1,v-2-2k+\mu ,v-2k+\lambda )$.

Примеры

• $srg(5,2,0,1)$ — Цикл длины 5;
• $srg(10,3,0,1)$ — Граф Петерсена;
• $srg(16,5,0,2)$ — Граф Клебша;
• $srg(16,6,2,2)$ — Граф Шрикханде , который не является дистанционно-транзитивным;
• $srg(27,10,1,5)$ — Рёберный граф обобщённого четырёхугольника $GQ(2,4)$;
• $srg(27,16,10,8)$ — Граф Шлефли ;
• $srg(28,12,6,4)$ — Графы Чана;
• $srg(50,7,0,1)$ — Граф Хоффмана-Синглтона;
• $srg(56,10,0,2)$ — Граф Гевирца;
• $srg(77,16,0,4)$ — Граф M22;
• $srg(81,20,1,6)$ — Граф Брауэра — Хемерса;
• $srg(100,22,0,6)$ — Граф Хигмана — Симса;
• $srg(162,56,10,24)$ — Шаблон:Не переведено 5;
• $srg(q,\frac{q-1}{2},\frac{q-5}{4},\frac{q-1}{4})$ — Граф Пэли порядка $q$;
• $srg(n^2,2n-2,n-2,2)$ — $n\times n$ квадратный ладейный граф .

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

Графы Мура

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

См. также

• Шаблон:Не переведено 5

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Eric W. Weisstein, Статья Mathworld с большим числом примеров.
• Шаблон:Не переведено 5, Список больших графов и семейств.
• Шаблон:Не переведено 5, Параметры сильно регулярных графов.
• Шаблон:Не переведено 5, Коллекция графов.
• Ted Spence, Strongly regular graphs on at most 64 vertices.