График Тутте – Кокстера

График Тутте – Кокстера

Названный в честь	WT Tutte H. SM Coxeter
Вершины	30
Края	45
Радиус	4
Диаметр	4
Обхват	8
Автоморфизмы	1440 (Aut (S ₆ ))
Хроматическое число	2
Хроматический индекс	3
Толщина книги	3
Номер очереди	2
Характеристики	Кубический граф Кейджа Мура Симметричный дистанционно-регулярный дистанционно-транзитивный Двудольный
Таблица графиков и параметров

В математической области теории графов , то граф Tutte-Косетер или Tutte восемь-клетка или Кремона-Ричмонд график представляет собой 3 - регулярный граф с 30 вершинами и 45 ребрами. В качестве уникального маленького кубического графа из обхвата 8 это клетка и граф Мура . Это двудольное , и может быть построено как граф Леви из обобщенного четырехугольника W ₂ (известный как конфигурация Кремоны-Richmond ). Граф назван в честь Уильяма Томаса Тутте иHSM Coxeter ; он был открыт Тутте (1947), но его связь с геометрическими конфигурациями была исследована обоими авторами в паре совместно опубликованных статей (Tutte 1958; Coxeter 1958a).

Все кубические дистанционно регулярные графы известны. ^[1] Тутт – Кокстер - один из 13 таких графиков.

Он имеет перекресток номер 13, ^[2]^[3] книжную толщину 3 и очередь номер 2. ^[4]

Конструкции и автоморфизмы

Особенно простая комбинаторная конструкция графа Тутта – Кокстера принадлежит Кокстеру (1958b) на основе работы Сильвестра (1844). В современной терминологии возьмем полный граф на 6 вершинах K ₆ . У него 15 граней, а также 15 идеальных сочетаний . Каждая вершина графа Тутта – Кокстера соответствует ребру или идеальному совпадению K ₆ , а каждое ребро графа Тутта-Кокстера соединяет идеальное совпадение K ₆ с каждым из трех составляющих его ребер. В силу симметрии каждое ребро K ₆принадлежит трем идеальным совпадениям. Между прочим, это разбиение вершин на ребра-вершины и совпадающие вершины показывает, что граф Тутта-Кокстера двудольный.

Основываясь на этой конструкции, Кокстер показал, что граф Тутте – Кокстера является симметричным графом ; у него есть группа из 1440 автоморфизмов , которые можно отождествить с автоморфизмами группы перестановок шести элементов (Coxeter 1958b). На внутренних автоморфизмах этой группы , соответствует перестановке шесть вершин К ₆ графу; эти перестановки действуют на граф Тутта – Кокстера, переставляя вершины на каждой стороне его двудольного деления, сохраняя при этом каждую из двух сторон фиксированной как набор. Кроме того, внешние автоморфизмыгруппы перестановок меняют одну сторону двудольного разделения на другую. Как показал Кокстер, любой путь, содержащий до пяти ребер в графе Тутта – Кокстера, эквивалентен любому другому такому пути с помощью одного такого автоморфизма.

Граф Тутте – Кокстера как здание

Этот граф является сферическим зданием, ассоциированным с симплектической группой (между этой группой и симметрической группой существует исключительный изоморфизм ). В частности, это график инцидентности обобщенного четырехугольника . ${\ Displaystyle Sp_ {4} (\ mathbb {F} _ {2})}$ ${\ displaystyle S_ {6}}$

Конкретно, граф Тутта-Кокстера может быть определен из 4-мерного симплектического векторного пространства над следующим образом: $V$ $\mathbb {F} _{2}$

вершины являются либо ненулевыми векторами, либо изотропными двумерными подпространствами,
существует грань между ненулевым вектором v и изотропным двумерным подпространством тогда и только тогда, когда . $W\subset V$ $v\in W$

Галерея

Хроматическое число графа Тутты-Кокстер 2.
Хроматической индекс графа Тутты-Кокстер равно 3.

использованная литература

^ Брауэр, AE; Коэн, AM; и Ноймайер А. Дистанционно регулярные графы. Нью-Йорк: Springer-Verlag, 1989.
^ Пегг, ET ; Эксу, Г. (2009). «Графики пересекающихся чисел». Mathematica Journal . 11 (2). DOI : 10.3888 / tmj.11.2-2 .
^ Exoo, G. "Прямолинейные рисунки известных графов" .
^ Wolz, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.

Кокстер, HSM (1958a). «Хорды неразрушенной квадрики в PG (3,3)». Жестяная банка. J. Math . 10 : 484–488. DOI : 10,4153 / CJM-1958-047-0 .

Кокстер , HSM (1958b). «Двенадцать баллов в PG (5,3) с 95040 самотрансформациями». Труды Королевского общества А . 247 (1250): 279–293. DOI : 10.1098 / rspa.1958.0184 . JSTOR 100667 . S2CID 121676627 .

Сильвестр, Дж. Дж. (1844 г.). «Элементарные исследования в анализе комбинаторной агрегации» . Фил. Mag . Серия 3. 24 : 285–295. DOI : 10.1080 / 14786444408644856 .

Тутте, WT (1947). «Семейство кубических графов». Proc. Cambridge Philos. Soc . 43 (4): 459–474. DOI : 10.1017 / S0305004100023720 .

Тутте, WT (1958). «Хорды неразрушенной квадрики в PG (3,3)». Жестяная банка. J. Math . 10 : 481–483. DOI : 10,4153 / CJM-1958-046-3 .

внешние ссылки

Франсуа Лабель. "3D модель восьмерки клетки Тутте" .
Вайсштейн, Эрик В. «Граф Леви» . MathWorld .
Эксу, Дж. «Прямолинейные рисунки известных графов». [1]

[1] Брауэр, AE; Коэн, AM; и Ноймайер А. Дистанционно регулярные графы. Нью-Йорк: Springer-Verlag, 1989.

[2] Пегг, ET ; Эксу, Г. (2009). «Графики пересекающихся чисел». Mathematica Journal . 11 (2). DOI : 10.3888 / tmj.11.2-2 .

[3] Exoo, G. "Прямолинейные рисунки известных графов" .

[4] Wolz, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.

[1]