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

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

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

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

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

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

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

Властивості

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

${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$

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

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

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

Приклади

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

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

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

Графи Мура

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

Див. також

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

Примітки

1. Brouwer, 2012.
2. Godsil, 2001.
3. Weisstein, Eric W. Schläfli graph(англ.) на сайті Wolfram MathWorld.

Література

• 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 з багатьма прикладами.
• Гордон Ройл^[en], Список великих графів і сімейств.
• Andries E. Brouwer^[en], Параметри сильно регулярних графів.
• Brendan McKay^[en], Колекція графів.
• Ted Spence, Strongly regular graphs on at most 64 vertices.