48-graphe de Zamfirescu

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 classe 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], dont les créateurs sont deux mathématiciens roumains : Carol Zamfirescu et Tudor Zamfirescu.. En 2009, le graphe de Zamfirescu est battu à son tour par le graphe de Wiener-Araya, qui devient avec ses 42 sommets le plus petit graphe hypohamiltonien planaire connu[9].