Le graphe de Wiener-Araya est, en théorie des graphes, un graphe possédant 42 sommets et 67 arêtes. Il est hypohamiltonien, c'est-à-dire qu'il n'a pas de cycle hamiltonien mais que la suppression de n'importe lequel de ses sommets suffit à le rendre hamiltonien. Il est également planaire.
Histoire
Les graphes hypohamiltoniens furent étudiés pour la première fois par Sousselier en 1963 dans Problèmes plaisants et délectables[1]. En 1967, Lindgren découvre une séquence infinie de graphes hypohamiltoniens[2]. Il cite alors Gaudin, Herz et Rossi[3] puis Busacker et Saaty[4] en tant qu'autres précurseurs sur le sujet.
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 Václav 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[6].
En 1979, Hatzel améliore ce résultat en introduisant un graphe hypohamiltonien planaire à 57 sommets : le graphe de Hatzel[7]. Ce graphe est battu en 2007 par le 48-graphe de Zamfirescu[8].
En 2009, c'est le graphe découvert par Gábor Wiener et Makoto Araya qui devient avec ses 42 sommets le plus petit graphe hypohamiltonien planaire connu[9]. Dans leur article, Wiener et Araya émettent l'hypothèse de la minimalité de leur graphe et plaisantent sur son ordre, égal à 42, et coïncidant avec la réponse à La Grande Question sur la vie, l'univers et le reste présente dans l'œuvre de l'humoriste Douglas Adams, Le Guide du voyageur galactique.
Références
↑R. Sousselier, « Problème no. 29: Le cercle des irascibles », dans Claude Berge, Problèmes plaisants et délectables, vol. 7, Rev. Franç. Rech. Opérationnelle, , p. 405–406
