Оглавление
График Кокстера
-
Определение и свойства графа Кокстера
- Граф Кокстера – 3-правильный граф с 28 вершинами и 42 ребрами, один из 13 кубических дистанционно-регулярных графов.
- Имеет хроматический номер 3, хроматический индекс 3, радиус 4, диаметр 4, обхват 7.
- Связан с 3 вершинами и 3 ребрами, имеет толщину книги 3 и номер очереди 2.
- Гипогамильтонов, имеет прямолинейное пересечение 11 и является наименьшим кубическим графом с таким числом пересечения.
-
Построение графа Кокстера
- Простое построение на плоскости Фано, где из 7C3 комбинаций отбрасываются 7 триплетов, соответствующих линиям плоскости, оставляя 28 триплетов.
- Граф Кокстера может быть представлен как индуцированный подграф нечетного графа O4 или графа Хивуда.
-
Алгебраические свойства
- Группа автоморфизмов порядка 336, действует транзитивно на вершины, ребра и дуги, делая граф симметричным.
- Единственный кубический симметричный граф с 28 вершинами, определяется спектром графа.
- Граф Кокстера является контрпримером к гипотезе Ловаша, но не удовлетворяет канонической формулировке гипотезы из-за отсутствия гамильтонова пути.
-
Характеристический многочлен
- Характеристический многочлен (x-3)(x-2)^8(x+1)^7(x^2+2x-1)^6, уникальный для графа Кокстера.
-
Галерея
- Представлены различные макеты графа Кокстера с использованием одних и тех же меток вершин.
-
Рекомендации
- Статья Кокстера, Х. С. М. “Мой график” в Proc. London Math. Soc. 46, 117-136, 1983.