Jump to content

Все 12 клеток

Все 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-клетка определяется ее спектром .

  1. ^ Перейти обратно: а б с Джеффри Эксу и Роберт Джейкей, Динамическое обследование клеток, Electr. Дж. Комбин. 15 (2008).
  2. ^ Вайсштейн, Эрик В. «Все 12 клеток» . Математический мир .
  3. ^ Бенсон, Коннектикут «Минимальные регулярные графики обхвата 8 и 12». Может. Дж. Математика. 18, 1091–1094, 1966.
  4. ^ Эксу, Г. «Прямолинейные рисунки известных графов» .
  5. ^ Пегг, И.Т. и Эксу, Г. «Графы пересечений чисел». Математика Дж. 11, 2009.
  6. ^ Польстер, Б. Геометрическая книжка с картинками. Нью-Йорк: Спрингер, с. 179, 1998.
  7. ^ Балабан, А. Т. «Трехвалентные графики обхвата девять и одиннадцать и отношения между клетками». Преподобный Румен Математик, 18, 1033–1043, 1973.
  8. ^ Иофинова М.Е., Иванов А.А. «Би-примитивные кубические графы». В исследованиях по алгебраической теории комбинаторных объектов. С. 123–134, 2002. (Всесоюз. Научно-Исслед. Инт. Систем. Исслед., Москва, С. 137–152, 1985.)
  9. ^ Кондер, Марстон ; Мальнич, Александр; Марушич, Драган ; Поточник, Примож (2006), «Перепись полусимметричных кубических графов с числом вершин до 768», Журнал алгебраической комбинаторики , 23 (3): 255–294, doi : 10.1007/s10801-006-7397-3 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 3119d56ff61d4a17bcfcadc1aaece910__1721753340
URL1:https://arc.ask3.ru/arc/aa/31/10/3119d56ff61d4a17bcfcadc1aaece910.html
Заголовок, (Title) документа по адресу, URL1:
Tutte 12-cage - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)