Graphe distance-régulier

En théorie des graphes, un graphe régulier est dit distance-régulier si pour tous sommets ${\displaystyle u,v}$ distants de ${\displaystyle k}$, et pour tous entiers naturels ${\displaystyle i,j}$, il y a toujours le même nombre de sommets qui sont à la fois à distance ${\displaystyle i}$ de ${\displaystyle u}$ et à distance ${\displaystyle j}$ de ${\displaystyle v}$.

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

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

Formellement, ${\displaystyle \exists b_{i},c_{i}\in N,i=0...d}$ tels que ${\displaystyle b_{0}=0}$ et

${\displaystyle \forall i\geq 1,b_{i}=|N(v)\cap N_{i-1}(u)|,c_{i}=|N(v)\cap N_{i+1}(u)|}$

où ${\displaystyle N_{i}(u)}$ est l’ensemble des sommets à distance ${\displaystyle i}$ de ${\displaystyle u}$, et ${\displaystyle N(u)=N_{1}(u)}$. La séquence ${\displaystyle \{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

• 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 K_n 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