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

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

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

Определение

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

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

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

Замечания

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

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

Свойства

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

• Четыре параметра в ${\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}$.

Графы Мура

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

См. также

• Матрица смежности Зайделя^[англ.]

Примечания

1. Brouwer, 2012, с. 101.
2. Godsil, 2001, с. 218.
3. Weisstein, Eric W. Schläfli graph (англ.) на сайте Wolfram MathWorld.

Литература

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