48-graphe de Zamfirescu

graphe hypohamiltonien

Le 48-graphe de Zamfirescu est, en théorie des graphes, un graphe possédant 48 sommets et 76 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 : il est possible de le représenter sur un plan sans qu'aucune arête n'en croise une autre.

48-Graphe de Zamfirescu
Image illustrative de l’article 48-graphe de Zamfirescu
Représentation du 48-graphe de Zamfirescu.

Nombre de sommets 48
Nombre d'arêtes 76
Distribution des degrés 3 (40 sommets)
4 (8 sommets)
Rayon 6
Diamètre 7
Maille 4
Automorphismes 8 (D4)
Nombre chromatique 3
Indice chromatique 4
Propriétés Hypohamiltonien
Planaire

Histoire

modifier

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

Propriétés

modifier

Propriétés générales

modifier

Le diamètre du 48-graphe de Zamfirescu, l'excentricité maximale de ses sommets, est 7, son rayon, l'excentricité minimale de ses sommets, est 6 et sa maille, la longueur de son plus court cycle, est 4. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.

Coloration

modifier

Le nombre chromatique du 48-graphe de Zamfirescu est 3. C'est-à-dire qu'il est possible de le colorer avec 3 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.

L'indice chromatique du 48-graphe de Zamfirescu est 4. Il existe donc une 4-coloration des arêtes du graphe telles que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Propriétés algébriques

modifier

Le groupe d'automorphismes du 48-graphe de Zamfirescu est un groupe d'ordre 8 isomorphe au groupe diédral D4, le groupe des isométries du plan conservant un carré. Ce groupe est constitué de 4 éléments correspondant aux rotations et de 4 autres correspondant aux réflexions.

Notes et références

modifier
  1. R. Sousselier et C. Berge (dir.), « Problèmes plaisants et délectables : Problème no. 29: Le cercle des irascibles », Rev. Franç. Rech. Opérationnelle, vol. 7,‎ , 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 (MR 0371722)
  6. (en) C. Thomassen, « Planar and Infinite Hypohamiltonian and Hypotraceable Graphs », Discrete Math. 14 (1976), 377-389
  7. (de) H. Hatzel, « Ein planarer hypohamiltonscher Graph mit 57 Knoten », Math. Ann. 243 (1979), 213-216
  8. (en) C. T. Zamfirescu et T. I. Zamfirescu, « A Planar Hypohamiltonian Graph with 48 Vertices », Journal of Graph Theory 48 (2007), 338-342
  9. (en) G. Wiener et M. Araya, The Ultimate Question, 20 avril 2009, arXiv:0904.3012

Voir aussi

modifier

Articles connexes

modifier

Lien externe

modifier

(en) Eric W. Weisstein, « Zamfirescu Graphs », sur MathWorld