Tutte 12-клеточный
| Tutte 12-клеточный | |
|---|---|
 Tutte 12-клеточный | |
| Назван в честь | WT Тутте |
| Вершины | 126 |
| Края | 189 |
| Радиус | 6 |
| Диаметр | 6 |
| Обхват | 12 |
| Автоморфизмы | 12096 |
| Хроматическое число | 2 |
| Хроматический индекс | 3 |
| Род | 17 |
| Характеристики | Кубическая клетка Гамильтониан Полусимметричный Двудольный |
| Таблица графиков и параметров | |
В математической области теории графов граф Бенсона или двенадцатиклеточный граф Тутта [1] — это 3- регулярный граф с 126 вершинами и 189 ребрами. Он назван в честь У. Т. Тутта . [2]
12-клетка Тутте — уникальная (3-12) -клетка (последовательность A052453 в OEIS ). Она была открыта CT Benson в 1966 году. [3] Она имеет хроматическое число 2 ( двудольная ), хроматический индекс 3, обхват 12 (как 12-клетка) и диаметр 6. Известно, что ее число пересечений меньше 165, см. Wolfram MathWorld. [4] [5]
Строительство
Двенадцатиклетка Тутта представляет собой кубический гамильтонов граф и может быть определена с помощью нотации LCF [17, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57, 11, –21, –57, 59, –17] 7 . [6]
С точностью до изоморфизма существуют ровно два обобщенных шестиугольника порядка (2,2), как доказали Коэн и Титц. Это расщепляемый шестиугольник Кэли H(2) и его двойственный точка-прямая. Очевидно, что оба они имеют один и тот же граф инцидентности, который фактически изоморфен 12-клетке Тутте. [1]
11-клетка Балабана может быть построена путем вырезания из 12-клетки Тутта путем удаления небольшого поддерева и подавления полученных вершин степени два. [7]
Алгебраические свойства
Группа автоморфизмов 12-клетки Тутта имеет порядок 12 096 и является полупрямым произведением проективной специальной унитарной группы PSU(3,3) с циклической группой Z /2 Z . [1] Она действует транзитивно на своих ребрах, но не на вершинах, что делает ее полусимметричным графом , регулярным графом, который является реберно-транзитивным , но не вершинно-транзитивным . Фактически, группа автоморфизмов 12-клетки Тутта сохраняет двудольные части и действует примитивно на каждой части. Такие графы называются бипримитивными графами, и существует только пять кубических бипримитивных графов; они называются графами Иофиновой-Иванова и имеют порядок 110, 126, 182, 506 и 990. [8]
Известны все кубические полусимметричные графы с числом вершин до 768. Согласно Кондеру , Малничу, Марушичу и Поточнику, 12-клетка Тутте является уникальным кубическим полусимметричным графом с числом вершин 126 и является пятым наименьшим возможным кубическим полусимметричным графом после графа Грея , графа Иофиновой–Иванова с числом вершин 110 , графа Любляны и графа с числом вершин 120 и обхватом 8. [9]
Характеристический полином 12-клетки Тутте равен
Это единственный граф с таким характеристическим многочленом; поэтому 12-клетка определяется его спектром .
Галерея
Ссылки
- ^ abc Джеффри Эксу и Роберт Джаджкей, Динамическое обследование клетки, Electr. J. Combin. 15 (2008).
- ^ Вайсштейн, Эрик В. «Все 12 клеток». Математический мир .
- ^ Бенсон, CT «Минимальные регулярные графы обхвата 8 и 12». Can. J. Math. 18, 1091–1094, 1966.
- ^ Эксо, Г. «Прямолинейные рисунки известных графиков».
- ^ Пегг, ET и Эксу, G. «Пересечение числовых графов». Mathematica J. 11, 2009.
- ^ Польстер, Б. Геометрическая иллюстрированная книга. Нью-Йорк: Springer, стр. 179, 1998.
- ^ Балабан, AT «Трёхвалентные графы обхвата девять и одиннадцать и отношения между клетками». Rev. Roumaine Math 18, 1033–1043, 1973.
- ^ Иофинова, М.Е. и Иванов, А.А. «Бипримативные кубические графы». В кн. Исследования по алгебраической теории комбинаторных объектов. С. 123–134, 2002. (Всесоюз. научно-исследовательский ин-т систем. исследований, Москва, с. 137–152, 1985.)
- ^ Кондер, Марстон ; Мальнич, Александр; Марушич, Драган ; Поточник, Примож (2006), «Перепись полусимметричных кубических графов с числом вершин до 768», Журнал алгебраической комбинаторики , 23 (3): 255–294, doi : 10.1007/s10801-006-7397-3.
