Граф Холта
| Граф Холта | |
|---|---|
 В графе Холта все вершины эквивалентны и все ребра эквивалентны, но ребра не эквивалентны своим обратным. | |
| Назван в честь | Дерек Ф. Холт |
| Вершины | 27 |
| Края | 54 |
| Радиус | 3 |
| Диаметр | 3 |
| Обхват | 5 |
| Автоморфизмы | 54 |
| Хроматическое число | 3 |
| Хроматический индекс | 5 |
| Толщина книги | 3 |
| Номер очереди | 3 |
| Характеристики | Вершинно-транзитивный Край-транзитивный полупереходный гамильтониан Эйлеров Граф Кэли |
| Таблица графиков и параметров | |
В теории графов граф Холта или граф Дойла — это наименьший полутранзитивный граф , то есть наименьший пример вершинно -транзитивного и реберно-транзитивного графа, который также не является симметричным . [1] [2] Такие графики встречаются нечасто. [3] Он назван в честь Питера Дж. Дойла и Дерека Ф. Холта, которые независимо открыли тот же график в 1976 году. [4] и 1981 год [5] соответственно.
Граф Холта имеет диаметр 3, радиус 3 и обхват 5, хроматическое число 3, хроматический индекс 5 и является гамильтоновым с 98 472 различными гамильтоновыми циклами. [6] Это также 4- вершинно-связный и 4- реберно-связный граф. Имеет толщину книги 3 и номер очереди 3. [7]
Имеет группу автоморфизмов порядка 54. [6] Это меньшая группа, чем могла бы иметь симметричный граф с таким же количеством вершин и ребер. График справа подчеркивает это, поскольку ему не хватает отражательной симметрии.
Характеристический полином графа Холта равен
Галерея
[ редактировать ]
Хроматическое число графа Холта равно 3.
Хроматический индекс графа Холта равен 5.
Граф Холта является гамильтоновым .
Граф Холта представляет собой граф единичных расстояний .
Ссылки
[ редактировать ]- ^ Дойл, П. «Граф с 27 вершинами, который является вершинно-транзитивным и реберно-транзитивным, но не L-транзитивным». Октябрь 1998 г. [1]
- ^ Олспах, Брайан ; Марушич, Драган ; Новиц, Льюис (1994), «Построение ½-транзитивных графов», Журнал Австралийского математического общества, серия A , 56 (3): 391–402, doi : 10.1017/S1446788700035564 .
- ^ Джонатан Л. Гросс, Джей Йеллен, Справочник по теории графов , CRC Press, 2004, ISBN 1-58488-090-2 , с. 491.
- ^ Дойл, П.Г. (1976), О транзитивных графах , Старшая диссертация, Гарвардский колледж . По данным MathWorld.
- ^ Холт, Дерек Ф. (1981), «Граф, транзитивный по ребрам, но не транзитивный по дугам», Journal of Graph Theory , 5 (2): 201–204, doi : 10.1002/jgt.3190050210 .
- ^ Jump up to: а б Вайсштейн, Эрик В. «График Дойла» . Математический мир .
- ^ Джессика Вольц, Разработка линейных макетов с помощью SAT . Магистерская диссертация, Тюбингенский университет, 2018 г.