Граф Коксетера — 3- регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны , граф Коксетера — один из 13-ти таких графов.

Свойства

Хроматическое число графа равно 3, хроматический индекс равен 3, радиус равен 4, диаметр — 4, а обхват — 7. Граф является также вершинно 3-связным и рёберно 3-связным .

Граф Коксетера является гипогамильтоновым — сам по себе он не содержит гамильтоновых циклов, но удаление любой вершины делает его гамильтоновым . Число прямолинейных скрещиваний графа Коксетера равно 11 и это минимальный известный кубический граф с таким числом скрещиваний, хотя графы с 26 вершинами и числом скрещиваний 11 существовать могут .

Граф Коксетера можно построить из несколько меньшего дистанционно-регулярного графа Хивуда путём создания вершины для каждого 6-цикла в графе Хивуда и ребра для каждой несвязной пары 6-циклов .

Алгебраические свойства

Группа автоморфизмов графа Коксетера — это группа порядка 336 . Она действует транзитивно на вершины и рёбра графа, поэтому граф Фостера является симметричным . Граф имеет автоморфизмы, которые переводят любую вершину в любую другую и любое ребро в любое другое ребро. В списке Фостера граф Коксетера, указанный как F28A, является единственным кубическим симметричным графом с 28 вершинами .

Граф Коксетера однозначно определяется по его спектру , множеству собственных значений матрицы смежности графа .

Как конечный связный вершинно-транзитивный граф, не содержащий гамильтонов цикл , граф Коксетера является контпримером варианта , но каноническая формулировка гипотезы требует наличия гамильтонова цикла.

Известно только пять вершинно-транзитивных графов без гамильтоновых циклов — полный граф K ₂ , граф Петерсена , граф Коксетера и два графа, полученные из графов Петерсена и Коксетера путём замены каждой вершины треугольником .

Характеристический многочлен графа Коксетера равен ${\displaystyle (x-3)(x-2)^{8}(x+1)^{7}(x^{2}+2x-1)^{6}}$ . Граф является единственным графом с таким полиномом, что делает граф однозначно определяемым по его спектру.

Галерея

• 
  Граф, полученный удалением любого ребра из графа Коксетера является .
• 
  Хроматическое число графа Коксетера равно 3.
• 
  Число прямолинейных скрещиваний графа Коксетера равно  11.

Примечания