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

Понятие в теории графов

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

В теории графов строго регулярный граф ( SRG ) — это регулярный граф G = ( V , E ) с v вершинами и степенью k, такой что для некоторых заданных целых чисел ${\displaystyle \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 , λ, μ). По соглашению графы, которые тривиально удовлетворяют определению, исключаются из подробных исследований и списков сильно регулярных графов. К ним относятся несвязное объединение одного или нескольких полных графов равного размера , ^{[1] [2]} и их дополнения , полные многодольные графы с независимыми множествами равного размера.

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

История

Сильно регулярные графы были введены Р. К. Бозе в 1963 году. ^[3] Они основывались на более ранних работах 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). ^[4]
• Граф Хоффмана–Синглтона — это 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 долларов за решение этой задачи. ^[5]

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

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

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

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

Алгебраические свойства сильно регулярных графов

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

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

${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$

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

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

Уравнения матрицы смежности

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

Первый:

${\displaystyle AJ=JA=kJ,}$

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

Второй:

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

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

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

Собственные значения и спектр графика

Так как матрица смежности A симметрична, то ее собственные векторы ортогональны . Мы уже наблюдали один собственный вектор выше, который состоит из всех единиц, что соответствует собственному значению k . Поэтому все остальные собственные векторы x должны удовлетворять где J — матрица из всех единиц, как и прежде. Возьмем ранее установленное уравнение: ${\displaystyle Jx=0}$

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

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

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

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

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

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

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

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

Наоборот, связный регулярный граф, имеющий только три собственных значения, является сильно регулярным. ^[10]

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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. Подставляя значения λ и μ в уравнение , можно увидеть, что , а кратности собственных значений уменьшаются до ${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$ ${\displaystyle v=k^{2}+1}$

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

Смотрите также

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

Примечания

1. Брауэр, Андрис Э.; Хемерс, Виллем Х. Спектры графов. стр. 101 Архивировано 16.03.2012 на Wayback Machine
2. Годсил, Крис; Ройл, Гордон. Алгебраическая теория графов . Springer-Verlag New York, 2001, стр. 218.
3. https://projecteuclid.org/euclid.pjm/1103035734, RC Bose, Сильно регулярные графы, частичные геометрии и частично сбалансированные планы, Pacific J. Math 13 (1963) 389–419. (стр. 122)
4. Вайсштейн, Эрик В. , «Граф Шлефли», MathWorld
5. Конвей, Джон Х. , Пять задач на 1000 долларов (обновление 2017 г.) (PDF) , Онлайн-энциклопедия целочисленных последовательностей , получено 12 февраля 2019 г.
6. Блокхейс, А .; Брауэр, AE (1988), «Геодезические графики второго диаметра», Geometriae Dedicata , 25 (1–3): 527–533, doi : 10.1007/BF00191941, MR  0925851, S2CID  189890651
7. Deutsch, J.; Fisher, PH (2001), "О сильно регулярных графах с ", European Journal of Combinatorics , 22 (3): 303–306, doi : 10.1006/eujc.2000.0472 , MR  1822718 ${\displaystyle \mu =1}$
8. Белоусов, И.Н.; Махнев, А.А. (2006), "О сильно регулярных графах с и их автоморфизмах", Доклады Академии наук , 410 (2): 151–155, MR  2455371 ${\displaystyle \mu =1}$
9. Кэмерон, П. Дж.; ван Линт, Дж. Х. (1991), Проекты, графики, коды и их связи, Лондонское математическое общество, студенческие тексты 22, Cambridge University Press, стр. 37, ISBN 978-0-521-42385-4
10. Годсил, Крис; Ройл, Гордон. Алгебраическая теория графов . Springer-Verlag, Нью-Йорк, 2001, Лемма 10.2.1.
11. Дальфо, К. (2019), «Обзор отсутствующего графа Мура», Линейная алгебра и ее приложения , 569 : 1–14, doi : 10.1016/j.laa.2018.12.035, hdl : 2117/127212 , MR  3901732, S2CID  126689579

Ссылки

• Андрис Брауэр и Хендрик ван Мальдегем (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 вершинами.