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

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

12-клетка Татта
Назван в честь	Уильяма Татта
Вершин	126
Рёбер	189
Радиус	6
Диаметр	6
Обхват	12
Автоморфизмы	12096
Хроматическое число	2
Хроматический индекс	3
Свойства	Кубический Клетка Гамильтонов Полусимметричный Двудольный
Медиафайлы на Викискладе

Является единственной (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]⁷.

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

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

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

Автоморфизм группы 12-клетки Татта имеет порядок 12 096 и является полупрямым произведением проективной специальной унитарной группы^[en] 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}.$$(x-3)x^{28}(x+3)(x^{2}-6)^{21}(x^{2}-2)^{27}.\$ 

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

ГалереяПравить

•  

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

•  

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

ЛитератураПравить

• Benson C. T. Minimal Regular Graphs of Girth 8 and 12 // Can. J. Math.. — 1966. — Вып. 18.
• Exoo G. Rectilinear Drawings of Famous Graphs. — 2006.
• Pegg E. T., Exoo G. Crossing Number Graphs // Mathematica J.. — 2009. — Вып. 11.
• Polster B. A. Geometrical Picture Book. — New York: Springer Science+Business Media, LLC, 1998. — (Universitext). — ISBN 978-1-4612-6426-2. — ISBN 978-1-4619-8526-2.
• Balaban A. T. Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages // Rev. Roumaine Math. — 1973. — Вып. 18.
• Geoffrey Exoo, Robert Jajcay. Dynamic cage survey // Electr. J. Combin. — 2008. — Вып. 15.
• Иванов А. A., Иофинова М. E. Бипримитивные кубические графы // Исследования по алгебраической теории комбинаторных объектов. — М., 1985. — С. 137–152. — (Серия: ВНИИ системных исследований. Труды семинара).
• Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. A census of semisymmetric cubic graphs on up to 768 vertices // Journal of Algebraic Combinatorics. — 2006. — Т. 23. — С. 255–294. — doi:10.1007/s10801-006-7397-3.