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

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

В математике , А дистанционно регулярный граф является регулярным график таким образом, что для любых двух вершин v и ш , число вершин на расстоянии J от V и на расстоянии к от ш зависит только от J , K , и я = D (v , ш) .

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

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

Получается, что график ${\ displaystyle G}$ диаметра ${\ displaystyle d}$ дистанционно регулярна тогда и только тогда, когда существует массив целых чисел ${\ displaystyle \ {b_ {0}, b_ {1}, \ ldots, b_ {d-1}; c_ {1}, \ ldots, c_ {d} \}}$ такое, что для всех ${\ displaystyle 1 \ leq j \ leq 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 0 \ Leq J \ Leq 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 0 \ Leq 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 к \ Leq {\ гидроразрыва {1} {2}} (м-1) (м + 2)}$ для любой кратности собственных значений ${\ displaystyle m> 1}$ из ${\ displaystyle G}$ , пока не ${\ displaystyle G}$ является полным многодольным графом.
${\ displaystyle d \ leq 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 п \ leq 4m-1}$ и ${\ Displaystyle к \ leq 2m-1}$ .

Примеры

Граф Клейна степени 7 и ассоциированное отображение, вложенные в ориентируемую поверхность рода 3. Этот граф дистанционно регулярен с массивом пересечений {7,4,1; 1,2,7} и группой автоморфизмов PGL (2,7).

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

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

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

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

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

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

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

В 13 различных кубических дистанционно регулярных графами являются К ₄ (или тетраэдру график ), К _3,3 , то граф Петерсена , то Кубический граф , то графы хивуд , то график Летучки , то граф Кокстера , то график Тутты-Косетер , то додекаэдрическое граф , то граф Дезарг , Тутте 12-клетка , то граф Биггс-Смит , и график , Фостер .

Ссылки

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

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

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

[1] Bang, S .; Дубицкас, А .; Кулен, JH; Моултон, В. (10 января 2015 г.). «Существует только конечное число дистанционно регулярных графов с фиксированной валентностью больше двух». Успехи в математике . 269 (Дополнение C): 1–55. arXiv : 0909.5253 . DOI : 10.1016 / j.aim.2014.09.025 . S2CID 18869283 .

[2] Godsil, CD (1988-12-01). «Ограничение диаметра дистанционно регулярных графов». Combinatorica . 8 (4): 333–343. DOI : 10.1007 / BF02189090 . ISSN 0209-9683 . S2CID 206813795 .

[1]