Дистанционно регулярный граф - Distance-regular graph

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

В математика, а дистанционно регулярный граф это обычный график такое, что для любых двух вершин v и ш, количество вершин в расстояние j из v и на расстоянии k из ш зависит только от j, k, и я = d (v, w).

Каждые дистанционно-транзитивный граф дистанционно регулярный. Действительно, дистанционно-регулярные графы были введены как комбинаторное обобщение дистанционно-транзитивных графов, обладающих свойствами числовой регулярности последних, но не обязательно имеющими большой размер. группа автоморфизмов.

Массивы пересечений

Получается, что график ${displaystyle G}$ диаметра ${displaystyle d}$ является дистанционно регулярным тогда и только тогда, когда существует массив целых чисел ${displaystyle {b_{0},b_{1},ldots ,b_{d-1};c_{1},ldots ,c_{d}}}$ такое, что для всех ${displaystyle 1leq jleq d}$, ${displaystyle b_{j}}$ дает количество соседей ${displaystyle u}$ на расстоянии ${displaystyle j+1}$ из ${displaystyle v}$ и ${displaystyle c_{j}}$ дает количество соседей ${displaystyle u}$ на расстоянии ${displaystyle j-1}$ из ${displaystyle v}$ для любой пары вершин ${displaystyle u}$ и ${displaystyle v}$ на расстоянии ${displaystyle j}$ на ${displaystyle G}$. Массив целых чисел, характеризующий дистанционно регулярный граф, известен как его массив пересечений.

Коспектральные дистанционно-регулярные графы

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

Дистанционно регулярный граф несвязен тогда и только тогда, когда он несвязный союз коспектральных дистанционно регулярных графов.

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

Предполагать ${displaystyle G}$ является связным дистанционно регулярным графом валентность ${displaystyle k}$ с массивом пересечений ${displaystyle {b_{0},b_{1},ldots ,b_{d-1};c_{1},ldots ,c_{d}}}$. Для всех ${displaystyle 0leq jleq d}$: позволять ${displaystyle G_{j}}$ обозначить ${displaystyle k_{j}}$-регулярный граф с матрица смежности ${displaystyle A_{j}}$ образованы связанными парами вершин на ${displaystyle G}$ на расстоянии ${displaystyle j}$, и разреши ${displaystyle a_{j}}$ обозначают количество соседей ${displaystyle u}$ на расстоянии ${displaystyle j}$ из ${displaystyle v}$ для любой пары вершин ${displaystyle u}$ и ${displaystyle v}$ на расстоянии ${displaystyle j}$ на ${displaystyle G}$.

Теоретико-графические свойства

• ${displaystyle {frac {k_{j+1}}{k_{j}}}={frac {b_{j}}{c_{j+1}}}}$ для всех ${displaystyle 0leq j<d}$.
• ${displaystyle b_{0}>b_{1}geq cdots geq b_{d-1}>0}$ и ${displaystyle 1=c_{1}leq cdots leq c_{d}leq b_{0}}$.

Спектральные свойства

• ${displaystyle kleq {frac {1}{2}}(m-1)(m+2)}$ для любой кратности собственных значений ${displaystyle m>1}$ из ${displaystyle G}$, если только ${displaystyle G}$ является полным многодольным графом.
• ${displaystyle dleq 3m-4}$ для любой кратности собственных значений ${displaystyle m>1}$ из ${displaystyle G}$, если только ${displaystyle G}$ является графом циклов или полным многодольным графом.
• ${displaystyle lambda in {pm k}}$ если ${displaystyle lambda }$ простое собственное значение ${displaystyle G}$.
• ${displaystyle G}$ имеет ${displaystyle d+1}$ различные собственные значения.

Если ${displaystyle G}$ является строго регулярный, тогда ${displaystyle nleq 4m-1}$ и ${displaystyle kleq 2m-1}$.

Примеры

Некоторые первые примеры дистанционно-регулярных графов включают:

• В полные графики.
• В графики циклов.
• В нечетные графики.
• В Графики Мура.
• График коллинеарности правильный возле многоугольника.
• В График Уэллса и Граф Сильвестра.
• Сильно регулярные графы диаметра ${displaystyle 2}$.

Классификация дистанционно регулярных графов

Существует лишь конечное число различных связных дистанционно регулярных графов любой данной валентности. ${displaystyle k>2}$.^[1]

Точно так же существует только конечное число различных связных дистанционно регулярных графов с любой заданной кратностью собственных значений ${displaystyle m>2}$^[2] (за исключением полных многодольных графов).

Кубические дистанционно регулярные графы

В кубический дистанционно регулярные графы полностью классифицированы.

13 различных кубических дистанционно регулярных графов K₄ (или же тетраэдр ), K_3,3, то Граф Петерсена, то куб, то График Хивуда, то График Паппа, то Граф Кокстера, то График Тутте – Кокстера, то додекаэдр, то График дезарга, Тутте 12 клеток, то График Биггса – Смита, а Граф Фостера.

Рекомендации

1. Bang, S .; Дубицкас, А .; Koolen, J. H .; Моултон, В. (10 января 2015 г.). «Существует лишь конечное число дистанционно регулярных графов с фиксированной валентностью больше двух». Успехи в математике. 269 (Дополнение C): 1–55. arXiv:0909.5253. Дои:10.1016 / j.aim.2014.09.025.
2. Годсил, К. Д. (1988-12-01). «Ограничение диаметра дистанционно регулярных графов». Комбинаторика. 8 (4): 333–343. Дои:10.1007 / BF02189090. ISSN  0209-9683.

дальнейшее чтение

• Годсил, К. Д. (1993). Алгебраическая комбинаторика. Математика Чепмена и Холла. Нью-Йорк: Чепмен и Холл. С. xvi + 362. ISBN  978-0-412-04131-0. Г-Н  1220704.