Граф Холта
| Граф Холта | |
|---|---|
 В графе Холта все вершины эквивалентны и все рёбра эквивалентны, но нет автоморфизма, переводящего ребро в себя с перестановкой вершин | |
| Назван в честь | Дерека Ф. Холта |
| Вершин | 27 |
| Рёбер | 54 |
| Радиус | 3 |
| Диаметр | 3 |
| Обхват | 5 |
| Автоморфизмы | 54 |
| Хроматическое число | 3 |
| Хроматический индекс | 5 |
| Свойства |
вершинно-транзитивный рёберно-транзитивный полутранзитивный гамильтонов эйлеров граф Кэли |
 Медиафайлы на Викискладе | |
Граф Холта или граф Дойла является наименьшим полутранзитивным графом, то есть наименьшим примером вершинно-транзитивного и рёберно-транзитивного графа, который не является симметричным[1][2]. Такие графы не часто встречаются[3]. Граф назван именами Питера Дж. Дойла и Дерека Ф. Холта, обнаружившими граф независимо в 1976[4] и 1981[5] соответственно.
Граф Холта имеет диаметр 3, радиус 3 и обхват 5, хроматическое число 3, хроматический индекс 5. Граф является гамильтоновым с 98 472 различными гамильтоновыми циклами[6]. Граф является вершинно 4-связным и рёберно 4-связным графом. Он имеет книжное вложение 3 и число очередей 3.[7]
Граф имеет группу автоморфизмов порядка 54[6]. Это самая маленькая группа для симметричных графов с тем же числом вершин и рёбер. Рисунок графа справа подчёркивает отсутствие у графа зеркальной симметрии.
Характеристический многочлен графа равен
Галерея[править | править код]
-
Хроматическое число графа Холта равно 3. -
Хроматический индекс графа Холта равен 5. -
Граф Холта является гамильтоновым.
Примечания[править | править код]
- ↑ Doyle, 1985.
- ↑ Alspach, Marušič, Nowitz, 1994, с. 391–402.
- ↑ Gross, Yellen, 2004, с. 491.
- ↑ Doyle, 1976.
- ↑ Holt, 1981, с. 201–204.
- ↑ 1 2 Weisstein, Eric W. Doyle Graph (англ.) на сайте Wolfram MathWorld.
- ↑ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
Литература[править | править код]
- Peter G. Doyle. A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive. — 1985. — Октябрь. — arXiv:math/0703861.
- Brian Alspach, Dragan Marušič, Lewis Nowitz. Constructing Graphs which are ½-Transitive // Journal of the Australian Mathematical Society (Series A). — 1994. — Т. 56, вып. 3. — doi:10.1017/S1446788700035564. Архивировано 27 ноября 2003 года.
- Jonathan L. Gross, Jay Yellen. Handbook of Graph Theory. — CRC Press, 2004. — ISBN 1-58488-090-2.
- Doyle P. G. On Transitive Graphs. — Harvard College, 1976. — (Senior Thesis).
- Derek F. Holt. A graph which is edge transitive but not arc transitive // Journal of Graph Theory. — 1981. — Т. 5, вып. 2. — doi:10.1002/jgt.3190050210.
- Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis).
 | Для улучшения этой статьи желательно:
|