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
Image illustrative de l’article 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

Histoire

modifier

Le 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

modifier

Propriétés générales

modifier

Le 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

modifier

Le 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

modifier

Le 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

modifier

Articles connexes

modifier

Liens externes

modifier

Références

modifier
  1. (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]
  2. (en) Eric W. Weisstein, Barnette-Bosák-Lederberg Graph (MathWorld)
  3. (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]
  4. (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.
  5. (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)
  6. (en) Faulkner, G. B. and Younger, D. H. "Non-Hamiltonian Cubic Planar Maps." Discr. Math. 7, 67-74, 1974.
  7. Claude Berge, Graphes et hypergraphes, Dunod, 1973.
  8. (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)