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 u,v distants de k, et pour tous entiers naturels i,j, il y a toujours le même nombre de sommets qui sont à la fois à distance i de u et à distance j de v.

De manière équivalente, un graphe est distance-régulier si pour tous sommets u,v∈V, le nombre de sommets voisins de u à distance i de v et le nombre de sommets voisins de v à distance j de u ne dépendent que de i,j et de la distance d(u,v) entre u et v.

Formellement, ∃bi,ci∈N,i=0...d tels que b0=0 et

∀i≥1,bi=|N(v)∩Ni−1(u)|,ci=|N(v)∩Ni+1(u)|

où Ni(u) est l’ensemble des sommets à distance i de u, et N(u)=N1(u). La séquence {b1,b2,…,bd;c1,c2,…,cd} forme un vecteur appelé vecteur d'intersection du graphe.

Propriétés

Exemples