Graphe distance-régulier
Familles de graphes définies par leurs automorphismes | ||||
---|---|---|---|---|
distance-transitif | → | distance-régulier | ← | fortement régulier |
↓ | ||||
symétrique (arc-transitif) | ← | t-transitif, (t ≥ 2) | symétrique gauche (en) | |
↓ | ||||
(si connexe) sommet-transitif et arête-transitif | → | régulier et arête-transitif | → | arête-transitif |
↓ | ↓ | ↓ | ||
sommet-transitif | → | régulier | → | (si biparti) birégulier |
↑ | ||||
graphe de Cayley | ← | zéro-symétrique | asymétrique |
En théorie des graphes, un graphe régulier est dit distance-régulier si pour tous sommets distants de , et pour tous entiers naturels , il y a toujours le même nombre de sommets qui sont à la fois à distance de et à distance de .
De manière équivalente, un graphe est distance-régulier si pour tous sommets , le nombre de sommets voisins de à distance de et le nombre de sommets voisins de à distance de ne dépendent que de et de la distance entre et .
Formellement, tels que et
où est l’ensemble des sommets à distance de , 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.
Portail de l'informatique théorique
Portail des mathématiques