Гипотеза Ловаса о гамильтоновом цикле — классическая гипотеза в теории графов.

Сформулирована в четвёртом томе « Искусства программирования », но, скорее всего, была известна гораздо раньше.

Формулировка

Каждый конечный связный вершинно-транзитивный граф содержит гамильтонов путь .

Вариации и обобщения

• Любой конечный связный вершинно-транзитивный граф , кроме пяти исключений, содержит гамильтонов цикл ; исключения составляют:
  • Полный граф ${\displaystyle K_{2}}$ ,
  • Граф Петерсена и граф, полученный из него заменой каждой вершины на треугольник,
  • Граф Коксетера и граф, полученный из него заменой каждой вершины на треугольник.

• 
  Полный граф ${\displaystyle K_{2}}$ .
• 
  Граф Петерсена.
• 
  Граф Коксетера.

Ни одно из пяти исключений не является графом Кэли . Это наблюдение приводит к более слабой версии гипотезы

• Любой граф Кэли конечной группы содержит гамильтонов цикл .

Для ориентированных графов Кэли гипотеза не верна.

Частные случаи

• Известно, что ориентированный граф Кэли абелевой группы имеет гамильтонов путь.
  • С другой стороны, циклические группы, порядок которых не является степенью простого числа, допускают ориентированный граф Кэли без гамильтонова цикла.
• В 1986 году Д. Витте доказал, что гипотеза верна для графов Кэли p-групп .
• Вопрос остаётся открытым для диэдральных групп .

Известно, что для симметрической группы гипотеза верна для следующих наборов образующих:

• ${\displaystyle a=(1,2,\dots ,n),b=(1,2)}$ (длинный цикл и транспозиция ).
• ${\displaystyle s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)}$ ( образующие Кокстера ). В этом случае гамильтонов цикл строится .
• ${\displaystyle a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots }$ .

Ссылки