Граф Холта

Перейти к навигации Перейти к поиску

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

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

(x^{3}-6x+2)^{6}(x+2)^{4}(x-1)^{4}(x-4).\

Галерея

Хроматическое число графа Холта равно 3.
Хроматический индекс графа Холта равен 5.
Граф Холта является гамильтоновым.

Примечания

↑ Doyle, 1985.
↑ Alspach, Marušič, Nowitz, 1994, с. 391–402.
↑ Gross, Yellen, 2004, с. 491.
↑ Doyle, 1976.
↑ Holt, 1981, с. 201–204.
↑ ¹ ² 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).

Похожие исследовательские статьи

В теории графов вершинно-транзитивным графом называется граф G такой, что для любых двух вершин v₁ и v₂ графа G существует автоморфизм

\text{[math]}

Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u₁—v₁ и u₂—v₂ имеется автоморфизм:

f : V(G) → V(G)

Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.

Обобщённые графы Петерсена — семейство кубических графов, образованное соединением вершин правильного многоугольника с соответствующими вершинами звезды. В семейство входит граф Петерсена и обобщает один из путей построения графа Петерсена. Семейство обобщённых графов Петерсена ввёл в рассмотрение в 1950 году Коксетер и этим графам дал имя в 1969 году Марк Воткинс.

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

Алмаз — планарный неориентированный граф с 4 вершинами и 5 рёбрами. Граф представляет собой полный граф $\text{[math]}$ без одного ребра.

Граф Любляны — неориентированный двудольный граф с 112 вершинами и 168 рёбрами.

Полусимметричный граф — неориентированный рёберно-транзитивный регулярный граф, не являющийся вершинно-транзитивным. Другими словами, граф полусимметричен, если каждая вершина имеет одно и то же число инцидентных рёбер и для каждой пары рёбер существует симметрия, переводящая одно ребро в другое, однако есть некоторая пара вершин, для которой нет симметрии, переводящей одну вершину в другую.

110-вершинный граф Иванова — Иофиновой — полусимметричный кубический граф с 110 вершинами и 165 рёбрами.

Граф Фолкмана — это двудольный 4-регулярный граф с 20 вершинами и 40 рёбрами.

Граф Шрикханде — граф, найденный С. С. Шрикханде в 1959 году. Граф сильно регулярен, имеет 16 вершин и 48 рёбер и каждая вершина имеет степень 6. Каждая пара узлов имеет ровно два общих соседа, независимо от того, связана эта пара ребром или нет.

Граф Бринкмана — 4-регулярный граф с 21 вершинами и 42 рёбрами, обнаруженный Гуннаром Бринкманом в 1992 году. Опубликовали его Бринкман и Мерингер в 1997 году.

Граф Хоффмана является 4-регулярным графом с 16 вершинами и 32 рёбрами, который открыл Алан Хоффман и опубликовал в 1963. Граф коспектрален графу гиперкуба Q₄.

Граф Робертсона или (4,5)-клетка — это 4-регулярный неориентированный граф с 19 вершинами и 38 рёбрами, названный именем Нейла Робертсона.

Граф Уэлса — единственный дистанционно-регулярный граф с массивом пересечений $\text{[math]}$ .

Граф Мередита — 4-регулярный неориентированный граф с 70 вершинами и 140 рёбрами, обнаруженный Гаем Мередитом в 1973 году.

Снарк «двойная звезда» — снарк с 30 вершинами и 45 рёбрами.

Полутранзитивный граф — это граф, который и вершинно-транзитивен, и рёберно-транзитивен, но не симметричен. Другими словами, граф полутранзитивен, если его группа автоморфизмов действует транзитивно как на вершины, так и на рёбра, но не на упорядоченные пары связанных вершин.

3-регулярный граф Клейна — кубический граф с 56 вершинами и 84 рёбрами; назван по имени Феликса Клейна с двойственным ему 7-регулярным графом.

7-регулярный граф Клейна — регулярный граф степени 7 с 24 вершинами и 84 рёбрами; назван, наряду с двойственным ему 3-регулярным графом, по имени Феликса Клейна.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.