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