Local medians in chordal graphs (Q2640607)

Let the vertices of a graph G be weighted by a function \(\pi\) : V(G)\(\to R^+_ 0\). The distance sum D(v) of a vertex v is defined to be \(\sum \{d(u,v)\pi (u)| u\in V(G)\}\) where d(u,v) is the distance between u and v. The median set of G consists of those vertices that minimize the distance sum. If the distance sum of a vertex v is minimal with respect to the neighbours of v, then v is called a local median. In this paper it is shown that every local median of a chordal graph is also a median, with respect to any weight functions, if a certain neighbourhood condition is satisfied. Moreover, the subgraph induced by the median set is connected in this case.