Graphe de Barnette-Bosák-Lederberg
Le graphe de Barnette-Bosák-Lederberg est, en théorie des graphes, un graphe 3-régulier possédant 38 sommets et 57 arêtes. C'est le plus petit contre-exemple possible à la conjecture de Tait sur les graphes hamiltoniens.
| Graphe de Barnette-Bosák-Lederberg | |
 Représentation du graphe Barnette-Bosák-Lederberg | |
| Nombre de sommets | 38 |
|---|---|
| Nombre d'arêtes | 57 |
| Distribution des degrés | 3-régulier |
| Rayon | 5 |
| Diamètre | 9 |
| Maille | 4 |
| Automorphismes | 2 (Z/2Z) |
| Nombre chromatique | 3 |
| Indice chromatique | 3 |
| Propriétés | Cubique Planaire Sans triangle Non-hamiltonien |
modifier  |
|
Histoire
modifierLe graphe de Barnette-Bosák-Lederberg est découvert par le généticien Joshua Lederberg en 1965[1]. Lederberg le construit en cherchant un contre-exemple minimal à la conjecture de Tait sur les graphes hamiltoniens, c'est-à-dire un graphe planaire non-hamiltonien étant 3-sommet-connexe. Lederberg émet l'hypothèse de sa minimalité mais est incapable de la prouver. Il démontre cependant qu'un contre-exemple minimal à la conjecture de Tait doit avoir strictement plus de 24 sommets.
À peu près à la même époque, David Barnette et Juraj Bosák (sk) construisent six contre-exemples d'ordre 38 à la conjecture de Tait, redécouvrant indépendamment le graphe de Barnette[2],[3].
Le graphe de Barnette-Bosák-Lederberg n'est pas le premier graphe de ce type puisque la conjecture de Tait, énoncée en 1884, est prouvée fausse dès 1946 par William Tutte qui construit alors un contre-exemple à 46 sommets, le graphe de Tutte[4],[5]. Par la suite d'autres contre-exemples sont construits, notamment trois par Grinberg (le 46-graphe de Grinberg, le 44-graphe de Grinberg et le 42-graphe de Grinberg), et deux par Faulkner et Younger (le 44-graphe de Faulkner-Younger et le 42-graphe de Faulkner-Younger)[6],[7].
Bien que sa minimalité ne soit pas prouvée, lors de sa publication, le graphe de Barnette-Bosák-Lederberg est le plus petit contre-exemple connu à la conjecture de Tait. En 1988, Derek Holton et Brendan McKay prouvent qu'il est impossible de construire un contre-exemple à la conjecture de Tait avec moins de 38 sommets. Dans le même article, ils démontrent que les 6 graphes décrits par D. Barnette et J. Bosák sont les seuls de cet ordre[8].
Propriétés
modifierPropriétés générales
modifierLe diamètre du graphe de Barnette-Bosák-Lederberg, l'excentricité maximale de ses sommets, est 9, son rayon, l'excentricité minimale de ses sommets, est 5 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
modifierLe nombre chromatique du graphe de Barnette-Bosák-Lederbergest 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 mais ce nombre est minimal. Il n'existe pas de 2-coloration valide du graphe.
L'indice chromatique du graphe de Barnette-Bosák-Lederberg est 3. Il existe donc une 3-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.
Propriétés algébriques
modifierLe groupe d'automorphismes du graphe de Barnette-Bosák-Lederberg est un groupe abélien d'ordre 2 : le groupe cyclique Z/2Z.
Voir aussi
modifierArticles connexes
modifierLiens externes
modifier- (en) Eric W. Weisstein, « Barnette-Bosák-Lederberg Graph », sur MathWorld
- (en) Eric W. Weisstein, « Tait's Hamiltonian Graph Conjecture », sur MathWorld
Références
modifier- (en) Lederberg, J. "DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs." Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. [1]
- (en) Eric W. Weisstein, Barnette-Bosák-Lederberg Graph (MathWorld)
- (en) Derek Holton and Robert E. L. Aldred. Planar Graphs, Regular Graphs, Bipartite Graphs and Hamiltonicity. Australasian Journal of Combinatorics, 20:111–131, 1999. [2]
- (en) P. G. Tait, « Listing's Topologie », Philosophical Magazine (5th ser.), vol. 17, , p. 30–46. Reprinted in Scientific Papers, Vol. II, pp. 85–98.
- (en) W. T. Tutte, « On Hamiltonian circuits », Journal of the London Mathematical Society (2nd ser.), vol. 21, no 2, , p. 98–101 (lire en ligne)
- (en) Faulkner, G. B. and Younger, D. H. "Non-Hamiltonian Cubic Planar Maps." Discr. Math. 7, 67-74, 1974.
- Claude Berge, Graphes et hypergraphes, Dunod, 1973.
- (en) D. A. Holton et B. D. McKay, « The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices », Journal of Combinatorial Theory, Series B, vol. 45, no 3, , p. 305–319 (DOI 10.1016/0095-8956(88)90075-5)
