Loading AI tools
наименьший полу-транзитивный граф Из Википедии, свободной энциклопедии
Граф Холта или граф Дойла является наименьшим полутранзитивным графом, то есть наименьшим примером вершинно-транзитивного и рёберно-транзитивного графа, который не является симметричным[1][2]. Такие графы не часто встречаются[3]. Граф назван именами Питера Дж. Дойла и Дерека Ф. Холта, обнаружившими граф независимо в 1976[4] и 1981[5] соответственно.
Граф Холта | |
---|---|
| |
Назван в честь | Дерека Ф. Холта |
Вершин | 27 |
Рёбер | 54 |
Радиус | 3 |
Диаметр | 3 |
Обхват | 5 |
Автоморфизмы | 54 |
Хроматическое число | 3 |
Хроматический индекс | 5 |
Свойства |
вершинно-транзитивный рёберно-транзитивный полутранзитивный гамильтонов эйлеров граф Кэли |
Медиафайлы на Викискладе |
Граф Холта имеет диаметр 3, радиус 3 и обхват 5, хроматическое число 3, хроматический индекс 5. Граф является гамильтоновым с 98 472 различными гамильтоновыми циклами[6]. Граф является вершинно 4-связным и рёберно 4-связным графом. Он имеет книжное вложение 3 и число очередей 3.[7]
Граф имеет группу автоморфизмов порядка 54[6]. Это самая маленькая группа для симметричных графов с тем же числом вершин и рёбер. Рисунок графа справа подчёркивает отсутствие у графа зеркальной симметрии.
Характеристический многочлен графа равен
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.