» » 12-клетка Татта

12-клетка Татта

13.01.2022


12-клетка Татта (граф Бенсона) — 3-регулярный граф с 126 вершинами и 189 рёбрами, названный в честь Уильяма Татта.

Является единственной (3-12)-клеткой; имеет хроматическое число 2 (двудольный), хроматический индекс 3, обхват 12 (как 12-клетки) и диаметр 6; число пересечений равно 170 и есть предположение, что этот граф является минимальным с данным числом пересечений.

Открыт Кларком Бенсоном в 1966 году.

Построение

12-клетка Татта является кубическим гамильтоновым графом и его можно определить LCF-кодом [17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]7.

Как доказали Коэн и Титс, есть, с точностью до изоморфизма, в точности два обобщённых шестиугольника порядка (2,2). Это разбитый шестиугольник Кэли H(2) и его двойственный (по точкам/прямым). Ясно, что оба имеют тот же самый граф инцидентности, который, фактически, изоморфен 12-клетке Татта.

11-клетка Балабана может быть построена путём отрезания от 12-клетки Татта маленького поддерева и удаления получившихся вершин степени два.

Алгебраические свойства

Автоморфизм группы 12-клетки Татта имеет порядок 12 096 и является полупрямым произведением проективной специальной унитарной группы PSU(3,3) с циклической группой Z/2Z. Группа действует транзитивно на рёбрах, но не на вершинах, что делает его полусимметричным графом, регулярным графом, который рёберно-транзитивен, но не вершинно транзитивен. Фактически, автоморфизм группы 12-клетки Татта сохраняет доли графа и действует просто на каждой из них. Такие графы называются бипримитивными и существует только пять кубических бипримитивных графов. Они называются графами Иванова — Иофиновой и они имеют порядки 110, 126, 182, 506 и 990.

Все кубические полусимметричные графы, содержащие вплоть до 768 вершин, известны. Согласно Кондеру, Малничу, Марушичу и Поточнику 12-клетка Татта является единственным полусимметричным графом с 126 вершинами и пятым наименьшим возможным кубическим полусимметричным графом после графа Грея, графа Иванова — Иофиновой с 110 вершинами, графа Любляны и графа с 120 вершинами с обхватом 8.

Характеристический многочлен 12-клетки Татта равен

( x − 3 ) x 28 ( x + 3 ) ( x 2 − 6 ) 21 ( x 2 − 2 ) 27 .   {displaystyle (x-3)x^{28}(x+3)(x^{2}-6)^{21}(x^{2}-2)^{27}. }

Граф является единственным с этим характеристическим многочленом, поэтому 12-клетка определяется его спектром.

Галерея

  • Хроматическое число 12-клетки Татта равно 2.

  • Хроматический индекс 12-клетки Татта равен 3.