Граф Коксетера

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

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

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

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

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

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

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

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

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