Graphe distance-régulier

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Familles de graphes définies par leurs automorphismes
distance-transitif distance-régulier fortement régulier
symétrique (transitif aux arcs) t-transitif, (t ≥ 2) symétrique gauche
(si connexe)
sommet-transitif et arc-transitif
régulier et arc-transitif arc-transitif
sommet-transitif régulier (si bipartite)
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 | modifier le code]

Exemples[modifier | modifier le code]