Гамильтонова проблема решения разложения

10

Пусть - неориентированный граф. Разложение V на непересекающиеся подмножества V я называюсь разложением Гамильтон из G , если подграф , индуцированный каждое множество V я либо граф Гамильтон , либо состоит из одного ребра с | V я | = 2 .G=(V,E)VViGVi|Vi|=2

Пример : полный двудольный граф обладает гамильтоновым разложением тогда и только тогда, когда m = n .Km,nm=n

Я ищу алгоритм, который решает, обладает ли данный граф разложением Гамильтона. Является ли это решение проблемы NP-завершенным? Если нет, как мы можем найти такое разложение?

Примечание : В литературе разложение Гамильтон часто означает разложение ребер из G такого , что индуцированные подграфы Гамильтон. В отличие от меня интересует разложение вершин.EG

Фолькер Турау
источник

Ответы:

17

|Vi|3|Vi|=2

Маркус Блезер
источник