Graphe distance-régulier

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, un graphe est distance-régulier si pour tous sommets u, v \in V, 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, \exists b_i, c_i \in N, i = 0...d tels que c_0 = 0 et

\forall i \ge 1, c_i = |N(v) \cap N_{i-1}(u)|, b_i = |N(v) \cap N_{i+1}(u)|

La séquence \{b_1,b_2,\dots,b_d; c_1,c_2,\dots,c_d \} forme un vecteur appelé vecteur d'intersection du graphe.

Propriétés[modifier | modifier le code]

Exemples[modifier | modifier le code]