Сильно регулярний граф
регулярний граф із v вершинами і степенем k, в якого число спільних сусідів залежить тільки від суміжності пари вершин / З Вікіпедії, безкоштовно encyclopedia
У теорії графів сильно регулярний граф — граф, що має такі властивості: Нехай — регулярний граф з
вершинами і степенем
.
називають сильно регулярним, якщо існують цілі
і
такі, що:
- будь-які дві суміжні вершини мають
спільних сусідів;
- будь-які дві несуміжні вершини мають
спільних сусідів.
Коротка інформація
Види графів за їхніми автоморфізмами | ||||
відстанево-транзитивний | сильно регулярний | |||
симетричний (дуго-транзитивний) | t-транзитивний, t ≥ 2 | |||
вершинно- та реберно-транзитивний[en] | реберно-транзитивний і регулярний | реберно-транзитивний | ||
вершинно-транзитивний | регулярний | |||
граф Келі | кососиметричний[en] | асиметричний |
Закрити
Графи такого виду іноді позначають як .
Деякі автори виключають графи, які задовольняють умовам тривіально, а саме графи, які є незв'язним об'єднанням одного або більше повних графів одного розміру[1][2], і їх доповнення, графи Турана.
Сильно регулярний граф є дистанційно-регулярним з діаметром , але тільки в тому випадку, коли
не дорівнює нулю.