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

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

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

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

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

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

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

Властивості

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

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

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

    • (Це тривіальне перефразування вимоги рівності степеня вершин числу ).

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

Приклади

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

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

Графи Мура

Докладніше: Граф Мура

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

Див. також

Примітки

  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.

Посилання