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] ⁷ .

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

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

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

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

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

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

${\displaystyle (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. . — 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 : .