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

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

${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$

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

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

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

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

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

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

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

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

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

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

• 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.