WikiDer > Граф Шлефли

Schläfli graph
Граф Шлефли
Schläfli graph.svg
Вершины27
Края216
Радиус2
Диаметр2
Обхват3
Автоморфизмы51840
Хроматическое число9
ХарактеристикиСильно регулярный
Без когтей
Гамильтониан
Таблица графиков и параметров

в математический поле теория графов, то Граф Шлефли, названный в честь Людвиг Шлефли, это 16-обычный неориентированный граф с 27 вершинами и 216 ребрами. Это сильно регулярный граф с параметрами srg (27, 16, 10, 8).

Строительство

Граф Шлефли рассматривается как 1-скелет 221 многогранник. Эта симметричная проекция содержит 2 кольца по 12 вершин и 3 вершины, совпадающие в центре.

В граф пересечений из 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]

С другой стороны, этот график можно рассматривать как дополнение к графику коллинеарности обобщенный четырехугольник GQ (2, 4).

Подграфы и окрестности

В район любой вершины в графе Шлефли образует подграф с 16 вершинами, в котором каждая вершина имеет 10 соседей (числа 16 и 10 взяты из параметров графа Шлефли как сильно регулярного графа). Все эти подграфы изоморфный к дополнительный граф из Граф Клебша.[1][3] Поскольку граф Клебша без треугольников, граф Шлефли есть без когтей. Он играет важную роль в теории структур для графов без клешней. Чудновский и Сеймур (2005).

Любые две косые линии из этих 27 принадлежат единственному Шлефли двойная шестерка конфигурация, набор из 12 прямых, граф пересечений которых является граф короны в котором две прямые имеют непересекающиеся окрестности. Соответственно, в графе Шлефли каждое ребро УФ принадлежит однозначно подграфу в виде Декартово произведение из полные графики K6 K2 таким образом, что ты и v принадлежат к разным K6 подграфы продукта. Граф Шлефли имеет всего 36 подграфов этой формы, один из которых состоит из векторов нуля или единицы в восьмимерном представлении, описанном выше.[2]

Ультраоднородность

Граф определяется как k-ультраоднородный если каждый изоморфизм между двумя своими индуцированные подграфы не более k вершины могут быть расширены до автоморфизм всего графа. Если граф 5-ультраоднородный, то он ультраоднороден для каждого k; единственный конечный связаны графики этого типа полные графики, Графики Турана, 3 × 3 графики ладьи, а 5-цикл. Бесконечный График Rado счетно ультраоднороден. Есть только два связных графа, которые являются 4-ультраоднородными, но не 5-ультраоднородными: граф Шлефли и его дополнение. Доказательство опирается на классификация конечных простых групп.[4]

Смотрите также

  • График Госсета - содержит граф Шлефли как индуцированный подграф окрестности любой вершины.

Примечания

  1. ^ а б Холтон и Шихан (1993).
  2. ^ а б Bussemaker & Neumaier (1992).
  3. ^ Кэмерон и ван Линт (1991). Обратите внимание, что Кэмерон и ван Линт используют альтернативное определение этих графов, в котором граф Шлефли и граф Клебша являются дополнен из их определений здесь.
  4. ^ Бучак (1980); Кэмерон (1980); Девильеры (2002).

Рекомендации

  • Бучак, Дж. М. Дж. (1980), Теория конечных групп, Кандидат наук. диссертация, Оксфордский университет. Как цитирует Девильеры (2002).
  • Bussemaker, F.C .; Neumaier, A. (1992), "Исключительные графы с наименьшим собственным значением-2 и связанные проблемы", Математика вычислений, 59 (200): 583–608, Дои:10.1090 / S0025-5718-1992-1134718-6.
  • Кэмерон, Питер Джефсон (1980), «6-транзитивные графы», Журнал комбинаторной теории, серия B, 28 (2): 168–179, Дои:10.1016/0095-8956(80)90063-5. Как цитирует Девильеры (2002).
  • Кэмерон, Питер Джефсон; ван Линт, Якобус Хендрикус (1991), Конструкции, графики, коды и их ссылки, Студенческие тексты Лондонского математического общества, 22, Cambridge University Press, стр. 35, ISBN 978-0-521-41325-1.
  • Чудновский, Мария; Сеймур, Пол (2005), "Структура графов без клешней", Обзоры по комбинаторике 2005 г. (PDF), Лондонская математика. Soc. Lecture Note Ser., 327, Кембридж: Cambridge Univ. Press, стр. 153–171, МИСТЕР 2187738.
  • Девиллерс, Алиса (2002), Классификация некоторых однородных и сверходнородных структур., Кандидат наук. диссертация, Université Libre de Bruxelles.
  • Холтон, Д. А .; Шихан, Дж. (1993), График Петерсена, Издательство Кембриджского университета, стр. 270–271.

внешняя ссылка