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

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

Определение

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

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

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

Замечания

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

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

Свойства

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

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

[math]\displaystyle{ (v-k-1)\mu = k(k-\lambda-1) }[/math]

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

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

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

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

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

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

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

Примеры

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

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

Графы Мура

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

См. также

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

Примечания

↑ Brouwer, 2012, с. 101.
↑ Godsil, 2001, с. 218.
↑ 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.

Ссылки

[_3bd1122ea54ab312-1] Brouwer, 2012, с. 101.

[_d1c6f86a89f794b9-2] Godsil, 2001, с. 218.

[3] Weisstein, Eric W. Schläfli graph (англ.) на сайте Wolfram MathWorld.

[1]

[2]

[3]