Accueil🇫🇷Chercher

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 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, 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

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, , p. 405–406
  2. (en) W. F. Lindgren, « An infinite class of hypohamiltonian graphs », American Mathematical Monthly, vol. 74,‎ , p. 1087–1089 (DOI 10.2307/2313617), lien Math Reviews
  3. T. Gaudin, P. Herz et Rossi, « Solution du problème No. 29 », Rev. Franç. Rech. Opérationnelle, vol. 8,‎ , p. 214–218
  4. (en) R. G. Busacker et T. L. Saaty, Finite Graphs and Networks, McGraw-Hill,
  5. (en) V. Chvátal, « Flip-flops in hypo-Hamiltonian graphs », Canadian Mathematical Bulletin, vol. 16,‎ , p. 33–41, lien Math Reviews
  6. 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, , 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 », Discrete Mathematics, vol. 10,‎ 1974b, p. 383–390 (DOI 10.1016/0012-365X(74)90128-9), lien Math Reviews
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.