Un code de Gray cyclique est une séquence ordonnée qui contient toutes les chaînes binaires d'une longueur donnée dans laquelle chaque chaîne consécutive diffère de la précédente en exactement une coordonnée. Une telle séquence représente directement un cycle Hamiltonien et un chemin dans l'hypercube. Ruskey et Savage ont demandé si chaque appariement dans l'hypercube s'étend à un cycle Hamiltonien, et Fink a prouvé que chaque appariement parfait dans la formule : voir le texte s'étend à un cycle Hamiltonien. Dans cette étude, nous abordons un problème lié aux chemins Hamiltoniens. Nous prouvons que chaque appariement à au plus cinq directions où chaque formule : voir le texte-cycle contient au moins un sommet non saturé, peut être étendu à un chemin Hamiltonien joignant deux sommets dans des ensembles partitis distincts de la formule : voir le texte, pour la formule : voir le texte. Les seules configurations interdites sont les soi-disant demi-couches, qui forment certains obstacles naturels.
Ali et al. (Mercredi,) ont étudié cette question.