В математике , А дистанционно регулярный граф является регулярным график таким образом, что для любых двух вершин v и ш , число вершин на расстоянии J от V и на расстоянии к от ш зависит только от J , K , и я = D (v , ш) .
Каждый дистанционно-транзитивный граф дистанционно регулярен. Действительно, дистанционно регулярные графы были введены как комбинаторное обобщение дистанционно-транзитивных графов, обладающих свойствами числовой регулярности последних, но не обязательно имеющими большую группу автоморфизмов .
Массивы пересечений
Получается, что график диаметра дистанционно регулярна тогда и только тогда, когда существует массив целых чисел такое, что для всех , дает количество соседей на расстоянии из а также дает количество соседей на расстоянии из для любой пары вершин а также на расстоянии на . Массив целых чисел, характеризующий дистанционно регулярный граф, известен как его массив пересечений .
Коспектральные дистанционно-регулярные графы
Пара связных дистанционно регулярных графов коспектральна тогда и только тогда, когда они имеют один и тот же массив пересечений.
Дистанционно регулярный граф несвязен тогда и только тогда, когда он является несвязным объединением коспектральных дистанционно регулярных графов.
Характеристики
Предполагать является связным дистанционно регулярным графом валентности с массивом пересечений . Для всех: позволять обозначить -регулярный граф с матрицей смежности образованы связанными парами вершин на на расстоянии , и разреши обозначают количество соседей на расстоянии из для любой пары вершин а также на расстоянии на .
Теоретико-графические свойства
- для всех .
- а также .
Спектральные свойства
- для любой кратности собственных значений из , пока не является полным многодольным графом.
- для любой кратности собственных значений из , пока не является графом циклов или полным многодольным графом.
- если простое собственное значение .
- имеет различные собственные значения.
Если является сильно регулярным , то а также .
Примеры
Некоторые первые примеры дистанционно-регулярных графов включают:
- В комплекте графики .
- В циклы графики .
- В нечетные графики .
- Мур графики .
- График коллинеарности правильного почти многоугольника .
- Скважины график и график Сильвестра .
- Сильно регулярные графы диаметра .
Классификация дистанционно регулярных графов
Существует лишь конечное число различных связных дистанционно регулярных графов любой данной валентности. . [1]
Точно так же существует только конечное число различных связных дистанционно регулярных графов с любой заданной кратностью собственных значений [2] (за исключением полных многодольных графов).
Кубические дистанционно регулярные графы
В кубических дистанционно регулярных графов были полностью засекречены.
В 13 различных кубических дистанционно регулярных графами являются К 4 (или тетраэдру график ), К 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 .
- ^ Годсил, 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 .