Граф Шлефли - Schläfli graph

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

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

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

Граф Шлефли рассматривается как 1-скелет 2₂₁ многогранник. Эта симметричная проекция содержит 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 прямых, граф пересечений которых является граф короны в котором две прямые имеют непересекающиеся окрестности. Соответственно, в графе Шлефли каждое ребро УФ принадлежит однозначно подграфу в виде Декартово произведение из полные графики K₆ ${ displaystyle square}$ K₂ таким образом, что ты и v принадлежат к разным K₆ подграфы продукта. Граф Шлефли имеет всего 36 подграфов этой формы, один из которых состоит из векторов нуля или единицы в восьмимерном представлении, описанном выше.^[2]

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

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

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

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

Примечания

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

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

[hs93-1] а ^б Холтон и Шихан (1993).

[bn92-2] а ^б Bussemaker & Neumaier (1992).

[3] Кэмерон и ван Линт (1991). Обратите внимание, что Кэмерон и ван Линт используют альтернативное определение этих графов, в котором граф Шлефли и граф Клебша являются дополнен из их определений здесь.

[4] Бучак (1980); Кэмерон (1980); Девильеры (2002).

[1]

[2]

[3]

[4]