Graphe hypohamiltonien

En théorie des graphes, un graphe est hypohamiltonien s'il n'a pas de cycle hamiltonien mais que la suppression de n'importe quel sommet du graphe suffit à le rendre hamiltonien.

Les graphes hypohamiltoniens furent étudiés pour la première fois par Sousselier en 1963 dans Problèmes plaisants et délectables. Sous forme d'une petite énigme la notion est introduite. L'énoncé demande de trouver un tel graphe d'ordre 10 (le graphe de Petersen) et de prouver que cet ordre est minimal, c'est-à-dire qu'il n'existe pas de graphe hypohamiltonien à moins de 10 sommets^[1].

En 1967, Lindgren découvre une séquence infinie de graphes hypohamiltoniens. Cette séquence est formée de graphes à 6k+10 sommets pour tout k entier. Le premier élément de la séquence est le graphe de Petersen^[2]. Le second graphe de cette suite est le graphe à 16 sommets illustré ci-contre. Lindgren cite alors Gaudin, Herz et Rossi^[3] puis Busacker et Saaty^[4] en tant qu'autres précurseurs sur le sujet. La même séquence de graphes hypohamiltoniens à 6k+10 sommets est trouvée indépendamment par Sousselier^[5],[6].

En 1973, Václav Chvátal publie un article où il explique comment ajouter des arêtes à certains graphes hypohamiltoniens pour en faire d'autres du même ordre. Il attribue la paternité de la méthode à Bondy^[5]. Comme exemple il montre comment ajouter deux arêtes au second graphe de la séquence de Lindgren (qu'il appelle séquence de Sousselier) pour obtenir un nouveau graphe hypohamiltonien à 16 sommets. Le graphe ainsi obtenu est appelé le graphe de Sousselier.

Dès le départ, le plus petit graphe hypohamiltonien est connu : le graphe de Petersen. Cependant la recherche du plus petit graphe hypohamiltonien planaire reste ouverte. La question de l'existence d'un tel graphe est introduite par Chvátal en 1973^[5]. La réponse est apportée en 1976 par Carsten Thomassen, qui exhibe un exemple à 105 sommets, le 105-graphe de Thomassen^[7]. En 1979, Hatzel améliore ce résultat en introduisant un graphe hypohamiltonien planaire à 57 sommets : le graphe de Hatzel^[8]. Ce graphe est battu en 2007 par le 48-graphe de Zamfirescu^[9].

En 2009, c'est le graphe de Wiener-Araya qui devient avec ses 42 sommets le plus petit graphe hypohamiltonien planaire connu^[10]. Dans leur article, Wiener et Araya émettent l'hypothèse de la minimalité de leur graphe.

En 1967, Herz, Duby et Vigué conjecturent que tout graphe hypohamiltonien a une maille de 5 ou plus^[6]. Cette hypothèse est invalidée par Thomassen en 1974 qui introduit simultanément un graphe hypohamiltonien de maille 3, le 60-graphe de Thomassen, et un graphe hypohamiltonien de maille 4, le 32-graphe de Thomassen^[11].

• Le plus petit graphe hypohamiltonien est le graphe de Petersen^[6].
• Parmi les autres exemples connus on peut citer, par ordre croissant, le graphe de Sousselier, le premier snark de Blanuša et le second, le 20-graphe de Thomassen, le premier snark de Loupekine et le second, le premier snark de Celmins-Swart et le second, le graphe de Coxeter, le snark double étoile et le 32-graphe de Thomassen.

• Portail de l'informatique théorique