Graphe distance-régulier
- Graphe distance-régulier
-
En théorie des graphes, un graphe est distance-régulier si pour tous sommets 
, le nombre de sommets voisins de u à distance i et le nombre de sommets voisins de v à distance j ne dépendent que de i,j et de la distance d(u,v) entre u et v.
Formellement, 
tels que c0 = 0 et
La séquence 
forme un vecteur appelé vecteur d'intersection du graphe.
Propriétés
- Un graphe distance-régulier est régulier.
- Un graphe distance-régulier de diamètre 2 est fortement régulier, et réciproquement (sauf si le graphe n'est pas connexe).
- Un graphe distance-transitif est toujours distance-régulier.
Exemples
- Tous les graphes cubiques étant distance-régulier sont connus. Ils sont 13 : le graphe biparti complet K(3,3), le graphe tétraédrique, le graphe hexaédrique, le graphe de Petersen, le graphe de Heawood, le graphe de Pappus, le graphe de Desargues, le graphe dodécaédrique, le graphe de Coxeter, le graphe de Tutte–Coxeter, le graphe de Foster, le graphe de Biggs-Smith, et la 12-cage de Tutte.
- Le premier graphe de Chang, le second graphe de Chang et le troisième graphe de Chang sont tous les trois distance-régulier avec un vecteur d'intersection égal à {12,5;1,4}.
- Le graphe complet Kn est distance-régulier de diamètre 1 et de degré n-1.
- Tous les graphes de Moore, notamment le graphe de Hoffman-Singleton, sont distance-réguliers.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe distance-régulier de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe fortement régulier — Le graphe de Paley d ordre 13, un graphe fortement régulier de type (13,6,2,3). En théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe qui est en particulier un graphe régulier. Soit G =… … Wikipédia en Français
Graphe de Hamming — H(4,2) Notation H(d,q) Nombre de sommets qd Nombre d arêtes … Wikipédia en Français
Graphe partiel — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A … Wikipédia en Français
Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier … Wikipédia en Français
Graphe tesseract — Une représentation du graphe tesseract. Nombre de sommets 16 Nombre d arêtes 32 Distribution des degrés 4 régulier Rayon 4 … Wikipédia en Français
Graphe hexaédrique — Représentation du graphe hexaédrique. Nombre de sommets 8 Nombre d arêtes 12 Distribution des degrés 3 régulier Rayon 3 … Wikipédia en Français
Graphe de Harborth — Nombre de sommets 52 Nombre d arêtes 104 Distribution des degrés 4 régulier Rayon 6 Diamètre 9 Maille … Wikipédia en Français
Graphe de Biggs-Smith — Représentation du graphe de Biggs Smith Nombre de sommets 102 Nombre d arêtes 153 Rayon 7 Diamètre 7 … Wikipédia en Français
Graphe tétraédrique — Représentation du graphe tétraédrique. Nombre de sommets 4 Nombre d arêtes 6 Distribution des degrés 3 régulier Rayon 1 … Wikipédia en Français
Graphe octaédrique — Représentation du graphe octaédrique. Nombre de sommets 6 Nombre d arêtes 12 Distribution des degrés 4 régulier Rayon … Wikipédia en Français
