Graphe médian

En théorie des graphes, les médians d'un triplet de sommets $u,v,w \in G$ sont les sommets z se trouvant sur les plus courts chemins entre ces sommets^[1]. Autrement dit, si I(u,v) est l'ensemble de sommets sur les plus courts chemins entre u et v, alors l'ensemble des sommets médians est $S_m = \{I(u,v) \cap I(u,w) \cap I(v,w)\}$. Un graphe médian respecte la propriété qu'il n'y a qu'un seul sommet médian pour tout triplet de sommets, c'est-à-dire $|I(u,v) \cap I(u,w) \cap I(v,w)| = 1$.

Propriétés

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !

• Le produit cartésien de deux graphes médians est un graphe médian.
• Le seul graphe médian régulier est l'hypercube.
• Les arbres sont des graphes médians^[1].

Notes et références

1. ↑ ^{a et b} (en)Wilfriend Imrich et Sandi Klavzar - Product Graphs: Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, 2000, (ISBN 0471370398).