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