Дистанційно-регулярний граф () — це такий регулярний граф, у якого для двох будь-яких вершин і , розташованих на однаковій відстані одна від одної, кількість вершин інцидентних до , і при цьому розташованих на відстані від вершини , залежить тільки від відстані між вершинами і ; більш того кількість інцидентних до вершин, розташованих на відстані від вершини , також залежить тільки від відстані .
Визначення Визначення дистанційно-регулярного графа:
Дистанційно-регулярний граф — це неорієнтований, зв'язний, обмежений, регулярний граф діаметром , для якого справедливо, що існують числа
такі, що для кожної пари вершин , відстань між якими справедливо:
(1) число вершин, інцидентних , розташованих на відстані від є (): (2) число вершин, інцидентних , розташованих на відстані від є ().
Масив є масив перетинів дистанційно-регулярного графа, де — валентність графа.
Дистанційно-регулярний граф з діаметром 2 є сильно регулярним і обернене твердження теж істинне (за умови, що граф є зв'язним).
Дистанційно-регулярний і дистанційно-транзитивний графи На перший погляд дистанційно-транзитивний граф і дистанційно-регулярний граф є дуже близькими поняттями. Дійсно, кожен дистанційно-транзитивний граф є дистанційно-регулярним. Однак їх природа різна. Якщо дистанційно-транзитивний граф визначається виходячи з симетрії графа через умову автоморфізму, то дистанційно-регулярний граф визначається з умови його комбінаторної регулярності.
Автоморфізм дистанційно-транзитивного графа викликає його регулярність, і відповідно, наявність чисел перетинів . Однак, якщо існує комбінаторна регулярність, і визначені числа перетинів для графа, і він дистанційно-регулярний, то автоморфізм з цього не випливає.
Якщо з дистанційно-транзитивності графа випливає його дистанційно-регулярність, то зворотне не істинне.
Це доведено 1969 року, ще до введення в ужиток терміна дистанційно-транзитивний граф, групою радянських математиків (Адельсон-Вельський Г. М., , Леман А. А., Фараджев І. А.). Найменший дистанційно-регулярний граф, який не є дистанційно-транзитивним — це граф Шрікханде. Єдиний тривалентний граф цього типу — це 12-клітка Татта, граф зі 126 вершинами.
Масив перетинів дистанційно-регулярного графа нехай — транзитивно-регулярний граф діаметра і порядку , а і — пара вершин, віддалених одна від одної на відстань . Тоді множину вершин, інцидентних до можна розбити на три множини , і , залежно від їх відстані до вершини , де вершина інцидентна до :
.
кардинальні числа цих множин є числами перетинів, а масив перетинів є
якщо — валентність графа, то , а . Більш того, . Тому масив перетинів записується як:
Властивості масиву перетинів дистанційно-регулярного графа Згідно з оглядом:
Кожна вершина має стале число вершин , віддалених від неї на відстань , причому і для всіх ; порядок графа дорівнює ; число вершин, віддалених від кожної вершини на відстан виражається через числа перетинів як для всіх ; добуток числа вершин, віддалених від довільної вершини на відстань , на порядок графа є парним числом для всіх ; добуток числа вершин, віддалених від довільної вершини на відстані , на кількість перетинів є парним числом для всіх ; добуток числа перетинів на порядок графа і на його валентність ділитися на 6; для чисел перетинів виконується ; для чисел перетинів виконується ; якщо , то ; є таке , що і .
Матриці відстаней транзитивно-регулярного графа Нехай граф — транзитивно-регулярний діаметра , — кардинальне число його множини вершин , а — валентність графа. Визначимо множину матриць відстаней () розміру як:
Властивості матриць відстаней
де — одинична матриця; є звичайною матрицею суміжності графа ; , де є матрицею одиниць , де — масив перетинів дистанційно-регулярного графа і Існують дійсні числа , такі що для всіх , причому — кількість перетинів, тобто кількість вершин, розташованих на відстані від вершини і на відстані від вершини за умови відстані між вершинами і . Відмітимо, що , ,
Алгебра суміжності Нехай на транзитивно-регулярному графі діаметру задано , тобто матричну підалгебру поліномів матриці суміжності . Її розмірністю буде , а базисом — множина матриць відстаней .
Приклади Повні графи Циклічні графи Графи Мура, зокрема граф Петерсена і граф Гофмана — Синглтона Графи Геммінга Граф Перкеля Сильно регулярні графи Непарні графи
Примітки
Література