105-graphe de Thomassen
Le 105-graphe de Thomassen est, en thĂ©orie des graphes, un graphe possĂ©dant 105 sommets et 170 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.
| 105-Graphe de Thomassen | |
| Nombre de sommets | 105 |
|---|---|
| Nombre d'arĂȘtes | 170 |
| Distribution des degrés | 3 (85 sommets) 4 (15 sommets) 5 (5 sommets) |
| Rayon | 8 |
| DiamĂštre | 9 |
| Maille | 5 |
| Nombre chromatique | 3 |
| Indice chromatique | 5 |
| 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 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]. 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
Propriétés générales
Le diamĂštre du 105-graphe de Thomassen, l'excentricitĂ© maximale de ses sommets, est 9, son rayon, l'excentricitĂ© minimale de ses sommets, est 8 et sa maille, la longueur de son plus court cycle, est 5. 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
Le nombre chromatique du 105-graphe de Thomassen 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 105-graphe de Thomassen est 5. Il existe donc une 5-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.
Voir aussi
Notes et références
- 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
- (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
- T. Gaudin, P. Herz et Rossi, « Solution du problĂšme No. 29 », Rev. Franç. Rech. OpĂ©rationnelle, vol. 8,â , p. 214â218
- (en) R. G. Busacker et T. L. Saaty, Finite Graphs and Networks, McGraw-Hill,
- (en) V. ChvĂĄtal, « Flip-flops in hypo-Hamiltonian graphs », Canadian Mathematical Bulletin, vol. 16,â , p. 33â41, lien Math Reviews
- (en) C. Thomassen, « Planar and Infinite Hypohamiltonian and Hypotraceable Graphs », Disc. Math 14, 377-389, 1976
- (de) H. Hatzel, « Ein planarer hypohamiltonscher Graph mit 57 Knoten », Math Ann. 243, 213-216, 1979
- (en) C. T. Zamfirescu et T. I. Zamfirescu, « A Planar Hypohamiltonian Graph with 48 Vertices », J. Graph Th. 48 (2007), 338-342
- (en) G. Wiener et M. Araya, The Ultimate Question, 20 avril 2009, arXiv:0904.3012
Lien externe
(en) Eric W. Weisstein, « Thomassen Graphs », sur MathWorld