Обобщение понятия гамильтонова графа

[fractalon]

Мне тут на досуге подумалось: а что если обобщить понятие гамильтонова пути и, соответственно, гамильтонова графа следующим образом: называть $k$-гамильтоновым граф в котором существует путь, позволяющий обойти все вершины графа, посетив каждую не более $k$ раз.
Если ввести такое понятие, то, может быть, возможно научится каким-то образом вычислять верхнюю оценку степени гамильтоновости графа, если известна такая оценка для отдельных его частей, можно как-то связывать $k$-гамильтоновость с приведением к графу с меньшей степенью гамильтоновости с помощью стягивания вершин или удаления рёбер...
Возможно, для достаточно больших, $k$ (например для $k=O(\log{n})$ или $k=O(\sqrt{n})$) возможен полиномиальный алгоритм проверки на k-гамильтоновость?
Кто что думает по этому поводу? Может быть, кто-то знает книги, в которых уже описаны рассуждения в этом русле, и я просто изобретаю велосипед?

[veg_nw]

У меня такой вопрос. Если граф 1-гамильтонов как вы определили. То он в то же время и 2-гамильтонов, 3-гамильтонов итд. Я правильно трактую вашу идею?

[fractalon]

Ну, это уже издержки формализации (хотя штука, конечно, важная). Да, я сформулировал именно так.

[hurtsy]

fractalon в сообщении #891970 писал(а):

Ну, это уже издержки формализации (хотя штука, конечно, важная).

Разумеется, формализация штука плодотворная. А что вам мешает наложить оганичение на кратность посещения вершин, как то связав ограничение с $k$. С уважением,

[fractalon]

Кратность - то есть каждая вершина должна быть посещена $nk$ раз, где $n>1$ - целое? Интересно, надо подумать...
Формулировку конечно можно изменить, сказав, что не существует пути, обходящего все вершины и посещающего каждую не более $k-1$ раз.