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

Дистанційно-регулярний граф (англ. distance-regular graph) — це такий регулярний граф, у якого для двох будь-яких вершин і , розташованих на однаковій відстані одна від одної, кількість вершин інцидентних до , і при цьому розташованих на відстані від вершини , залежить тільки від відстані між вершинами і ; більш того кількість інцидентних до вершин, розташованих на відстані від вершини , також залежить тільки від відстані .

Граф Шрікханде — дистанційно-регулярний граф, який не є дистанційно-транзитивним

Визначення

Визначення дистанційно-регулярного графа[1][2]:

Дистанційно-регулярний граф — це неорієнтований, зв'язний, обмежений, регулярний граф діаметром , для якого справедливо, що існують числа

такі, що для кожної пари вершин , відстань між якими справедливо:

(1) число вершин, інцидентних , розташованих на відстані від є (): (2) число вершин, інцидентних , розташованих на відстані від є ().

Масив є масив перетинів дистанційно-регулярного графа, де  — валентність графа.

Дистанційно-регулярний граф з діаметром 2 є сильно регулярним[1] і обернене твердження теж істинне (за умови, що граф є зв'язним).

Дистанційно-регулярний і дистанційно-транзитивний графи

На перший погляд дистанційно-транзитивний граф і дистанційно-регулярний граф є дуже близькими поняттями. Дійсно, кожен дистанційно-транзитивний граф є дистанційно-регулярним. Однак їх природа різна. Якщо дистанційно-транзитивний граф визначається виходячи з симетрії графа через умову автоморфізму, то дистанційно-регулярний граф визначається з умови його комбінаторної регулярності[1].

Автоморфізм дистанційно-транзитивного графа викликає його регулярність, і відповідно, наявність чисел перетинів . Однак, якщо існує комбінаторна регулярність, і визначені числа перетинів для графа, і він дистанційно-регулярний, то автоморфізм з цього не випливає.

Якщо з дистанційно-транзитивності графа випливає його дистанційно-регулярність, то зворотне не істинне.

Це доведено 1969 року, ще до введення в ужиток терміна дистанційно-транзитивний граф, групою радянських математиків[3] (Адельсон-Вельський Г. М., Вейсфейлер Б. Ю., Леман А. А., Фараджев І. А.). Найменший дистанційно-регулярний граф, який не є дистанційно-транзитивним — це граф Шрікханде. Єдиний тривалентний граф цього типу — це 12-клітка Татта, граф зі 126 вершинами.

Масив перетинів дистанційно-регулярного графа

нехай  — транзитивно-регулярний граф діаметра і порядку , а і  — пара вершин, віддалених одна від одної на відстань . Тоді множину вершин, інцидентних до можна розбити на три множини , і , залежно від їх відстані до вершини , де вершина інцидентна до :

.

кардинальні числа цих множин є числами перетинів, а масив перетинів є

якщо  — валентність графа, то , а . Більш того, . Тому масив перетинів записується як:

Властивості масиву перетинів дистанційно-регулярного графа

Згідно з оглядом[4][5]:

  • Кожна вершина має стале число вершин , віддалених від неї на відстань , причому і для всіх ;
  • порядок графа дорівнює ;
  • число вершин, віддалених від кожної вершини на відстан виражається через числа перетинів як для всіх ;
  • добуток числа вершин, віддалених від довільної вершини на відстань , на порядок графа є парним числом для всіх ;
  • добуток числа вершин, віддалених від довільної вершини на відстані , на кількість перетинів є парним числом для всіх ;
  • добуток числа перетинів на порядок графа і на його валентність ділитися на 6;
  • для чисел перетинів виконується ;
  • для чисел перетинів виконується ;
  • якщо , то ;
  • є таке , що і .

Матриці відстаней транзитивно-регулярного графа

Нехай граф  — транзитивно-регулярний діаметра ,  кардинальне число його множини вершин , а  — валентність графа. Визначимо[1] множину матриць відстаней (англ. distance matrices) розміру як:

Властивості матриць відстаней[1]

  • де  одинична матриця;
  • є звичайною матрицею суміжності графа ;
  • , де є матрицею одиниць
  • , де  — масив перетинів дистанційно-регулярного графа і
  • Існують дійсні числа , такі що для всіх , причому  — кількість перетинів, тобто кількість вершин, розташованих на відстані від вершини і на відстані від вершини за умови відстані між вершинами і . Відмітимо, що , ,

Алгебра суміжності

Нехай на транзитивно-регулярному графі діаметру задано алгебру суміжності [6], тобто матричну підалгебру поліномів матриці суміжності . Її розмірністю буде , а базисом — множина матриць відстаней [7].

Приклади

Примітки

Література

  • Адельсон-Вельский Г.М., Вейсфелер Б.Ю., Леман А.А., Фараджев И.А. Об одном примере графа, не имеющнго транзитивной группы автоморфизмов // Доклады Академии наук.  1969. Т. 185, № 5 (3 березня). С. 975—976.
  • Biggs N.L. Algebraic Graph Theory. — 2nd. — Cambridge University Press, 1993. — 205 с.
  • Brouwer A., Cohen A.M., Neumaier A. Distance Regular Graphs. — Berlin, New York : Springer-Verlag, 1989. — ISBN 3-540-50619-5, 0-387-50619-5.
  • van Dam E.R., Koolen J.H., Tanaka H. Distance-regular graphs // The Electronic Journal of Combinatorics : dynamic surveys.  2006. No. DS22 (3 March).
  • Godsil C. D. Algebraic combinatorics. — N. Y. : Chapman and Hall, 1993. — С. xvi+362. — (Chapman and Hall Mathematics Series) — ISBN 0-412-04131-6.
  • Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction. — 2nd. — Combridge : Combridge University Press, 2016. — 188 с.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.