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

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

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

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

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

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

Сильно регулярний граф є дистанційно-регулярним з діаметром $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)$.

• Нехай $𝐈$ позначає одиничну матрицю (порядку $v$) і нехай $𝐉$ позначає матрицю, всі елементи якої рівні $1$. Матриця суміжності $𝐀$ сильно регулярного графа має такі властивості:
  • $𝐀𝐉=k𝐉$
    (Це тривіальне перефразування вимоги рівності степеня вершин числу $k$).
  • ${𝐀}^2+(\mu -\lambda )𝐀+(\mu -k)𝐈=\mu 𝐉$
    (Перший член, ${𝐀}^2$, дає число двокрокових шляхів з будь-якої вершини до всіх вершин. Другий член, $(\mu -\lambda )𝐀$, відповідає безпосередньо пов'язаним ребрам. Третій член,$(\mu -k)𝐈$, відповідає тривіальним парам, коли вершини в парі ті ж самі).
• Граф має рівно три власних значень:
  • $k$, кратність якого дорівнює 1
  • $\frac{1}{2}[(\lambda -\mu )+\sqrt{(\lambda -\mu {)}^2+4(k-\mu )}]$, кратність якого дорівнює $\frac{1}{2}[(v-1)-\frac{2k+(v-1)(\lambda -\mu )}{\sqrt{(\lambda -\mu {)}^2+4(k-\mu )}}]$
  • $\frac{1}{2}[(\lambda -\mu )-\sqrt{(\lambda -\mu {)}^2+4(k-\mu )}]$, кратність якого дорівнює $\frac{1}{2}[(v-1)+\frac{2k+(v-1)(\lambda -\mu )}{\sqrt{(\lambda -\mu {)}^2+4(k-\mu )}}]$
• Сильно регулярні графи, для яких $2k+(v-1)(\lambda -\mu )=0$, називають конференсними зважаючи на їх зв'язки зі симетричними конференсними матрицями. Число незалежних параметрів цих графів скорочується до одного — $srg(v,\frac{v-1}{2},\frac{v-5}{4},\frac{v-1}{4})$.
• Сильно регулярні графи, для яких $2k+(v-1)(\lambda -\mu )\ne 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)$. Невідомо, чи існує такий граф, і якщо існує, чи єдиний він.

Див. також

• Шаблон:Не перекладено
• Два-граф
• Граф Геймса
• Конференційний граф

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Посилання

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