Сильно регулярный граф - Strongly regular graph

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

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

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

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

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

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

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

Характеристики

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

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

{ Displaystyle (v-k-1) mu = k (k- lambda -1)}

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

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

Матрица смежности

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

{ Displaystyle AJ = JA = кДж,}

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

{ displaystyle {A} ^ {2} = k {I} + lambda {A} + mu ({J-I-A})}

что выражает сильную регулярность. В ij-й элемент левой части дает количество двухшаговых путей из я к j. Первый член правой части дает количество путей из я к я, а именно k рёбра наружу и обратно. Второй член дает количество двухшаговых путей, когда я и j связаны напрямую. Третий член дает соответствующее значение, когда я и 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}$ называются графики конференций из-за их связи с симметричными матрицы конференций. Их параметры сводятся к

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

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

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

Примеры

В цикл длины 5 - это srg (5, 2, 0, 1).
В Граф Петерсена является srg (10, 3, 0, 1).
В Граф Клебша является srg (16, 5, 0, 2).
В Граф Шриханде это srg (16, 6, 2, 2), который не является дистанционно-транзитивный граф.
В п × п квадрат график ладьи, т.е. линейный граф сбалансированного полного двудольного графа K_{п, п}, является srg (п², 2п − 2, п - 2, 2). Параметры для п= 4 совпадают с графами Шрикханде, но эти два графа не изоморфны.
В линейный график полного графа K_п это srg ( ${ Displaystyle { binom {п} {2}}, 2 (п-2), п-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]

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

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

Примечания

^ https://projecteuclid.org/euclid.pjm/1103035734, Р. К. Боз, Сильно регулярные графы, частичные геометрии и частично сбалансированные планы, PacificJ. Математика 13 (1963) 389–419. (стр.122)
^ Брауэр, Андрис Э; Хемерс, Виллем Х. Спектры графиков. п. 101 В архиве 2012-03-16 в Wayback Machine
^ Годсил, Крис; Ройл, Гордон. Алгебраическая теория графов. Springer-Verlag New York, 2001, стр. 218.
^ Cameron, P.J .; ван Линт, Дж. (1991), Конструкции, графики, коды и их ссылки, Тексты студентов Лондонского математического общества 22, Cambridge University Press, стр.37, ISBN 978-0-521-42385-4
^ Годсил, Крис; Ройл, Гордон. Алгебраическая теория графов. Springer-Verlag, Нью-Йорк, 2001, лемма 10.2.1.
^ Вайсштейн, Эрик В., «Граф Шлефли», MathWorld
^ Конвей, Джон Х., Пять проблем по 1000 долларов (обновление 2017 г.) (PDF), Интернет-энциклопедия целочисленных последовательностей, получено 2019-02-12
^ Dalfó, C. (2019), "Обзор отсутствующего графа Мура", Линейная алгебра и ее приложения, 569: 1–14, Дои:10.1016 / j.laa.2018.12.035, Г-Н 3901732
^ ^а ^б Блохейс, А.; Брауэр, А. Э. (1988), "Геодезические графы диаметра два", Geometriae Dedicata, 25 (1–3): 527–533, Дои:10.1007 / BF00191941, Г-Н 0925851
^ Deutsch, J .; Фишер, П. Х. (2001), "О сильно регулярных графах с ${ displaystyle mu = 1}$ ", Европейский журнал комбинаторики, 22 (3): 303–306, Дои:10.1006 / eujc.2000.0472, Г-Н 1822718
^ Белоусов, И. Н .; Махнев А.А. (2006), "О сильно регулярных графах с ${ displaystyle mu = 1}$ и их автоморфизмы », Доклады Академии Наук, 410 (2): 151–155, Г-Н 2455371

внешняя ссылка

[1] ttps://projecteuclid.org/euclid.pjm/1103035734, Р. К. Боз, Сильно регулярные графы, частичные геометрии и частично сбалансированные планы, PacificJ. Математика 13 (1963) 389–419. (стр.122)

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

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

[4] Cameron, P.J .; ван Линт, Дж. (1991), Конструкции, графики, коды и их ссылки, Тексты студентов Лондонского математического общества 22, Cambridge University Press, стр.37, ISBN 978-0-521-42385-4

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

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

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

[8] Dalfó, C. (2019), "Обзор отсутствующего графа Мура", Линейная алгебра и ее приложения, 569: 1–14, Дои:10.1016 / j.laa.2018.12.035, Г-Н 3901732

[bb-9] а ^б Блохейс, А.; Брауэр, А. Э. (1988), "Геодезические графы диаметра два", Geometriae Dedicata, 25 (1–3): 527–533, Дои:10.1007 / BF00191941, Г-Н 0925851

[10] Deutsch, J .; Фишер, П. Х. (2001), "О сильно регулярных графах с ${ displaystyle mu = 1}$ ", Европейский журнал комбинаторики, 22 (3): 303–306, Дои:10.1006 / eujc.2000.0472, Г-Н 1822718

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

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