Граф Холта

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

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

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

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