Все 12 клеток
Все 12 клеток | |
---|---|
Назван в честь | WT Тутте |
Вершины | 126 |
Края | 189 |
Радиус | 6 |
Диаметр | 6 |
Обхват | 12 |
Автоморфизмы | 12096 |
Хроматическое число | 2 |
Хроматический индекс | 3 |
Род | 17 |
Характеристики | Кубический Клетка гамильтониан Полусимметричный двусторонний |
Таблица графиков и параметров |
В математической области теории графов граф Тутта с 12 клетками или граф Бенсона. [1] представляет собой 3- регулярный граф со 126 вершинами и 189 ребрами. Он назван в честь WT Tutte . [2]
12-клетка Tutte – это уникальная клетка (3-12) (последовательность A052453 в OEIS ). Он был открыт К. Т. Бенсоном в 1966 году. [3] Он имеет хроматическое число 2 ( двудольный ), хроматический индекс 3, обхват 12 (как клетка из 12) и диаметр 6. Известно, что его число пересечений меньше 165, см. Wolfram MathWorld. [4] [5]
Строительство
[ редактировать ]12-клетка Тутте представляет собой кубический гамильтонов граф и может быть определена с помощью обозначений 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-клетка определяется ее спектром .
Галерея
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Джеффри Эксу и Роберт Джейкей, Динамическое обследование клеток, Electr. Дж. Комбин. 15 (2008).
- ^ Вайсштейн, Эрик В. «Все 12 клеток» . Математический мир .
- ^ Бенсон, Коннектикут «Минимальные регулярные графики обхвата 8 и 12». Может. Дж. Математика. 18, 1091–1094, 1966.
- ^ Эксу, Г. «Прямолинейные рисунки известных графов» .
- ^ Пегг, И.Т. и Эксу, Г. «Графы пересечений чисел». Математика Дж. 11, 2009.
- ^ Польстер, Б. Геометрическая книжка с картинками. Нью-Йорк: Спрингер, с. 179, 1998.
- ^ Балабан, А. Т. «Трехвалентные графики обхвата девять и одиннадцать и отношения между клетками». Преподобный Румен Математик, 18, 1033–1043, 1973.
- ^ Иофинова М.Е., Иванов А.А. «Би-примитивные кубические графы». В исследованиях по алгебраической теории комбинаторных объектов. С. 123–134, 2002. (Всесоюз. Научно-Исслед. Инт. Систем. Исслед., Москва, С. 137–152, 1985.)
- ^ Кондер, Марстон ; Мальнич, Александр; Марушич, Драган ; Поточник, Примож (2006), «Перепись полусимметричных кубических графов с числом вершин до 768», Журнал алгебраической комбинаторики , 23 (3): 255–294, doi : 10.1007/s10801-006-7397-3 .