Сильно регулярний граф

Види графів за їхніми автоморфізмами
відстанево-транзитивний	$\leftarrow$	сильно регулярний
$\downarrow$
симетричний (дуго-транзитивний)	$\leftarrow$	t-транзитивний, t ≥ 2
$\downarrow$(якщо зв'язний)
вершинно- та реберно-транзитивний	$\rightarrow$	реберно-транзитивний і регулярний	$\rightarrow$	реберно-транзитивний
$\downarrow$		$\downarrow$
вершинно-транзитивний	$\rightarrow$	регулярний
$\uparrow$
граф Келі		кососиметричний		асиметричний

У теорії графів сильно регулярний граф — граф, що має такі властивості: Нехай $G=(V,E)$ — регулярний граф з $v$ вершинами і степенем $k$. $G$ називають сильно регулярним, якщо існують цілі $\lambda$ і $\mu$ такі, що:

• будь-які дві суміжні вершини мають $\lambda$ спільних сусідів;
• будь-які дві несуміжні вершини мають $\mu$ спільних сусідів.

Графи такого виду іноді позначають як $srg(v,k,\lambda ,\mu )$.

Деякі автори виключають графи, які задовольняють умовам тривіально, а саме графи, які є незв'язним об'єднанням одного або більше повних графів одного розміру, і їх доповнення, графи Турана.

Сильно регулярний граф є дистанційно-регулярним з діаметром $2$, але тільки в тому випадку, коли $\mu$ не дорівнює нулю.

Властивості

• Чотири параметри в $srg(v,k,\lambda ,\mu )$ не є незалежними і мають задовольняти такій умові:

$(v-k-1)\mu =k(k-\lambda -1)$

Цю умову можна отримати дуже просто, якщо підрахувати аргументи так:

• Уявімо, що вершини графа лежать на трьох рівнях. Виберемо будь-яку вершину як корінь, рівень $0$. Тоді її $k$ сусідніх вершин лежать на рівні $1$, а решта лежать на рівні $2$.
• Вершини рівня $1$ пов'язані безпосередньо з коренем, а тому вони повинні мати $\lambda$ інших сусідів, які є сусідами кореня, і ці сусіди повинні також лежати на рівні $1$. Оскільки кожна вершина має степінь $k$, є $k-\lambda -1$ ребер, що з'єднують кожну вершину рівня $1$ з рівнем $2$.
• Вершини рівня $2$ не пов'язані безпосередньо з коренем, а тому вони повинні мати $\mu$ спільних сусідів з коренем, і всі ці сусіди повинні лежати на рівні $1$. Таким чином, $\mu$ вершин рівня $1$ пов'язані з кожною вершиною рівня $2$ і кожна з $k$ вершин на рівні 1 пов'язана з $k-\lambda -1$ вершин на рівні $2$. Отримуємо, що число вершин на рівні $2$ дорівнює $k(k-\lambda -1)/\mu$.
• Повне число вершин на всіх трьох рівнях, таким чином, дорівнює $v=1+k+k(k-\lambda -1)/\mu$ і, після перетворення, маємо $(v-k-1)\mu =k(k-\lambda -1)$.

• Нехай $\mathbf {I}$ позначає одиничну матрицю (порядку $v$) і нехай $\mathbf {J}$ позначає матрицю, всі елементи якої рівні $1$. Матриця суміжності $\mathbf {A}$ сильно регулярного графа має такі властивості:
  • $\mathbf {A} \mathbf {J} =k\mathbf {J}$
    (Це тривіальне перефразування вимоги рівності степеня вершин числу $k$).
  • ${\mathbf {A} }^{2}+(\mu -\lambda ){\mathbf {A} }+(\mu -k){\mathbf {I} }=\mu {\mathbf {J} }$
    (Перший член, ${\mathbf {A} }^{2}$, дає число двокрокових шляхів з будь-якої вершини до всіх вершин. Другий член, $(\mu -\lambda ){\mathbf {A} }$, відповідає безпосередньо пов'язаним ребрам. Третій член,$(\mu -k){\mathbf {I} }$, відповідає тривіальним парам, коли вершини в парі ті ж самі).
• Граф має рівно три власних значень:
  • $k$, кратність якого дорівнює 1
  • ${\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]$, кратність якого дорівнює ${\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
  • ${\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]$, кратність якого дорівнює ${\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
• Сильно регулярні графи, для яких $2k+(v-1)(\lambda -\mu )=0$, називають конференсними зважаючи на їх зв'язки зі симетричними конференсними матрицями. Число незалежних параметрів цих графів скорочується до одного — $srg\left(v,{\frac {v-1}{2}},{\frac {v-5}{4}},{\frac {v-1}{4}}\right)$.
• Сильно регулярні графи, для яких $2k+(v-1)(\lambda -\mu )\neq 0$, мають цілочисельні власні значення з нерівними кратностями.
• Доповнення $srg(v,k,\lambda ,\mu )$ також сильно регулярне — це $srg(v,v-k-1,v-2-2k+\mu ,v-2k+\lambda )$.

Приклади

Граф Пелі 13-го порядку, сильно регулярний граф із параметрами srg(13,6,2,3).

• $srg(5,2,0,1)$ — цикл довжини 5;
• $srg(10,3,0,1)$ — граф Петерсена;
• $srg(16,5,0,2)$ — граф Клебша;
• $srg(16,6,2,2)$ — граф Шрікханде, який не є дистанційно-транзитивним;
• $srg(27,10,1,5)$ — реберний граф узагальненого чотирикутника $GQ(2,4)$;
• $srg(27,16,10,8)$ — граф Шлефлі;
• $srg(28,12,6,4)$ — графи Чана;
• $srg(50,7,0,1)$ — граф Гофмана — Синглтона;
• $srg(56,10,0,2)$ — граф Гевірца;
• $srg(77,16,0,4)$ — граф M₂₂;
• $srg(81,20,1,6)$ — граф Брауера — Хемерса;
• $srg(100,22,0,6)$ — граф Гіґмана — Сімса;
• $srg(162,56,10,24)$ — локальний граф Маклафліна;
• $srg(q,{\frac {q-1}{2}},{\frac {q-5}{4}},{\frac {q-1}{4}})$ — граф Пелі порядку $q$;
• $srg(n^{2},2n-2,n-2,2)$ — $n\times n$ квадратний туровий граф.

Сильно регулярний граф називається простим, якщо і граф, і його доповнення зв'язні. Всі наведені вище графи прості, оскільки в іншому випадку $\mu =0$ або $\mu =k$.

Графи Мура

Сильно регулярні графи з $\lambda =0$ не містять трикутників. Крім повних графів з числом вершин менше 3 і всіх повних двочасткових графів сім наведених вище — це всі відомі графи цього виду. Сильно регулярні графи з $\lambda =0$ і $\mu =1$ — це графи Мура з обхватом 5. Знову ж, три графи, наведені вище, з параметрами $srg(5,2,0,1)$, $srg(10,3,0,1)$ і $srg(50,7,0,1)$— це єдині відомі графи цього виду. Єдина інша можлива множина параметрів, відповідна графам Мура — це $srg(3250,57,0,1)$. Невідомо, чи існує такий граф, і якщо існує, чи єдиний він.

Див. також

• Матриця суміжності Зайделя
• Два-граф
• Граф Геймса
• Конференційний граф

Література

• Brouwer A.E., Cohen A.M., Neumaier A. Distance Regular Graphs. — Berlin, New York : Springer-Verlag, 1989. — ISBN 3-540-50619-5.
• Brouwer A.E., Haemers W.H. Spectra of Graphs. — New York : Springer-Verlag, 2012. — Т. 418. — (Universitext) — ISBN 978-1-4614-1938-9.
• Godsil C., Royle G. Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — ISBN 0-387-95241-1.

Посилання

• Eric W. Weisstein, Стаття Mathworld з багатьма прикладами.
• Гордон Ройл, Список великих графів і сімейств.
• Andries E. Brouwer, Параметри сильно регулярних графів.
• Brendan McKay, Колекція графів.
• Ted Spence, Strongly regular graphs on at most 64 vertices.