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

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

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

Оказывается, что граф диаметра является дистанционно-регулярным тогда и только тогда, когда существует массив целых чисел такой , что для всех дает число соседей на расстоянии от и дает число соседей на расстоянии от для любой пары вершины и на расстоянии на . Массив целых чисел, характеризующий дистанционно регулярный граф, называется массивом его пересечений .${\ Displaystyle г}$${\ Displaystyle д}$${\ displaystyle \ {b_ {0}, b_ {1}, \ ldots, b_ {d-1}; c_ {1}, \ ldots, c_ {d} \}}$${\ Displaystyle 1 \ Leq j \ Leq D}$${\ displaystyle b_ {j}}$${\ Displaystyle ты}$${\ Displaystyle j + 1}$${\ Displaystyle v}$${\ displaystyle c_ {j}}$${\ Displaystyle ты}$${\ Displaystyle j-1}$${\ Displaystyle v}$${\ Displaystyle ты}$${\ Displaystyle v}$${\ Displaystyle j}$${\ Displaystyle г}$

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

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

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