Дистанционно-регулярный граф () — такой регулярный граф, у которого для двух любых вершин и , расположенных на одинаковом расстоянии друг от друга, справедливо, что количество вершин, инцидентных к и при этом находящихся на расстоянии от вершины , зависит только от расстояния между вершинами и ; более того, количество вершин, инцидентных к и находящихся на расстоянии от вершины , также зависит только от расстояния .
Дистанционно-регулярные графы были введены Н. Биггсом в 1969 году на конференции в Оксфорде, хотя сам термин появился гораздо позже.
Определение Определение дистанционно-регулярного графа:
Дистанционно-регулярный граф — это неориентрированный, связанный, ограниченный, регулярный граф валентности и диаметром , для которого справедливо следующее. Существуют натуральные числа
такие, что для каждой пары вершин , отстоящих друг от друга на расстоянии , справедливо:
(1) число вершин, инцидентных и находящихся на расстоянии от , есть () (2) число вершин, инцидентных и находящихся на расстоянии от , есть ().
Тогда
есть массив пересечений графа (см. ), а — числа пересечений, где .
Массив пересечений Изначально термины «массив пересечений» и «числа пересечений» были введены для описания дистанционно-транзитивных графов.
Пусть есть неориентированный, связанный, ограниченный граф, а две его вершины находятся на расстоянии друг от друга. Все вершины , инцидентные к вершине , можно разбить на три множества , и в зависимости от их расстояния до вершины :
Если граф дистанционно-транзитивный, то мощности (кардинальные числа) множеств не зависят от вершин , а зависят только от расстояния . Пусть , где есть числа пересечений.
Определим массив пересечений дистанционно-транзитивного графа как:
Если — валентность графа, то , а . Более того, , тогда компактная форма записи массива пересечений есть:
Дистанционно-регулярный и дистанционно-транзитивный графы На первый взгляд дистанционно-транзитивный граф и дистанционно-регулярный граф являются очень близкими понятиями. Действительно, каждый дистанционно-транзитивный граф является дистанционно-регулярным. Однако их природа разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности.
Следствием автоморфизма дистанционно-транзитивного графа является его регулярность. Соответственно, для регулярного графа можно определить числа пересечений. С другой стороны для дистанционно-регулярного графа существует комбинаторная регулярность, и для него также определены числа пересечений (см. ), однако автоморфизм из этого не следует.
Из дистанционно-транзитивности графа следует его дистанционно-регулярность, но обратное неверно. Это было доказано в 1969 г., еще до введения в обиход термина «дистанционно-транзитивный граф», группой советских математиков (Г. М. Адельсон-Вельский, Б. Ю. Вейсфелер, А. А. Леман, И. А. Фараджев). Наименьший дистанционно-регулярный граф, не являющийся дистанционно-транзитивным, — это граф Шрикханде. Единственный тривалентный граф этого типа — это 12-клетка Татта, граф с 126 вершинами.
Свойства Дистанционно-регулярный граф с диаметром 2 является сильно регулярным, и обратное тоже верно (при условии, что граф является связным).
Свойства массива пересечений дистанционно-регулярного графа Массив пересечений дистанционно-регулярного графа обладает следующими свойствами: Каждая вершина имеет постоянное число вершин , отстоящих от нее на расстояние , причем и для всех ; Порядок графа равен ; Число вершин, отстоящих от каждой вершины на расстоянии , выражается через числа пересечений как для всех ; Произведение числа вершин, отстоящих от произвольной вершины на расстоянии , на порядок графа есть четная величина для всех ; Произведение числа вершин, отстоящих от произвольной вершины на расстоянии , на число пересечений на есть четная величина для всех ; Произведение числа пересечений на порядок графа и на его валентность делится на 6; Для чисел пересечений справедливо ; Для чисел пересечений справедливо ; Если , то ; Есть такое , что и .
Матрицы расстояний транзитивно-регулярного графа Пусть граф — транзитивно-регулярный диаметра , есть число его вершин, а — валентность графа. Определим множество матриц расстояний () размера как :
Свойства матриц расстояний Матрицы расстояния обладают следующими свойствами: , где есть единичная матрица ; есть обычная матрица смежности графа ; , где есть матрица единиц , где — массив пересечений дистанционно-регулярного графа и существуют такие действительные числа , что для всех , причем есть число пересечений, то есть количество вершин, находящихся на расстоянии от вершины и на расстоянии от вершины при условии расстояния между вершинами и . Отметим, что , , .
Примечания
Литература
Категория:Алгебраическая теория графов Категория:Регулярные графы