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

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Материалы без ссылок могут быть оспорены и удалены. Найти источники:  "Distance-regular graph" – новости  · газеты  · книги  · ученый  · JSTOR ( июнь 2009 г. ) ( Узнайте, как и когда удалять это сообщение )

В математической области теории графов дистанционно регулярный граф — это регулярный граф , такой что для любых двух вершин 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 д}$${\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}$

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

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

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

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

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

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

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