Граф Шлефли — 16-регулярный ненаправленный граф с 27 вершинами и 216 рёбрами. Граф назван в честь Людвига Шлефли. Это сильно регулярный граф с параметрами srg(27, 16, 10, 8).
Конструкция Граф пересечений 27 прямых на кубической поверхности является дополнением графа Шлефли. Таким образом, две вершины смежны в графе Шлефли тогда и только тогда, когда соответствующие прямые являются скрещивающимися
Граф Шлефли можно получить также из системы восьмимерных векторов (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.
Подграфы и окрестности
Окрестность любой вершины графа Шлефли есть подграф с 16 вершинами, в котором каждая вершина имеет 10 соседних вершин (числа 16 и 10 получаются как параметры графа Шлефли, когда он рассматривается как строго регулярный граф). Все эти подграфы изоморфны дополнению графа КлебшаНадо отметить, что Камерон и ван Линт использовали другие определения этих графов, по которому и граф Шлефли и граф Клебша являются дополнениями графам, определение которых дано здесь.. Поскольку граф Клебша не содержит треугольников, граф Шлефли не содержит клешней. Этот факт играет важную роль в структурной теории графов без клешней, разработанной Марией Чудновской и Полом Сеймуром.
Любые две скрещивающиеся прямые из этих 27 прямых принадлежат единственной конфигурации двойной шестёрки Шлефли — набору из 12 прямых, пересечение которых образует корону. Соответственно, в графе Шлефли каждое ребро uv принадлежит единственному подграфу, образованному прямым произведением полных графов K6 K2, в котором вершины u и v принадлежат различным K6 подграфам произведения. Граф Шлефли содержит 36 подграфов такого вида, один из которых состоит из векторов с координатами 0 и 1 в восьмимерном пространстве, как было описано выше.
Ультраоднородность
Граф называется , если любой изоморфизм между двумя его порождёнными подграфами, содержащими не более k вершин, может быть продолжен до автоморфизма всего графа. Если граф 5-ультраоднороден, он ультраоднороден для любого k. Единственными связными конечными графами этого типа являются полные графы, графы Турана, 3 × 3 ладейные графы и цикл с 5 вершинами. Бесконечный граф Радо счётно ультраоднороден.
Существует только два связных графа, которые 4-ультраоднородны, но не 5-ультраоднородны — это граф Шлефли и его дополнение. Доказательство основывается на классификации простых конечных групп.
Замечания
Ссылки
Andries E. Brouwer page.
Категория:Регулярные графы Категория:Графы, имеющие собственные названия