Graphe de Wiener-Araya

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.

Graphe de Wiener-Araya

Représentation du graphe de Wiener-Araya.
Nombre de sommets 42
Nombre d'arêtes 67
Distribution des degrés 3 (34 sommets)
4 (8 sommets)
Maille 4
Propriétés Hypohamiltonien
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
  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. (en) C. Thomassen, "Planar and Infinite Hypohamiltonian and Hypotraceable Graphs." Disc. Math 14, 377-389, 1976
  7. (de) H. Hatzel, "Ein planarer hypohamiltonscher Graph mit 57 Knoten." Math Ann. 243, 213-216, 1979
  8. (en) C. T. Zamfirescu et T. I. Zamfirescu, « A Planar Hypohamiltonian Graph with 48 Vertices » dans J. Graph Th. 48 (2007), 338-342
  9. (en) G. Wiener et M. Araya, The Ultimate Question, 20 avril 2009, arXiv:0904.3012

Lien externe

(en) Eric W. Weisstein, « Wiener-Araya Graph », sur MathWorld

  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.