Гипотеза Ловаса о гамильтоновом цикле — классическая гипотеза в теории графов.
Сформулирована в четвёртом томе «Искусства программирования», но, скорее всего, была известна гораздо раньше.
Формулировка Каждый конечный связный вершинно-транзитивный граф содержит гамильтонов путь.
Вариации и обобщения
Любой конечный связный вершинно-транзитивный граф, кроме пяти исключений, содержит гамильтонов цикл; исключения составляют: Полный граф , Граф Петерсена и граф, полученный из него заменой каждой вершины на треугольник, Граф Коксетера и граф, полученный из него заменой каждой вершины на треугольник.
Ни одно из пяти исключений не является графом Кэли. Это наблюдение приводит к более слабой версии гипотезы Любой граф Кэли конечной группы содержит гамильтонов цикл.
Для ориентированных графов Кэли гипотеза не верна.
Частные случаи Известно, что ориентированный граф Кэли абелевой группы имеет гамильтонов путь. С другой стороны, циклические группы, порядок которых не является степенью простого числа, допускают ориентированный граф Кэли без гамильтонова цикла.. В 1986 году Д. Витте доказал, что гипотеза верна для графов Кэли p-групп. Вопрос остаётся открытым для диэдральных групп.
Известно, что для симметрической группы гипотеза верна для следующих наборов образующих: (длинный цикл и транспозиция). (образующие Кокстера). В этом случае гамильтонов цикл строится алгоритмом Штайнхаусa — Джонсона — Троттера. .
Ссылки
Категория:Алгебраическая теория графов Категория:Математические гипотезы Категория:Конечные группы Категория:Теория графов Категория:Теория групп Категория:Гамильтоновы пути и циклы