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. HistoireLe 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ésPropriétés généralesLe 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. ColorationLe 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ébriquesLe groupe d'automorphismes du graphe de Barnette-Bosák-Lederberg est un groupe abélien d'ordre 2 : le groupe cyclique Z/2Z. Voir aussiArticles connexesLiens externes
Références
|