Graphe distance-régulier
De Wikipedia, l'encyclopédie encyclopedia
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
.
Davantage d’informations Familles de graphes définies par leurs automorphismes, → ...
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 |
Fermer
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.