Interested Article - Гипотеза Ловаса о гамильтоновом цикле

Гамильтонов путь в графе Кэли симметрической группы.

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

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

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

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

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

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

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

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

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

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

  • (длинный цикл и транспозиция ).
  • ( образующие Кокстера ). В этом случае гамильтонов цикл строится .
  • .

Ссылки

  1. Holsztyński, W.; Strube, R. F. E. (1978), "Paths and circuits in finite groups", Discrete Mathematics , 22 (3): 263—272, doi : , MR .
Источник —

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