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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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