The plurality strategy on graphs

Goldman [Transportation Science 5 (1971), 212-221] proved the classical result on how to find the medians for a set of clients in a tree using majority rule. Here the clients are located at vertices of the tree, and a median is a vertex in the tree that minimizes the sum of the distances to the locations of the clients. The majority rule can be rephrased as the Majority Strategy: if we are at vertex v, thenwemoveto neighbor w of v if a majority of the clients is closer to w than to v. This strategy can be applied in any connected graph. In Mulder [Discrete Applied Math. 80 (1997), 97-105] the question was answered for which connected graphs the Majority Strategy always produces the set of medians for any given set of clients: these are precisely the median graphs. This class of graphs has been well-studied in the literature. In this paper we relax the Majority Strategy: instead of requiring a majority of the clients to be.