WikiSort.ru - Не сортированное

Граф Холта
В графе Холта все вершины эквивалентны и все рёбра эквивалентны, но нет автоморфизма, переводящего ребро в себя с перестановкой вершин
Назван в честь	Дерека Ф. Холта
Вершин	27
Рёбер	54
Радиус	3
Диаметр	3
Обхват	5
Автоморфизмы	54
Хроматическое число	3
Хроматический индекс	5
Свойства	вершинно-транзитивный рёберно-транзитивный полутранзитивный гамильтонов эйлеров граф Кэли

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

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

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

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

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

Галерея

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

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.