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

Определение

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

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

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

Замечания

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

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

Свойства

• Сильно регулярный граф ${\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)}$ — Граф Шлефли ;
• ${\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)}$ . Неизвестно, существует ли такой граф, и если существует, единственный ли он.

См. также

Примечания

Литература

• 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 ,
• ,
• ,
• ,
• Ted Spence,