Ê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 Graph Search.
Concept
Graphe de Nauru
Résumé
En mathématiques, et plus précisément en théorie des graphes, le graphe de Nauru est un graphe 3-régulier possédant 24 sommets et 36 arêtes. Il a été nommé ainsi par David Eppstein d'après l'étoile à 12 branches ornant le drapeau de Nauru.
Le diamètre du graphe de Nauru, l'excentricité maximale de ses sommets, est 4, son rayon, l'excentricité minimale de ses sommets, est 4 et sa maille, la longueur de son plus court cycle, est 6. 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 Nauru 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. Ce nombre est minimal.
L'indice chromatique du graphe de Nauru 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 graphe de Nauru est symétrique, c'est-à-dire que son groupe d'automorphismes agit transitivement sur ses arêtes, ses sommets et ses arcs. Il est donc également arête-transitif et sommet-transitif. Le graphe de Nauru est l'unique graphe cubique symétrique à 24 sommets et sa notation dans le Foster Census, le catalogue classifiant tous les graphes cubiques symétriques, est F24A.
Le groupe d'automorphismes du graphe de Nauru est d'ordre 144. Sa structure exacte est connue : il est isomorphe au produit direct des groupes symétriques S4 et S3.
Le graphe de Petersen généralisé G(n,k) est sommet-transitif si et seulement si n = 10 et k =2 ou si k2 ≡ ±1 (mod n). Il est arête-transitif seulement dans les sept cas qui suivent : (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). Donc le graphe de Nauru est un des sept graphes de Petersen généralisés symétriques. Les six autres sont le graphe hexaédrique , le graphe de Petersen , le graphe de Möbius-Kantor , le graphe dodécaédrique et le graphe de Desargues .
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.