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

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

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

В теории графов , сильно регулярный граф определяется следующим образом . Пусть G = ( V , E ) - регулярный граф с v вершинами и степенью k . G называется сильно регулярной, если существуют также целые числа λ и μ такие, что:

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

Иногда такой граф называют srg ( v , k , λ, μ). Сильно регулярные графы были введены Раджем Чандрой Бозом в 1963 г. ^[1]

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

Комплемента из SRG ( v , к , λ, мкм) также сильно регулярны. Это srg ( v , v − k −1, v −2−2 k + μ, v −2 k + λ).

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

Свойства [ править ]

Связь между параметрами [ править ]

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

{\ Displaystyle (ВК-1) \ му = К (к- \ лямбда -1)}

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

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

Матрица смежности [ править ]

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

{\ Displaystyle AJ = JA = кДж,}

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

{\ displaystyle {A} ^ {2} = k {I} + \ lambda {A} + \ mu ({JIA})}

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

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

Собственные значения [ править ]

Матрица смежности графа имеет ровно три собственных значения :

k , кратность которого равна 1 (как показано выше)
${\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) + {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ верно],}$ чья кратность ${\ 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)}} \ верно],}$ чья кратность ${\ displaystyle {\ frac {1} {2}} \ left [(v-1) + {\ frac {2k + (v-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu) ) ^ {2} +4 (k- \ mu)}}} \ right]}$

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

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

{\text{srg}}\left(v,{\tfrac {1}{2}}(v-1),{\tfrac {1}{4}}(v-5),{\tfrac {1}{4}}(v-1)\right).

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

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

Примеры [ править ]

Цикл длины 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 _п является SRG ( ). ${\binom {n}{2}},2(n-2),n-2,4$
Эти графики Чанг являются SRG (28, 12, 6, 4), так же , как линейный график K ₈ , но эти четыре графика не изоморфны.
Линейный график из обобщенного четырехугольника GQ (2, 4) является SRG (27, 10, 1, 5). Фактически каждый обобщенный четырехугольник порядка (s, t) дает строго регулярный граф следующим образом: а именно, srg ((s + 1) (st + 1), s (t + 1), s-1, t +1).
Граф Шлефли - это srg (27, 16, 10, 8). ^[6]
Граф Хоффмана – Синглтона - это 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 долларов за решение этой проблемы. ^[7]

Графы без треугольников, графики Мура и геодезические графики [ править ]

Сильно регулярные графы с λ = 0 не содержат треугольников . Помимо полных графов с менее чем 3 вершинами и всех полных двудольных графов, семь перечисленных выше (пятиугольник, Петерсен, Клебш, Хоффман-Синглтон, Гевиртц, Меснер-M22 и Хигман-Симс) являются единственными известными. Сильно регулярные графы с λ = 0 и μ = 1 являются графами Мура с обхватом 5. Снова три графа, приведенные выше (пятиугольник, Петерсен и Хоффман-Синглтон), с параметрами (5, 2, 0, 1), (10, 3, 0, 1) и (50, 7, 0, 1) - единственные известные. Единственный другой возможный набор параметров, дающий граф Мура, - (3250, 57, 0, 1); неизвестно, существует ли такой граф, и если да, то единственен ли он. ^[8]

В более общем смысле, каждый строго регулярный граф с является геодезическим графом , графом, в котором каждые две вершины имеют уникальный невзвешенный кратчайший путь . ^[9] Единственные известные сильно регулярные графы с графами Мура. Такой график не может быть , но другие комбинации параметров, такие как (400, 21, 2, 1), еще не исключены. Несмотря на продолжающееся исследование свойств, которыми мог бы обладать сильно регулярный граф , ^[10]^[11] неизвестно, существуют ли еще какие-либо свойства или даже их количество конечно. ^[9] $\mu =1$ $\mu =1$ $\lambda =1$ $\mu =1$

См. Также [ править ]

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

Заметки [ править ]

^ https://projecteuclid.org/euclid.pjm/1103035734 , RC Bose, Сильно регулярные графы, частичные геометрии и частично сбалансированные планы, Pacific J. Math 13 (1963) 389–419. (стр.122)
^ Брауэр, Андрис Э; Хемерс, Виллем Х. Спектры графов . п. 101 Архивировано 16 марта 2012 г. в Wayback Machine.
^ Годсил, Крис; Ройл, Гордон. Алгебраическая теория графов . Springer-Verlag New York, 2001, стр. 218.
^ Cameron, PJ; ван Линт, Дж. Х. (1991), Дизайны, графики, коды и их связи , Тексты студентов 22 Лондонского математического общества, издательство Кембриджского университета, стр. 37 , ISBN 978-0-521-42385-4
^ Годсил, Крис; Ройл, Гордон. Алгебраическая теория графов . Springer-Verlag, Нью-Йорк, 2001, лемма 10.2.1.
^ Вайсштейн, Эрик В. , "Граф Шлефли" , MathWorld
^ Конвей, Джон Х. , Five $ 1,000 Problems (обновление 2017 г.) (PDF) , Интернет-энциклопедия целочисленных последовательностей , получено 12 февраля 2019 г.
^ Dalfó, C. (2019), "Обзор пропавшего графа Мура", Линейная алгебра и ее приложения , 569 : 1–14, DOI : 10.1016 / j.laa.2018.12.035 , hdl : 2117/127212 , MR 3901732
^ a b Blokhuis, A .; Брауэр, А. Е. (1988), "Геодезический граф диаметра два", Geometriae Dedicata , 25 (1-3): 527-533, DOI : 10.1007 / BF00191941 , МР 0925851
^ Deutsch, J .; Фишер, PH (2001), "О сильно регулярных графов с ", Европейский журнал комбинаторике , 22 (3): 303-306, DOI : 10,1006 / eujc.2000.0472 , MR 1822718 $\mu =1$
^ Белоусов И.Н.; Махнев А.А. (2006), "О сильно регулярных графах с автоморфизмами и их автоморфизмами", Докл. Академии наук , 410 (2): 151–155, MR 2455371. $\mu =1$

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[1] ttps://projecteuclid.org/euclid.pjm/1103035734 , RC Bose, Сильно регулярные графы, частичные геометрии и частично сбалансированные планы, Pacific J. Math 13 (1963) 389–419. (стр.122)

[2] Брауэр, Андрис Э; Хемерс, Виллем Х. Спектры графов . п. 101 Архивировано 16 марта 2012 г. в Wayback Machine.

[3] Годсил, Крис; Ройл, Гордон. Алгебраическая теория графов . Springer-Verlag New York, 2001, стр. 218.

[4] Cameron, PJ; ван Линт, Дж. Х. (1991), Дизайны, графики, коды и их связи , Тексты студентов 22 Лондонского математического общества, издательство Кембриджского университета, стр. 37 , ISBN 978-0-521-42385-4

[5] Годсил, Крис; Ройл, Гордон. Алгебраическая теория графов . Springer-Verlag, Нью-Йорк, 2001, лемма 10.2.1.

[6] Вайсштейн, Эрик В. , "Граф Шлефли" , MathWorld

[7] Конвей, Джон Х. , Five $ 1,000 Problems (обновление 2017 г.) (PDF) , Интернет-энциклопедия целочисленных последовательностей , получено 12 февраля 2019 г.

[8] Dalfó, C. (2019), "Обзор пропавшего графа Мура", Линейная алгебра и ее приложения , 569 : 1–14, DOI : 10.1016 / j.laa.2018.12.035 , hdl : 2117/127212 , MR 3901732

[bb-9] Blokhuis, A .; Брауэр, А. Е. (1988), "Геодезический граф диаметра два", Geometriae Dedicata , 25 (1-3): 527-533, DOI : 10.1007 / BF00191941 , МР 0925851

[10] Deutsch, J .; Фишер, PH (2001), "О сильно регулярных графов с ", Европейский журнал комбинаторике , 22 (3): 303-306, DOI : 10,1006 / eujc.2000.0472 , MR 1822718 $\mu =1$

[11] Белоусов И.Н.; Махнев А.А. (2006), "О сильно регулярных графах с автоморфизмами и их автоморфизмами", Докл. Академии наук , 410 (2): 151–155, MR 2455371. $\mu =1$

[1]