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