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

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

Дистанційно-регулярний граф (Шаблон:Lang-en) — це такий регулярний граф, у якого для двох будь-яких вершин $v$ і $w$, розташованих на однаковій відстані $j$ одна від одної, кількість вершин інцидентних до $v$, і при цьому розташованих на відстані $j-1$ від вершини $w$, залежить тільки від відстані $j$ між вершинами $v$ і $w$; більш того кількість інцидентних до $v$ вершин, розташованих на відстані $j+1$ від вершини $w$, також залежить тільки від відстані $j$.

Визначення

Визначення дистанційно-регулярного графаШаблон:SfnШаблон:Sfn:

Дистанційно-регулярний граф — це неорієнтований, зв'язний, обмежений, регулярний граф $\mathrm{\Gamma }=(V,E)$ діаметром $D$, для якого справедливо, що існують числа

$b_0=k{b}_1,\dots ,b_{D-1}{c}_1=1,c_2,\dots ,c_D$

такі, що для кожної пари вершин $(u,v)$, відстань між якими $d(u,v)=j$ справедливо:

(1) число вершин, інцидентних $u$, розташованих на відстані $j-1$ від $v$ є $c_j$ ($1⩽j⩽D$): (2) число вершин, інцидентних $u$, розташованих на відстані $j+1$ від $v$ є $b_j$ ($0⩽j⩽D-1$).

Масив $\{k,b_1,\dots ,b_{D-1};1,c_2,\dots ,c_D\}$ є масив перетинів дистанційно-регулярного графа, де $k$ — валентність графа.

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

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

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

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

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

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

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

нехай $\mathrm{\Gamma }=(V,E)$ — транзитивно-регулярний граф діаметра $D$ і порядку $n$, а $u$ і $v$ — пара вершин, віддалених одна від одної на відстань $d=(u,v)$. Тоді множину вершин, інцидентних до $u$ можна розбити на три множини $A$, $B$ і $C$, залежно від їх відстані $d(v,w)$ до вершини $v$, де вершина $w$ інцидентна до $u$:

$\{w\in A:d(v,w)=j\},\{w\in B:d(v,w)=j+1\},\{w\in C:d(v,w)=j-1\}$ .

кардинальні числа $|A|,|B|,|C|$ цих множин $a_j=|A|,b_j=|B|,c_j=|C|$ є числами перетинів, а масив перетинів є

$\iota (\mathrm{\Gamma })=\left\{\begin{array}{cccccc}\ast & c_1& c_2& \dots & c_{D-1}& c_D\\ a_0& a_1& a_2& \dots & a_{D-1}& a_D\\ b_0& b_1& b_2& \dots & b_{D-1}& \ast \end{array}\right\}$

якщо $k$ — валентність графа, то $b_0=k$, $c_0=0$ а $c_1=1$. Більш того, $a_i+b_i+c_i=k$ . Тому масив перетинів записується як:

$\iota (\mathrm{\Gamma })=\left\{\begin{array}{c}k,b_1,\dots ,b_{D-1};1,c_2,\dots ,c_D\end{array}\right\}$

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

Згідно з оглядомШаблон:SfnШаблон:Sfn:

• Кожна вершина має стале число вершин $k_j$, віддалених від неї на відстань $j$, причому $k_0=1$ і $k_{j+1}=\frac{b_j{k}_j}{c_{j+1}}$ для всіх $j=0,1,\dots ,D-1$;
• порядок графа $n$ дорівнює $n=k_0+k_1+\dots +k_D$;
• число вершин, віддалених від кожної вершини на відстан $j+1$ виражається через числа перетинів як $k_{j+1}=\frac{b_0{b}_1\dots b_j}{c_1{c}_2\dots c_{j+1}}$ для всіх $j=0,1,\dots ,D-1$;
• добуток $k_j\cdot n$ числа вершин, віддалених від довільної вершини на відстань $j$, на порядок графа є парним числом для всіх $j=1,2,\dots ,D$;
• добуток $k_j\cdot a_j$ числа вершин, віддалених від довільної вершини на відстані $j$, на кількість перетинів $a_j$ є парним числом для всіх $j=1,2,\dots ,D$;
• добуток $a_1\cdot n\cdot k$ числа перетинів $a_1$ на порядок графа і на його валентність ділитися на 6;
• для чисел перетинів $c_j$ виконується $1⩽c_1⩽c_2⩽\dots ⩽c_D$;
• для чисел перетинів $b_j$ виконується $k=b_0⩾b_1⩾b_2\dots ⩾b_{D-1}$;
• якщо $i+j⩽D$, то $c_i⩽b_j$;
• є таке $i$, що $k_0⩽k_1⩽\dots ⩽k_i$ і $k_{i+1}⩾k_{i+2}⩾\dots ⩾k_D$.

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

Нехай граф $\mathrm{\Gamma }(V,E)$ — транзитивно-регулярний діаметра $D$, $n=|V|$ — кардинальне число його множини вершин $V$, а $k$ — валентність графа. ВизначимоШаблон:Sfn множину матриць відстаней (Шаблон:Lang-en) розміру $n\times n$$\{{𝐀}_0,{𝐀}_1,\dots ,{𝐀}_D\}$ як:

${\left({𝐀}_h\right)}_{r,s}=\{\begin{array}{cc}1& :d(v_r,v_s)=h,\\ 0& :d(v_r,v_s)\ne h\end{array}$

Властивості матриць відстанейШаблон:Sfn

• ${𝐀}_0={𝐈}_n$ де ${𝐈}_n$ — одинична матриця;
• ${𝐀}_1=𝐀$ є звичайною матрицею суміжності графа $\mathrm{\Gamma }(V,E)$;
• ${𝐀}_0+{𝐀}_1+{𝐀}_2+\dots +{𝐀}_D={𝐉}_n$, де ${𝐉}_n$ є матрицею одиниць
• $𝐀{𝐀}_i=b_{i-1}{𝐀}_{i-1}+a_i{𝐀}_i+c_{i+1}{𝐀}_{i+1}$, де $\left\{\begin{array}{c}k,b_1,\dots ,b_{d-1};1,c_2,\dots ,c_d\end{array}\right\}$ — масив перетинів дистанційно-регулярного графа і $a_i=k-b_i-c_i$
• Існують дійсні числа $p_{i,j}^h,(i,j,h=0,1,\dots ,D)$, такі що ${𝐀}_i{𝐀}_j=\sum _{h=0}^D{p}_{i,j}^h{𝐀}_h$ для всіх $(i,j=0,1,\dots ,D)$, причому $p_{i,j}^h$ — кількість перетинів, тобто кількість вершин, розташованих на відстані $j$ від вершини $v$ і на відстані $i$ від вершини $w$ за умови відстані $h$ між вершинами $v$ і $w$. Відмітимо, що $p_{1,i-1}^i=c_i$, $p_{1,i}^i=a_i$, $p_{1,i+1}^i=b_i$

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

Нехай на транзитивно-регулярному графі $\mathrm{\Gamma }$ діаметру $D$ задано Шаблон:Нп $𝔸(\mathrm{\Gamma })$Шаблон:Sfn, тобто матричну підалгебру $M_{n\times n}(ℝ)$ поліномів матриці суміжності $𝐀$. Її розмірністю буде $dim(𝔸)=D+1$, а базисом — множина матриць відстаней $\{{𝐀}_0,{𝐀}_1,\dots ,{𝐀}_D\}$Шаблон:Sfn.

Приклади

• Повні графи
• Циклічні графи
• Графи Мура, зокрема граф Петерсена і граф Гофмана — Синглтона
• Графи Геммінга
• Сильно регулярні графи
• Непарні графи

Література

• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга