12-клетка Татта
Шаблон:Граф 12-клетка Татта (граф БенсонаШаблон:Sfn) — 3-регулярный граф с 126 вершинами и 189 рёбрами, названный в честь Уильяма Татта[1].
Является единственной (3-12)-клеткой[2]; имеет хроматическое число 2 (двудольный), хроматический индекс 3, обхват 12 (как 12-клетки) и диаметр 6; число пересечений равно 170 и есть предположение, что этот граф является минимальным с данным числом пересеченийШаблон:SfnШаблон:Sfn.
Открыт Кларком Бенсоном в 1966 годуШаблон:Sfn.
Построение
12-клетка Татта является кубическим гамильтоновым графом и его можно определить LCF-кодом [17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]7Шаблон:Sfn.
Как доказали Коэн и Титс, есть, с точностью до изоморфизма, в точности два обобщённых шестиугольника порядка (2,2). Это разбитый шестиугольник Кэли H(2) и его двойственный (по точкам/прямым). Ясно, что оба имеют тот же самый граф инцидентности, который, фактически, изоморфен 12-клетке ТаттаШаблон:Sfn.
11-клетка Балабана может быть построена путём отрезания от 12-клетки Татта маленького поддерева и удаления получившихся вершин степени дваШаблон:Sfn.
Алгебраические свойства
Автоморфизм группы 12-клетки Татта имеет порядок 12 096 и является полупрямым произведением Шаблон:Не переведено 5 PSU(3,3) с циклической группой Z/2ZШаблон:Sfn. Группа действует транзитивно на рёбрах, но не на вершинах, что делает его полусимметричным графом, регулярным графом, который рёберно-транзитивен, но не вершинно транзитивен. Фактически, автоморфизм группы 12-клетки Татта сохраняет доли графа и действует просто на каждой из них. Такие графы называются бипримитивными и существует только пять кубических бипримитивных графов. Они называются графами Иванова — Иофиновой и они имеют порядки 110, 126, 182, 506 и 990Шаблон:Sfn.
Все кубические полусимметричные графы, содержащие вплоть до 768 вершин, известны. Согласно Кондеру, Малничу, Марушичу и Поточнику 12-клетка Татта является единственным полусимметричным графом с 126 вершинами и пятым наименьшим возможным кубическим полусимметричным графом после графа Грея, графа Иванова — Иофиновой с 110 вершинами, графа Любляны и графа с 120 вершинами с обхватом 8Шаблон:Sfn.
Характеристический многочлен 12-клетки Татта равен
Граф является единственным с этим характеристическим многочленом, поэтому 12-клетка определяется его спектром.
Галерея
-
Хроматическое число 12-клетки Татта равно 2. -
Хроматический индекс 12-клетки Татта равен 3.
