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

В теории графов сильно регулярным графом называется граф, обладающий следующими свойствами:

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

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

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

Графы такого вида иногда обозначаются как s r g ( v , k , λ , μ ) {displaystyle srg(v,k,lambda ,mu )} .

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

Сильно регулярный граф является дистанционно-регулярным с диаметром 2 {displaystyle 2} , но только в том случае, когда μ {displaystyle mu } не равно нулю.

Свойства

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

( v − k − 1 ) μ = k ( k − λ − 1 ) {displaystyle (v-k-1)mu =k(k-lambda -1)}

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

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

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

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

• Сильно регулярные графы, для которых 2 k + ( v − 1 ) ( λ − μ ) = 0 {displaystyle 2k+(v-1)(lambda -mu )=0} , называются конференсными ввиду их связи с симметричными конференсными матрицами. Число независимых параметров этих графов сокращается до одного — s r g ( v , v − 1 2 , v − 5 4 , v − 1 4 ) {displaystyle srgleft(v,{frac {v-1}{2}},{frac {v-5}{4}},{frac {v-1}{4}} ight)} .

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

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

Примеры

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

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

Графы Мура

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