Граф Кокстера - Coxeter graph
| Граф Кокстера | |
|---|---|
 Граф Кокстера | |
| Названный в честь | Х. С. М. Коксетер |
| Вершины | 28 |
| Края | 42 |
| Радиус | 4 |
| Диаметр | 4 |
| Обхват | 7 |
| Автоморфизмы | 336 (PGL2(7)) |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Толщина книги | 3 |
| Номер очереди | 2 |
| Характеристики | Симметричный Дистанционно-регулярный Дистанционно-транзитивный Кубический Гипогамильтониан |
| Таблица графиков и параметров | |
в математический поле теория графов, то Граф Кокстера это 3-регулярный граф с 28 вершинами и 42 ребрами.[1] Это один из 13 известных кубический дистанционно регулярные графы.[2] Он назван в честь Гарольд Скотт Макдональд Кокстер.
Характеристики
Граф Кокстера имеет хроматическое число 3, хроматический индекс 3, радиус 4, диаметр 4 и обхват 7. Это также 3-вершинно-связный граф и 3-реберный граф. Она имеет толщина книги 3 и номер очереди 2.[3]
Граф Кокстера гипогамильтониан: сам по себе не имеет гамильтонова цикла, но каждый граф, образованный удалением из него единственной вершины, является гамильтоновым. Она имеет номер прямолинейного перехода 11, и является наименьшим кубическим графом с этим числом пересечения[4] (последовательность A110507 в OEIS ).
Строительство
Простейшее построение графа Кокстера из Самолет Фано. Возьми 7C3 = 35 возможных 3-комбинаций по 7 предметам. Отбросьте 7 троек, которые соответствуют линиям плоскости Фано, оставив 28 троек. Свяжите две тройки, если они не пересекаются. Результатом является граф Кокстера. Эта конструкция показывает граф Кокстера как индуцированный подграф из Граф Кнезера КГ7,3.
Граф Кокстера также может быть построен из меньшего дистанционно регулярного График Хивуда путем построения вершины для каждого 6-цикла в графе Хивуда и ребра для каждой непересекающейся пары 6-циклов.[5]
Граф Кокстера может быть получен из Граф Хоффмана-Синглтона. Возьмите любую вершину v в графе Хоффмана-Синглтона. Существует независимый набор размера 15, который включает v. Удалите 7 соседей v, и весь независимый набор, включая v, оставив позади граф Кокстера.
Алгебраические свойства
Группа автоморфизмов графа Кокстера - это группа порядка 336.[6] Он действует транзитивно на вершинах, на ребрах и на дугах графа. Следовательно, граф Кокстера является симметричный граф. У него есть автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно Приемная перепись, граф Кокстера, обозначаемый как F28A, является единственным кубическим симметричным графом с 28 вершинами.[7]
Граф Кокстера также однозначно определяется своим спектр графика, множество собственных значений графа его матрица смежности.[8]
Как конечный связный вершинно-транзитивный граф, не содержащий Гамильтонов цикл, граф Кокстера является контрпримером к варианту Гипотеза Ловаса, но каноническая формулировка гипотезы требует наличия гамильтонова пути и проверяется графом Кокстера.
Известно всего пять примеров вершинно-транзитивного графа без гамильтоновых циклов: полный график K2, то Граф Петерсена, граф Кокстера и два графа, полученные из графов Петерсена и Кокстера путем замены каждой вершины треугольником.[9]
В характеристический многочлен графа Кокстера есть . Это единственный граф с таким характеристическим полиномом, что делает его графом, определяемым его спектром.
Галерея
Граф, полученный любым вырезанием ребер из Кокстера, является гамильтоновым.
В хроматическое число графа Кокстера равно 3.
В номер прямолинейного перехода графа Кокстера равно 11.
Рекомендации
- ^ Вайсштейн, Эрик В. «График Кокстера». MathWorld.
- ^ Brouwer, A.E .; Коэн, А. М .; и Ноймайер А. Дистанционно регулярные графы. Нью-Йорк: Springer-Verlag, 1989.
- ^ Вольц, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Хэйторп, Майкл; Ньюкомб, Алекс (2018), Кубических графов на 26 вершинах с пересечением 11 не существует, arXiv:1804.10336
- ^ Дейтер, Итало Дж. (2011), «От графа Кокстера к графу Клейна», Журнал теории графов, arXiv:1002.1960, Дои:10.1002 / jgt.20597.
- ^ Ройл, Г. Данные F028A[постоянная мертвая ссылка ]
- ^ Кондер, М. и Добчаньи П. «Трехвалентные симметричные графы до 768 вершин». J. Combin. Математика. Комбинировать. Comput. 40, 41-63, 2002.
- ^ Э. Р. ван Дам, В. Х. Хемерс, Спектральные характеристики некоторых дистанционно регулярных графов. J. Алгебраический комбинат. 15, страницы 189-202, 2003 г.
- ^ Ройл, Г. «Кубические симметричные графы (перепись Фостера)».
- Кокстер, Х. С. М. «Мой график». Proc. Лондонская математика. Soc. 46, 117-136, 1983.