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

Свойство графика

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

Некоторые авторы исключают из этого определения полные графы и несвязные графы.

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

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

Массив пересечений дистанционно регулярного графа — это массив, в котором — диаметр графа и для каждого , дает число соседей на расстоянии от и дает число соседей на расстоянии от для любой пары вершин и на расстоянии . Существует также число , которое дает число соседей на расстоянии от . Числа называются числами пересечений графа. Они удовлетворяют уравнению , где — валентность , т. е. число соседей, любой вершины. ${\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}$ ${\displaystyle 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 a_{j}}$ ${\displaystyle u}$ ${\displaystyle j}$ ${\displaystyle v}$ ${\displaystyle a_{j},b_{j},c_{j}}$ ${\displaystyle a_{j}+b_{j}+c_{j}=k,}$ ${\displaystyle k=b_{0}}$

Оказывается, граф диаметра является дистанционно регулярным тогда и только тогда, когда он имеет массив пересечений в предыдущем смысле. ${\displaystyle G}$ ${\displaystyle d}$

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

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

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

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

Предположим, что есть связный дистанционно-регулярный граф валентности с массивом пересечений . Для каждого пусть обозначает число вершин на расстоянии от любой заданной вершины и пусть обозначает -регулярный граф с матрицей смежности, образованной путем связывания пар вершин на расстоянии . ${\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 k_{j}}$ ${\displaystyle k}$ ${\displaystyle G_{j}}$ ${\displaystyle k_{j}}$ ${\displaystyle A_{j}}$ ${\displaystyle G}$ ${\displaystyle j}$

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

• ${\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 G}$имеет различные собственные значения. ${\displaystyle d+1}$
• Единственное простое собственное значение равно или обоим , и если является двудольным. ${\displaystyle G}$ ${\displaystyle k,}$ ${\displaystyle k}$ ${\displaystyle -k}$ ${\displaystyle G}$
• ${\displaystyle k\leq {\frac {1}{2}}(m-1)(m+2)}$для любой кратности собственных значений , если только это не полный многодольный граф. ${\displaystyle m>1}$ ${\displaystyle G,}$ ${\displaystyle G}$
• ${\displaystyle d\leq 3m-4}$для любой кратности собственных значений , если только это не циклический граф или полный многодольный граф. ${\displaystyle m>1}$ ${\displaystyle G,}$ ${\displaystyle G}$

Если сильно регулярно , то и . ${\displaystyle G}$ ${\displaystyle n\leq 4m-1}$ ${\displaystyle k\leq 2m-1}$

Примеры

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

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

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

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

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

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

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

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

Тринадцать различных кубических дистанционно регулярных графов — это K 4 (или тетраэдрический граф ), K _3,3 , граф Петерсена , кубический граф , граф Хивуда , граф Паппуса , граф Коксетера , граф Тутта–Коксетера , додекаэдрический граф , граф Дезарга , 12-клетка Тутта , граф Биггса–Смита и граф Фостера .

Ссылки

1. Bang, S.; Dubickas, A.; Koolen, JH; Moulton, V. (2015-01-10). «Существует только конечное число дистанционно-регулярных графов фиксированной валентности, большей двух». Advances in Mathematics . 269 (Supplement 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.

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

• Godsil, C. D. (1993). Алгебраическая комбинаторика . Серия Chapman and Hall Mathematics. Нью-Йорк: Chapman and Hall. ISBN 978-0-412-04131-0. МР  1220704.