Graphe de Barnette-Bosák-Lederberg - Définition

Introduction

Graphe de 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 un graphe 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. Lederberg le construit en cherchant une 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.

A peu près à la même époque, D. Barnette et J. Bosák construisent six contres-exemples d'ordre 38 à la conjecture de Tait, redécouvrant indépendamment le graphe de Barnette.

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. C'est cependant, lors de sa publication, le plus petit contre-exemple connu à la conjecture de Tait. En 1988, Holton et Brendan McKay prouvent sa minimalité et construisent les 6 seuls graphes d'ordre 38 étant des contre-exemple à la conjecture de Tait.

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.