Гіпотеза Ловаса про гамільтонів цикл

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

Гамільтонів шлях у графі Келі симетричної групи.

Сформульована в четвертому томі «Мистецтва програмування», але, найпевніше, була відома значно раніше.

Формулювання

Кожен скінченний зв'язний вершинно-транзитивний граф містить гамільтонів шлях.

Варіації та узагальнення

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

• 

  Повний граф $K_{2}$.

• 

  Граф Петерсена.

• 

  Граф Коксетера.

Жоден із п'яти винятків не є графом Келі. Це спостереження приводить до слабшої версії гіпотези:

• Будь-який граф Келі скінченної групи містить гамільтонів цикл.

Для орієнтованих графів Келі гіпотеза хибна.

Окремі випадки

• Відомо, що орієнтований граф Келі абелевої групи має гамільтонів шлях.
  • З іншого боку, циклічні групи, порядок яких не є степенем простого числа, допускають орієнтований граф Келі без гамільтонового циклу.
• 1986 року Д. Вітте довів, що гіпотеза істинна для графів Келі p-груп.
• Питання залишається відкритим для діедральних груп.

Відомо, що для симетричної групи гіпотеза істинна для таких наборів твірних:

• $a=(1,2,\dots ,n),b=(1,2)$ (довгий цикл і транспозиція).
• $s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)$ (твірні Коксетера). У цьому випадку гамільтонів цикл будується алгоритмом Штайнгауза — Джонсона — Троттера.
• $a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots$.