| Граф Холта | |
|---|---|
 В графе Холта все вершины эквивалентны, и все ребра эквивалентны, но ребра не эквивалентны своим обратным. | |
| Названный в честь | Дерек Ф. Холт |
| Вершины | 27 |
| Края | 54 |
| Радиус | 3 |
| Диаметр | 3 |
| Обхват | 5 |
| Автоморфизмы | 54 |
| Хроматическое число | 3 |
| Хроматический индекс | 5 |
| Толщина книги | 3 |
| Номер очереди | 3 |
| Характеристики | Вершинно-транзитивный Edge-транзитивный Полутранзитивный гамильтонов эйлеров граф Кэли |
| Таблица графиков и параметров | |
В математической области теории графов , то граф Холт или Дойла граф является наименьшим наполовину симметрический граф , то есть, самый маленький пример вершины-переходных и ребра-транзитивным графом , который не является также симметричной . [1] [2] Такие графы встречаются нечасто. [3] Он назван в честь Питера Г. Дойла и Дерека Ф. Холта, которые независимо друг от друга открыли тот же граф в 1976 [4] и 1981 [5] соответственно.
Граф Холта имеет диаметр 3, радиус 3 и обхват 5, хроматическое число 3, хроматический индекс 5 и является гамильтоновым с 98 472 различными гамильтоновыми циклами. [6] Это также 4- вершинно-связный и 4 -реберный граф. Он имеет книжную толщину 3 и номер очереди 3. [7]
Он имеет группу автоморфизмов порядка 54 автоморфизмов. [6] Это меньшая группа, чем симметричный граф с таким же количеством вершин и ребер. График справа подчеркивает это тем, что ему не хватает отражательной симметрии.
Характеристический многочлен графа Холта равен
Галерея [ править ]
Хроматическое число от Holt графа 3.
Хроматической индекс в Holt графа 5.
Граф Холта гамильтонов .
Ссылки [ править ]
- ^ Дойл, П. "График с 27 вершинами, который является вершинно-транзитивным и реберно-транзитивным, но не L-транзитивным". Октябрь 1998 г. [1]
- ^ Альспах, Брайан ; Марушич, Драган ; Nowitz, Льюис (1994), "Построение графиков , которые являются ½-Переходный" , журнал Австралийского математического общества Серии А , 56 (3): 391-402, DOI : 10,1017 / S1446788700035564 , архивируется с оригинала на 2003-11- 27.
- ^ Джонатан Л. Гросс, Джей Йеллен, Справочник по теории графов , CRC Press, 2004, ISBN 1-58488-090-2 , стр. 491.
- Перейти ↑ Doyle, PG (1976), On Transitive Graphs , Senior Thesis, Harvard College. Цитируется MathWorld.
- ^ Холт, Дерек Ф. (1981), "Граф , который является краем транзитивно , но не транзитивно дуги", журнал теории графов , 5 (2): 201-204, DOI : 10.1002 / jgt.3190050210.
- ^ a b Вайсштейн, Эрик В. "Дойл Граф" . MathWorld .
- ^ Джессика Wolz, Инженерная Линейные Макеты с SAT . Магистерская работа, Тюбингенский университет, 2018 г.