Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.
Свойства Хроматическое число графа равно 3, хроматический индекс равен 3, радиус равен 4, диаметр — 4, а обхват — 7. Граф является также вершинно 3-связным и рёберно 3-связным.
Граф Коксетера является гипогамильтоновым — сам по себе он не содержит гамильтоновых циклов, но удаление любой вершины делает его гамильтоновым. Число прямолинейных скрещиваний графа Коксетера равно 11 и это минимальный известный кубический граф с таким числом скрещиваний, хотя графы с 26 вершинами и числом скрещиваний 11 существовать могут.
Граф Коксетера можно построить из несколько меньшего дистанционно-регулярного графа Хивуда путём создания вершины для каждого 6-цикла в графе Хивуда и ребра для каждой несвязной пары 6-циклов..
Алгебраические свойства Группа автоморфизмов графа Коксетера — это группа порядка 336Royle, G. F028A data. Она действует транзитивно на вершины и рёбра графа, поэтому граф Фостера является симметричным. Граф имеет автоморфизмы, которые переводят любую вершину в любую другую и любое ребро в любое другое ребро. В списке Фостера граф Коксетера, указанный как F28A, является единственным кубическим симметричным графом с 28 вершинамиM. Conder, P. Dobcsányi, «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002..
Граф Коксетера однозначно определяется по его спектру, множеству собственных значений матрицы смежности графаE. R. van Dam and W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraic Combin. 15, pages 189—202, 2003.
Как конечный связный вершинно-транзитивный граф, не содержащий гамильтонов цикл, граф Коксетера является контрпримером варианта , но каноническая формулировка гипотезы требует наличия гамильтонова цикла.
Известно только пять вершинно-транзитивных графов без гамильтоновых циклов — полный граф K2, граф Петерсена, граф Коксетера и два графа, полученные из графов Петерсена и Коксетера путём замены каждой вершины треугольникомRoyle, G. «Cubic Symmetric Graphs (The Foster Census).» .
Характеристический многочлен графа Коксетера равен . Граф является единственным графом с таким полиномом, что делает граф однозначно определяемым по его спектру.
Галерея
Примечания
Категория:Регулярные графы Категория:Графы, имеющие собственные названия