Concept

Graphe de Biggs-Smith

Résumé
Le graphe de Biggs-Smith est, en théorie des graphes, un graphe 3-régulier possédant 102 sommets et 153 arêtes. Propriétés Propriétés générales Le diamètre du graphe de Biggs-Smith, l'excentricité maximale de ses sommets, est 7, son rayon, l'excentricité minimale de ses sommets, est 7 et sa maille, la longueur de son plus court cycle, est 9. 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 sommet ou de 3 arêtes. La graphe de Biggs-Smith est l'un des 13 graphes cubiques distance-réguliers. Il est également hamiltonien et possède cycles hamiltoniens distincts. Coloration Le nombre chromatique du graphe de Biggs-Smith est 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. Ce nombre est minimal. L'indice chromatique du graphe
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement