Graphe de Barnette-Bosák-Lederberg

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

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.

Histoire

Le graphe de Barnette-Bosák-Lederberg est découvert par 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 contres-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 (en) 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

Propriétés générales

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.

Coloriage

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 tels que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Propriétés algébriques

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

Articles connexes

• Théorie des graphes
• Conjecture de Barnette (en)

Lien externe

• (en) Eric W. Weisstein, « Barnette-Bosák-Lederberg Graph », MathWorld
• (en) Eric W. Weisstein, « Tait's Hamiltonian Graph Conjecture », MathWorld

Références

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 », dans Philosophical Magazine (5th ser.), vol. 17, 1884, p. 30–46 . Reprinted in Scientific Papers, Vol. II, pp. 85–98.
5. ↑ (en) W. T. Tutte, « On Hamiltonian circuits », dans Journal of the London Mathematical Society (2nd ser.), vol. 21, n^o 2, 1946, p. 98–101 [texte intégral] 
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 », dans Journal of Combinatorial Theory, Series B, vol. 45, n^o 3, 1988, p. 305–319 [lien DOI]