The median function on graphs with bounded profiles

The median of a profile π=(u1,…,uk)π=(u1,…,uk) of vertices of a graph GG is the set of vertices xx that minimize the sum of distances from xx to the vertices of ππ. It is shown that for profiles ππ with diameter θθ the median set can be computed within an isometric subgraph of GG that contains a vertex xx of ππ and the rr-ball around xx, where r>2θ−1−2θ/|π|r>2θ−1−2θ/|π|. The median index of a graph and rr-joins of graphs are introduced and it is shown that rr-joins preserve the property of having a large median index. Consensus strategies are also briefly discussed on a graph with bounded profiles.