Граф Холта


Граф Холта или граф Дойла является наименьшим полутранзитивным графом, то есть наименьшим примером вершинно-транзитивного и рёберно-транзитивного графа, который не является симметричным. Такие графы не часто встречаются. Граф назван именами Питера Дж. Дойла и Дерека Ф. Холта, обнаружившими граф независимо в 1976 и 1981 соответственно.

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

Граф имеет группу автоморфизмов порядка 54. Это самая маленькая группа для симметричных графов с тем же числом вершин и рёбер. Рисунок графа справа подчёркивает отсутствие у графа зеркальной симметрии.

Характеристический многочлен графа равен

( x 3 − 6 x + 2 ) 6 ( x + 2 ) 4 ( x − 1 ) 4 ( x − 4 ) .   {displaystyle (x^{3}-6x+2)^{6}(x+2)^{4}(x-1)^{4}(x-4). }

Галерея

  • Хроматическое число графа Холта равно 3.

  • Хроматический индекс графа Холта равен 5.

  • Граф Холта является гамильтоновым.


  • Вальтеоф, граф Данбар
  • Граф Дюрера
  • Граф Леви
  • Гипотеза Шейнермана
  • Циркулянтный граф

  •  

    • Яндекс.Метрика
    • Индекс цитирования