Граф Холта или граф Дойла является наименьшим полутранзитивным графом, то есть наименьшим примером вершинно-транзитивного и рёберно-транзитивного графа, который не является симметричным[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]. Это самая маленькая группа для симметричных графов с тем же числом вершин и рёбер. Рисунок графа справа подчёркивает отсутствие у графа зеркальной симметрии.

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

Галерея

править

Примечания

править
  1. Doyle, 1985.
  2. Alspach, Marušič, Nowitz, 1994, с. 391–402.
  3. Gross, Yellen, 2004, с. 491.
  4. Doyle, 1976.
  5. Holt, 1981, с. 201–204.
  6. 1 2 Weisstein, Eric W. Doyle Graph (англ.) на сайте Wolfram MathWorld.
  7. 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).