12-клетка Татта (12-tlymtg Mgmmg)
| 12-клетка Татта | |
|---|---|
 | |
| Назван в честь | Уильяма Татта |
| Вершин | 126 |
| Рёбер | 189 |
| Радиус | 6 |
| Диаметр | 6 |
| Обхват | 12 |
| Автоморфизмы | 12096 |
| Хроматическое число | 2 |
| Хроматический индекс | 3 |
| Свойства |
Кубический Клетка Гамильтонов Полусимметричный Двудольный |
 Медиафайлы на Викискладе | |
12-клетка Татта (граф Бенсона[1]) — 3-регулярный граф с 126 вершинами и 189 рёбрами, названный в честь Уильяма Татта[2].
Является единственной (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-клетка определяется его спектром.
Галерея
[править | править код]-
Хроматическое число 12-клетки Татта равно 2. -
Хроматический индекс 12-клетки Татта равен 3.
Примечания
[править | править код]- ↑ 1 2 3 Exoo, Jajcay, 2008.
- ↑ Weisstein, Eric W. Tutte 12-cage (англ.) на сайте Wolfram MathWorld.
- ↑ последовательность A052453 в OEIS
- ↑ Exoo, 2006.
- ↑ Pegg, Exoo, 2009.
- ↑ Benson, 1966, с. 1091—1094.
- ↑ Polster, 1998, с. 179.
- ↑ Balaban, 1973, с. 1033—1043.
- ↑ Иванов, Иофинова, 1985, с. 123—134.
- ↑ 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.