Graphe distance-régulier

(Redirigé depuis Vecteur d'intersection)
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

est l’ensemble des sommets à distance de , et . La séquence forme un vecteur appelé vecteur d'intersection du graphe.

Propriétés

modifier

Exemples

modifier