Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
10-cage de Balaban
Résumé
La 10-cage de Balaban (ou (3,10)-cage de Balaban) est, en théorie des graphes, un graphe régulier possédant 70 sommets et 105 arêtes.
Il porte le nom du mathématicien A. T. Balaban qui en a publié la description en 1972.
La 10-cage de Balaban est une (3,10)-cage, c'est-à-dire un graphe minimal en nombres de sommets ayant une maille de 10 et étant régulier de degré 3. Il s'agit de la première cage de ce type à avoir été découverte, mais elle n'est pas unique. La liste complète des (3-10)-cages a été donnée par O'Keefe et Wong en 1980. Il en existe trois distinctes, les deux autres étant le graphe de Harries et le graphe de Harries-Wong.
La 10-cage de Balaban est un graphe hamiltonien. Elle possède cycles hamiltoniens distincts.
Le diamètre de la 10-cage de Balaban, l'excentricité maximale de ses sommets, ainsi que son rayon, l'excentricité minimale de ses sommets, sont tous deux égaux à 6. Cela entraîne que tous ses sommets appartiennent à son centre. Il s'agit par ailleurs 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. Comme il est régulier de degré 3, ce nombre est optimal. La 10-cage de Balaban est donc un graphe optimalement connecté.
Le nombre chromatique de la 10-cage de Balaban est 2, c'est-à-dire qu'il est possible de le colorer avec 2 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes, et ce nombre est (évidemment) minimal.
L'indice chromatique de la 10-cage de Balaban est 3. Il existe donc une 3-coloration des arêtes du graphe telles que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes, et ce nombre est minimal.
Le groupe d'automorphismes de la 10-cage de Balaban est d'ordre 80.
Le polynôme caractéristique de la matrice d'adjacence de la 10-cage de Balaban est : .
Fichier:balaban_10-cage_2COL.svg|Représentation du [[coloration de graphe|nombre chromatique]] de la 10-cage de Balaban : 2.
Source officielle
À 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.