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.

Histoire

Un graphe hypohamiltonien d'ordre 16 décrit par Lindgren en 1967.

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 (en) 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.

Planarité

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 (en), 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].

Exemples

• 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.

Références

1. ↑ 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, 1963, p. 405–406 
2. ↑ (en) W. F. Lindgren, « An infinite class of hypohamiltonian graphs », dans American Mathematical Monthly, vol. 74, 1967, p. 1087–1089 [lien DOI] , MR0224501
3. ↑ T. Gaudin, « Solution du problème No. 29 », dans Rev. Franç. Rech. Opérationnelle, vol. 8, 1964, p. 214–218 
4. ↑ (en) R. G. Busacker et T. L. Saaty, Finite Graphs and Networks, McGraw-Hill, 1965 
5. ↑ ^{a, b et c} (en) V. Chvátal, « Flip-flops in hypo-Hamiltonian graphs », dans Canadian Mathematical Bulletin, vol. 16, 1973, p. 33–41 , MR0371722
6. ↑ ^{a, b et c} J. C. Herz, J. J. Duby et F. Vigué, « Recherche systématique des graphes hypohamiltoniens », dans Pierre Rosenstiehl, Theory of Graphs: International Symposium, Rome 1966, Paris, Gordon and Breach, 1967, p. 153–159 
7. ↑ (en) Thomassen, C. "Planar and Infinite Hypohamiltonian and Hypotraceable Graphs." Disc. Math 14, 377-389, 1976
8. ↑ (de) Hatzel, H. "Ein planarer hypohamiltonscher Graph mit 57 Knoten." Math Ann. 243, 213-216, 1979
9. ↑ (en) C. T. Zamfirescu et T. I. Zamfirescu, « A Planar Hypohamiltonian Graph with 48 Vertices » dans J. Graph Th. 48 (2007), 338-342
10. ↑ (en) G. Wiener et M. Araya, The Ultimate Question, 20 avril 2009, arXiv:0904.3012
11. ↑ (en) Carsten Thomassen, « On hypohamiltonian graphs », dans Discrete Mathematics, vol. 10, 1974b, p. 383–390 [lien DOI] , MR0357226