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

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

Семейства графов, определенные своими автоморфизмами
дистанционно-транзитивный	→	дистанционно-регулярный	←	сильно регулярный
↓
симметричный (дугопереходный)	←	t -транзитивен, t ≥ 2		кососимметричный
↓
(если подключен) вершинно- и реберно-транзитивен	→	реберно-транзитивный и регулярный	→	краево-транзитивный
↓		↓		↓
вершинно-транзитивный	→	обычный	→	(если двусторонний) бирегулярный
↑
Граф Кэли	←	нуль-симметричный		асимметричный

В теории графов ( сильно регулярный граф SRG ) — это регулярный граф G = ( V , E ) с v вершинами и степенью k такой, что для некоторых заданных целых чисел $\lambda ,\mu \geq 0$

• каждые две соседние вершины имеют λ общих соседей, и
• каждые две несмежные вершины имеют μ общих соседей.

Такой сильно регулярный граф обозначается srg( v , k , λ, µ) ; его «параметрами» являются числа в ( v , k , λ, µ). Его граф дополнений также сильно регулярен: это srg( v , v − k − 1, v − 2 − 2 k + µ, v − 2 k + λ) .

Сильно регулярный граф — это дистанционно регулярный граф с диаметром 2, если µ не равно нулю. Это локально линейный граф, если λ = 1 .

Этимология

обозначается как srg( v , k Сильно регулярный граф в литературе , λ, µ). По соглашению графы, тривиально удовлетворяющие этому определению, исключаются из детальных исследований и списков сильно регулярных графов. одинакового размера К ним относятся несвязное объединение одного или нескольких полных графов , и их дополнения — полные многодольные графы с независимыми множествами одинакового размера.

Андрис Брауэр и Хендрик ван Мальдегем (см. #Ссылки ) используют альтернативное, но полностью эквивалентное определение сильно регулярного графа, основанное на теории спектральных графов : сильно регулярный граф — это конечный регулярный граф, который имеет ровно три собственных значения, только одно из которых равно до степени k кратности 1. Это автоматически исключает полносвязные графы (которые имеют только два различных собственных значения, а не три) и несвязные графы (для которых кратность степени k равна числу различных компонент связности, которые следовательно, будет превышать единицу). Большая часть литературы, включая Брауэра, называет большее собственное значение r (с кратностью f ), а меньшее — s (с кратностью g ).

История

Сильно регулярные графы были введены Р. К. Бозе в 1963 году. Они основывались на более ранних работах 1950-х годов в новой на тот момент области теории спектральных графов .

Примеры

• Цикл . длины 5 — это srg(5, 2, 0, 1)
• Граф Петерсена представляет собой srg(10, 3, 0, 1).
• Граф Клебша представляет собой srg(16, 5, 0, 2).
• Граф Шрикханде — это srg(16, 6, 2, 2), который не является дистанционно-транзитивным графом .
• Граф размера n × n квадратных ладей , т. е. линейный граф сбалансированного полного двудольного графа K _{n , n} , представляет собой srg( n ² , 2 n - 2, n - 2, 2). Параметры для n = 4 совпадают с параметрами графа Шрикханде, но эти два графа не изоморфны.
• Линейный график полного графа K _n — это ${\textstyle \operatorname {srg} \left({\binom {n}{2}},2(n-2),n-2,4\right)}$.
• Графы Чанга — это srg(28, 12, 6, 4), такие же, как линейный граф K ₈ , но эти четыре графа не изоморфны.
• Каждый обобщенный четырехугольник порядка (s, t) дает srg((s + 1)(st + 1), s(t + 1), s − 1, t + 1) в качестве линейного графика . Например, GQ(2, 4) дает srg(27, 10, 1, 5) в качестве линейного графика.
• Граф Шлефли представляет собой srg(27, 16, 10, 8).
• Граф Хоффмана – Синглтона представляет собой srg(50, 7, 0, 1).
• Граф Симса-Гевирца представляет собой (56, 10, 0, 2).
• Граф M22, также известный как граф Меснера, представляет собой srg(77, 16, 0, 4).
• Граф Брауэра-Хемерса представляет собой srg(81, 20, 1, 6).
• Граф Хигмана-Симса представляет собой srg(100, 22, 0, 6).
• Локальный граф Маклафлина представляет собой srg(162, 56, 10, 24).
• Граф Кэмерона представляет собой srg(231, 30, 9, 3).
• Граф Берлекампа –ван Линта–Зейделя представляет собой srg(243, 22, 1, 2).
• Граф Маклафлина представляет собой srg(275, 112, 30, 56).
• Граф Пэли порядка q представляет собой srg( q , ( q − 1)/2, ( q − 5)/4, ( q − 1)/4). Самый маленький граф Пэли с q = 5 — это 5-цикл (см. выше).
• самодополняющие дуготранзитивные графы сильно регулярны.

Сильно регулярный граф называется примитивным , если и граф, и его дополнение связны. Все приведенные выше графы примитивны, так как в противном случае µ = 0 или λ = k .

Задача Конвея о 99 графах требует построения srg(99, 14, 1, 2). Неизвестно, существует ли график с такими параметрами, а Джон Хортон Конвей предложил за решение этой проблемы приз в 1000 долларов.

Графики без треугольников

Сильно регулярные графы с λ = 0 не содержат треугольников . Помимо полных графов с числом менее трех вершин и всех полных двудольных графов, известны только семь перечисленных ранее графов (пятиугольник, Петерсен, Клебш, Хоффман-Синглтон, Гевирц, Меснер-М22 и Хигман-Симс).

Геодезические графики

Любой сильно регулярный граф с $\mu =1$ — геодезический граф , граф, в котором каждые две вершины имеют уникальный невзвешенный кратчайший путь . Единственные известные сильно регулярные графы с $\mu =1$ это те, где $\lambda$ равно 0, следовательно, также не содержит треугольников. Они называются графами Мура и более подробно рассматриваются ниже . Другие комбинации параметров, такие как (400, 21, 2, 1), пока не исключены. Несмотря на продолжающиеся исследования свойств, которые сильно регулярный граф с $\mu =1$ бы, неизвестно, существуют ли еще какие-либо и даже конечно ли их число. Известен только элементарный результат: $\lambda$ не может быть 1 для такого графа.

графов

Базовая связь между параметрами

Четыре параметра в srg( v , k , λ, µ) не являются независимыми. Они должны подчиняться следующему соотношению:

$(v-k-1)\mu =k(k-\lambda -1)$

Вышеупомянутое соотношение получается с помощью аргумента подсчета следующим образом:

1. Представьте себе, что вершины графа лежат на трех уровнях. Выберите любую вершину в качестве корня на уровне 0. Тогда ее k соседей лежат на уровне 1, а все остальные вершины лежат на уровне 2.
2. Вершины на уровне 1 напрямую связаны с корнем, следовательно, они должны иметь λ других общих соседей с корнем, и эти общие соседи также должны находиться на уровне 1. Поскольку каждая вершина имеет степень k , существуют $k-\lambda -1$ ребра, оставшиеся для каждого узла уровня 1 для соединения с вершинами уровня 2. Следовательно, существуют $k(k-\lambda -1)$ границы между уровнем 1 и уровнем 2.
3. Вершины на уровне 2 не связаны напрямую с корнем, следовательно, они должны иметь μ общих соседей с корнем, и все эти общие соседи должны находиться на уровне 1. Существуют $(v-k-1)$ вершин на уровне 2, и каждая соединена с µ вершинами на уровне 1. Следовательно, количество ребер между уровнями 1 и уровнем 2 равно $(v-k-1)\mu$.
4. Приравнивая два выражения для ребер между уровнем 1 и уровнем 2, получаем следующее соотношение.

матрицы

Пусть I обозначает единичную матрицу , а J обозначает матрицу единиц , обе матрицы порядка v . Матрица смежности A сильно регулярного графа удовлетворяет двум уравнениям.

Первый:

$AJ=JA=kJ,$

что является повторением требования регулярности. Это показывает, что k является собственным значением матрицы смежности с собственным вектором, состоящим из всех единиц.

Второй:

$A^{2}=kI+\lambda {A}+\mu (J-I-A)$

что выражает сильную закономерность. ij - й элемент левой части дает количество двухшаговых путей от i до j . Первый член правой части дает количество двухшаговых путей от i обратно к i , а именно k ребер наружу и обратно. Второй член дает количество двухшаговых путей, когда i и j напрямую связаны. Третий член дает соответствующее значение, когда i и j не связаны. Поскольку эти три случая являются взаимоисключающими и в совокупности исчерпывающими , отсюда следует простое аддитивное равенство.

И наоборот, граф, матрица смежности которого удовлетворяет обоим вышеуказанным условиям и который не является полным или нулевым графом, является сильно регулярным графом.

и спектр

Поскольку матрица смежности A симметрична, отсюда следует, что ее собственные векторы ортогональны . Выше мы уже наблюдали один собственный вектор, состоящий из всех единиц, соответствующий собственному значению k . Следовательно, все остальные собственные векторы x должны удовлетворять $Jx=0$ где J — матрица «все единицы», как и раньше. Возьмем ранее составленное уравнение:

$A^{2}=kI+\lambda {A}+\mu (J-I-A)$

и умножьте приведенное выше уравнение на собственный вектор x :

$A^{2}x=kIx+\lambda {A}x+\mu (J-I-A)x$

Назовите соответствующее собственное значение p (не путать с $\lambda$ параметр графика) и подставьте $Ax=px$, $Jx=0$ и $Ix=x$:

$p^{2}x=kx+\lambda px-\mu x-\mu px$

Устраните x и переставьте, чтобы получить квадратичное число:

$p^{2}+(\mu -\lambda )p-(k-\mu )=0$

Это дает два дополнительных собственных значения ${\frac {1}{2}}\left[(\lambda -\mu )\pm {\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]$. Таким образом, у сильно регулярной матрицы имеется ровно три собственных значения.

И наоборот, связный регулярный граф только с тремя собственными значениями является сильно регулярным.

Следуя терминологии, используемой в большей части литературы по строго регулярным графам, большее собственное значение называется r с кратностью f , а меньшее — s с кратностью g .

Поскольку сумма всех собственных значений является следом матрицы смежности соответствующие кратности f и g , которая в данном случае равна нулю, можно вычислить :

• Собственное значение k имеет кратность 1.
• собственное значение $r={\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]$ имеет кратность $f={\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$.
• собственное значение $s={\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]$ имеет кратность $g={\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$.

Поскольку кратности должны быть целыми числами, их выражения обеспечивают дополнительные ограничения на значения v , k , µ и λ .

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

Сильно регулярные графы, для которых $2k+(v-1)(\lambda -\mu )=0$ называются графами конференций из-за их связи с симметричными матрицами конференций . Их параметры уменьшаются до

$\operatorname {srg} \left(v,{\frac {1}{2}}(v-1),{\frac {1}{4}}(v-5),{\frac {1}{4}}(v-1)\right).$

Их собственные значения $r={\frac {-1+{\sqrt {v}}}{2}}$ и $s={\frac {-1-{\sqrt {v}}}{2}}$, обе кратности которых равны ${\frac {v-1}{2}}$. Кроме того, в этом случае v должно равняться сумме двух квадратов, что связано с теоремой Брука–Райзера–Чоулы .

Дополнительные свойства собственных значений и их кратностей:

• $(A-rI)\times (A-sI)=\mu .J$, поэтому $(k-r).(k-s)=\mu v$
• $\lambda -\mu =r+s$
• $k-\mu =-r\times s$
• $k\geq r$
• Учитывая srg( v , k , λ, µ) с собственными значениями r и s , его дополнение srg( v , v − k − 1, v − 2 − 2 k + µ, v − 2 k + λ) имеет собственные значения -1 -s и -1-r .
• Альтернативные уравнения для кратностей: $f={\frac {(s+1)k(k-s)}{\mu (s-r)}}$ и $g={\frac {(r+1)k(k-r)}{\mu (r-s)}}$
• Условие коэффициента кадра: $vk(v-k-1)=fg(r-s)^{2}$. Как следствие, $v=(r-s)^{2}$ тогда и только тогда, когда ${f,g}={k,v-k-1}$ в каком-то порядке.
• Условия крана: $(v-k-1)^{2}(k^{2}+r^{3})\geq (r+1)^{3}k^{2}$ и $(v-k-1)^{2}(k^{2}+s^{3})\geq (s+1)^{3}k^{2}$
• Абсолютная граница: $v\leq {\frac {f(f+3)}{2}}$ и $v\leq {\frac {g(g+3)}{2}}$.
• Коготь связан: если $r+1>{\frac {s(s+1)(\mu +1)}{2}}$, затем $\mu =s^{2}$ или $\mu =s(s+1)$.

Если приведенные выше условия нарушены для какого-либо набора параметров, то для этих параметров не существует строго регулярного графика. такие списки существования или несуществования Брауэр собрал здесь с указанием причин несуществования, если таковые имеются.

Теорема Хоффмана-Синглтона

Как отмечалось выше, кратности собственных значений определяются выражением

$M_{\pm }={\frac {1}{2}}\left[(v-1)\pm {\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$

которые должны быть целыми числами.

В 1960 году Алан Хоффман и Роберт Синглтон исследовали эти выражения применительно к графам Мура с λ = 0 и µ = 1. Такие графы свободны от треугольников (в противном случае λ превышало бы ноль) и четырехугольников (в противном случае µ превышало бы 1), следовательно, они имеют обхват (наименьшую длину цикла) 5. Подставляя значения λ и μ в уравнение $(v-k-1)\mu =k(k-\lambda -1)$, видно, что $v=k^{2}+1$, а кратности собственных значений сводятся к

$M_{\pm }={\frac {1}{2}}\left[k^{2}\pm {\frac {2k-k^{2}}{\sqrt {4k-3}}}\right]$

Чтобы кратности были целыми числами, величина ${\frac {2k-k^{2}}{\sqrt {4k-3}}}$ должен быть рациональным, поэтому либо числитель $2k-k^{2}$ это ноль или знаменатель ${\sqrt {4k-3}}$ является целым числом.

Если числитель $2k-k^{2}$ равен нулю, возможности таковы:

• k = 0 и v = 1 дают тривиальный граф с одной вершиной и без ребер, а
• k = 2 и v с 5 вершинами. = 5 дают граф цикла $C_{5}$, обычно изображаемый в виде правильного пятиугольника .

Если знаменатель ${\sqrt {4k-3}}$ является целым числом t , тогда $4k-3$ это идеальный квадрат $t^{2}$, так $k={\frac {t^{2}+3}{4}}$. Замена:

${\begin{aligned}M_{\pm }&={\frac {1}{2}}\left[\left({\frac {t^{2}+3}{4}}\right)^{2}\pm {\frac {{\frac {t^{2}+3}{2}}-\left({\frac {t^{2}+3}{4}}\right)^{2}}{t}}\right]\\32M_{\pm }&=(t^{2}+3)^{2}\pm {\frac {8(t^{2}+3)-(t^{2}+3)^{2}}{t}}\\&=t^{4}+6t^{2}+9\pm {\frac {-t^{4}+2t^{2}+15}{t}}\\&=t^{4}+6t^{2}+9\pm \left(-t^{3}+2t+{\frac {15}{t}}\right)\end{aligned}}$

Поскольку обе части являются целыми числами, ${\frac {15}{t}}$ должно быть целым числом, поэтому t кратно 15, а именно $t\in \{\pm 1,\pm 3,\pm 5,\pm 15\}$, поэтому $k\in \{1,3,7,57\}$. По очереди:

• k = 1 и v = 2 дает тривиальный граф из двух вершин, соединенных ребром,
• k = 3 и v = 10 дают граф Петерсена ,
• k = 7 и v = 50 дает граф Хоффмана–Синглтона , открытый Хоффманом и Синглтоном в ходе этого анализа, и
• k = 57 и v = 3250 предсказывают знаменитый граф, который не был открыт с 1960 года и его существование не было опровергнуто.

Теорема Хоффмана-Синглтона утверждает, что не существует строго регулярных графов Мура с обхватом 5, кроме перечисленных выше.

См. также

• Частичная геометрия
• Матрица смежности Зейделя
• Двухграфический

Ссылки

• Андрис Брауэр и Хендрик ван Мальдегем (2022), Сильно регулярные графы . Кембридж: Издательство Кембриджского университета. ISBN   1316512037 . ISBN   978-1316512036
• А. Е. Брауэр, А. М. Коэн и А. Ноймайер (1989), Дистанционные регулярные графы . Берлин, Нью-Йорк: Springer-Verlag. ISBN   3-540-50619-5 , ISBN   0-387-50619-5
• Крис Годсил и Гордон Ройл (2004), Алгебраическая теория графов . Нью-Йорк: Springer-Verlag. ISBN   0-387-95241-1

Внешние ссылки

• Эрик В. Вайсштейн , статья Mathworld с многочисленными примерами.
• Гордон Ройл , Список крупных графов и семейств.
• Андрис Э. Брауэр , Параметры сильно регулярных графов.
• Брендан Маккей , Некоторые сборники графиков.
• Тед Спенс , Сильно регулярные графы не более чем с 64 вершинами.