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

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

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

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

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

Построение

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

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

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

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

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

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

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

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

Галерея

Примечания
  1. Exoo, Jajcay, 2008.
  2. Weisstein, Eric W. Tutte 12-cage (англ.) на сайте Wolfram MathWorld.
  3. последовательность A052453 в OEIS
  4. Exoo, 2006.
  5. Pegg, Exoo, 2009.
  6. Benson, 1966, с. 1091—1094.
  7. Polster, 1998, с. 179.
  8. Balaban, 1973, с. 1033—1043.
  9. Иванов, Иофинова, 1985, с. 123—134.
  10. Conder, Malnič, Marušič, Potočnik, 2006, с. 255–294.

Литература
  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.