Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe hypohamiltonien
Résumé
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.
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. Le second graphe de cette suite est le graphe à 16 sommets illustré ci-contre. Lindgren cite alors Gaudin, Herz et Rossi puis Busacker et Saaty 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.
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. 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. La réponse est apportée en 1976 par Carsten Thomassen, qui exhibe un exemple à 105 sommets, le 105-graphe de Thomassen.
En 1979, Hatzel améliore ce résultat en introduisant un graphe hypohamiltonien planaire à 57 sommets : le graphe de Hatzel.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.