Kannan, Balakrishnan; Sandi, Klavzar; Manoj, Changat(Elsevier, December 31, 2007)
[+]
[-]
Abstract:
The median of a profile = (u1, . . . , uk ) of vertices of a graph G is the set of vertices x that minimize the sum of distances
from 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 that contains a vertex x of and the r -ball around x, where r > 2 − 1 − 2 /| |. The median index of a graph
and r -joins of graphs are introduced and it is shown that r -joins preserve the property of having a large median index. Consensus
strategies are also briefly discussed on a graph with bounded profiles.