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

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

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

Определение

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

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

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

Замечания

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

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

Свойства

• Сильно регулярный граф $srg(v,k,\lambda ,\mu )$ является дистанционно-регулярным с диаметром $2$, только в том случае, когда $\mu \neq 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)$.

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

См. также

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

Литература

• Brouwer A.E., Cohen A.M., Neumaier A. Distance Regular Graphs (англ.). — Berlin, New York: Springer-Verlag, 1989. — ISBN 3-540-50619-5.
• Brouwer A.E., Haemers W.H. Spectra of Graphs (англ.). — New York: Springer-Verlag, 2012. — Vol. 418. — (Universitext). — ISBN 978-1-4614-1938-9.
• Godsil C., Royle G. Algebraic Graph Theory (англ.). — New York: Springer-Verlag, 2001. — ISBN 0-387-95241-1.

Ссылки

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