Граф Шлефлі
В теорія графів графом Шлефлі — 16-регулярний ненаправлений граф із 27 вершинами і 216 ребрами. Граф названо на честь Людвіга Шлефлі. Це сильно регулярний граф із параметрами srg(27, 16, 10, 8).
| Граф Шлефлі | |
|---|---|
 Граф Шлефлі | |
| Вершин | 27 |
| Ребер | 216 |
| Хроматичне число | 9 |
| Властивості | сильно регулярний без клешень |
Побудова
ред.Граф перетинів 27 прямих на кубічній поверхні є доповненням графа Шлефлі. Таким чином, дві вершини суміжні в графі Шлефлі тоді й лише тоді, коли відповідні прямі мимобіжні[1]
Граф Шлефлі можна отримати також із системи восьмивимірних векторів: (1, 0, 0, 0, 0, 0, 1, 0),
- (1, 0, 0, 0, 0, 0, 0, 1) і: (−1/2, −1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2), і 24 векторів, отриманих перестановкою перших шести координат цих трьох векторів. Ці 27 векторів відповідають вершинам графа Шлефлі. Дві вершини суміжні тоді й лише тоді, коли внутрішній добуток відповідних двох векторів дорівнює 1[2].
Підграфи і сусідство
ред.Окіл будь-якої вершини графа Шлефлі є підграфом з 16 вершинами, в якому кожна вершина має 10 сусідніх вершин (числа 16 і 10 виходять як параметри графа Шлефлі, коли його розглядаєти як строго регулярний граф). Всі ці підграфи ізоморфні доповненню графа Клебша[1][3]. Оскільки граф Клебша не містить трикутників, граф Шлефлі не містить клешень. Цей факт відіграє важливу роль у структурній теорії графів без клешень, яку розробили Марія Чудновська та Пол Сеймур[en][4].
Будь-які дві мимобіжні прямі з цих 27 прямих належать єдиній конфігурації подвійної шістки Шлефлі — набору з 12 прямих, перетин яких утворює корону. Відповідно, в графі Шлефлі кожне ребро uv належить єдиному підграфу, утвореному прямим добутком повного графа K6 K2, в якому вершини u і v належать різним K6 підграфам добутку. Граф Шлефлі містить 36 підграфів такого виду, один з яких складається з векторів з координатами 0 і 1 у восьмивимірному просторі, як описано вище[2].
Ультраоднорідність
ред.Граф називають k-ультраоднорідним[en], якщо будь-який ізоморфізм між двома його породженими підграфами, що містять не більше k вершин, можна продовжити до автоморфізму всього графа. Якщо граф 5-ультраоднорідний, він ультраоднорідний для будь-якого k. Єдині зв'язні скінченні графи цього типу — це повні графи, графи Турана, 3 × 3 турові графи і цикл із 5 вершинами. Нескінченний граф Радо зліченно ультраоднорідний. Існує тільки два зв'язних графи, які 4-ультраоднорідні, але не 5-ультраоднорідні — це граф Шлефлі і його доповнення. Доведення ґрунтується на класифікації простих скінченних груп[5][6][7].
Примітки
ред.- ↑ а б D. A. Holton, J. Sheehan. The Petersen Graph. — Cambridge University Press, 1993. — С. 270–271.
- ↑ а б F. C. Bussemaker, A. Neumaier. Exceptional graphs with smallest eigenvalue-2 and related problems // Mathematics of Computation. — 1992. — Т. 59, вип. 200. — С. 583–608. — DOI:.
- ↑ Peter Jephson Cameron, Jacobus Hendricus van Lint. Designs, graphs, codes and their links. — Cambridge University Press, 1991. — Т. 22. — С. 35. — ISBN 978-0-521-41325-1. Слід зауважити, що Камерон і ван Лінт використали інші визначення цих графів, за яким і граф Шлефлі і граф Клебша є доповненнями графів, визначення яких наведено тут.
- ↑ Maria Chudnovsky, Paul Seymour. Surveys in combinatorics 2005. — Cambridge Univ. Press, 2005. — Т. 327. — С. 153–171. Архівовано з джерела 9 червня 2010.
- ↑ J. M. J. Buczak. Finite Group Theory. — Oxford University, 1980.
- ↑ Peter Jephson Cameron. 6-transitive graphs // Journal of Combinatorial Theory, Series B. — 1980. — Т. 28. — С. 168–179.
- ↑ Alice Devillers. Classification of some homogeneous and ultrahomogeneous structures. — Université Libre de Bruxelles, 2002.
Посилання
ред.- Weisstein, Eric W. Граф Шлефлі(англ.) на сайті Wolfram MathWorld.
- Andries E. Brouwer page.[Архівовано 1 липня 2014 у Wayback Machine.]