Key points are not available for this paper at this time.
Nous étudions la généralisation suivante du problème du cycle hamiltonien : Étant donné des entiers a, b et un graphe G, existe-t-il une marche fermée dans G qui visite chaque sommet au moins a fois et au plus b fois ? En d'autres termes, existe-t-il un facteur 2a, 2b de 2b G connecté avec tous les degrés pairs ? Ce problème est NP-difficile pour toute constante 1 ≤ a ≤ b. Cependant, les graphes produits par des réductions connues ont un degré maximum qui croît linéairement en b. Le cas a = b = 1 -- c'est-à-dire la Hamiltonicité -- reste NP-difficile même dans les graphes 3-réguliers ; une question naturelle est de savoir si cela est vrai pour d'autres a, b. Dans ce travail, nous étudions quels a, b permettent des algorithmes en temps polynomial et lesquels conduisent à la NP-difficulté dans des graphes avec des degrés contraints. Nous donnons des caractérisations serrées pour les graphes réguliers et les graphes de degré maximum borné, tant dirigés qu'non dirigés.
Liu et al. (Sat,) ont étudié cette question.