Graphe de Barnette-Bosák-Lederberg

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

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.

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.

Le groupe d'automorphismes du graphe de Barnette-Bosák-Lederberg est un groupe abélien d'ordre 2 : le groupe cyclique Z/2Z.

• Théorie des graphes
• Conjecture de Barnette

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

• Portail des mathématiques