У теорії графів сильно регулярний граф — граф, що має такі властивості: Нехай  — регулярний граф з вершинами і степенем . називають сильно регулярним, якщо існують цілі і такі, що:

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

Графи такого виду іноді позначають як .

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

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

Властивості Чотири параметри в не є незалежними і мають задовольняти такій умові:

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

Уявімо, що вершини графа лежать на трьох рівнях. Виберемо будь-яку вершину як корінь, рівень . Тоді її сусідніх вершин лежать на рівні , а решта лежать на рівні . Вершини рівня пов'язані безпосередньо з коренем, а тому вони повинні мати інших сусідів, які є сусідами кореня, і ці сусіди повинні також лежати на рівні . Оскільки кожна вершина має степінь , є ребер, що з'єднують кожну вершину рівня з рівнем . Вершини рівня не пов'язані безпосередньо з коренем, а тому вони повинні мати спільних сусідів з коренем, і всі ці сусіди повинні лежати на рівні . Таким чином, вершин рівня пов'язані з кожною вершиною рівня і кожна з вершин на рівні 1 пов'язана з вершин на рівні . Отримуємо, що число вершин на рівні дорівнює . Повне число вершин на всіх трьох рівнях, таким чином, дорівнює і, після перетворення, маємо . Нехай позначає одиничну матрицю (порядку ) і нехай позначає матрицю, всі елементи якої рівні . Матриця суміжності сильно регулярного графа має такі властивості: (Це тривіальне перефразування вимоги рівності степеня вершин числу ). (Перший член, , дає число двокрокових шляхів з будь-якої вершини до всіх вершин. Другий член, , відповідає безпосередньо пов'язаним ребрам. Третій член,, відповідає тривіальним парам, коли вершини в парі ті ж самі). Граф має рівно три власних значень: , кратність якого дорівнює 1 , кратність якого дорівнює , кратність якого дорівнює Сильно регулярні графи, для яких , називають конференсними зважаючи на їх зв'язки зі симетричними конференсними матрицями. Число незалежних параметрів цих графів скорочується до одного — . Сильно регулярні графи, для яких , мають цілочисельні власні значення з нерівними кратностями. Доповнення також сильно регулярне — це .

Приклади

 — цикл довжини 5;  — граф Петерсена;  — граф Клебша;  — граф Шрікханде, який не є дистанційно-транзитивним;  — реберний граф узагальненого чотирикутника ;  — граф Шлефлі;  — графи Чана;  — граф Гофмана — Синглтона;  — граф Гевірца;  — граф M22;  — граф Брауера — Хемерса;  — граф Гіґмана — Сімса;  — ;  — граф Пелі порядку ;  — квадратний туровий граф.

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

Графи Мура

Сильно регулярні графи з не містять трикутників. Крім повних графів з числом вершин менше 3 і всіх повних двочасткових графів сім наведених вище — це всі відомі графи цього виду. Сильно регулярні графи з і  — це графи Мура з обхватом 5. Знову ж, три графи, наведені вище, з параметрами , і — це єдині відомі графи цього виду. Єдина інша можлива множина параметрів, відповідна графам Мура — це . Невідомо, чи існує такий граф, і якщо існує, чи єдиний він.

Див. також

Два-граф Граф Геймса Конференційний граф

Примітки

Література

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