The target location function on finite trees

A location function on a finite connected graph G takes as input any k-tuple of vertices (a profile) and outputs a single vertex. If G is a full y gated graph, then a target location function is defined by a predetermined vertex (the target) and outputs the unique vertex belonging to the convex closure of the profile which is closest to the target. If G is a finite tree, then any target function on G satisfies two conditions known in the literature as Pareto efficiency and replacement domination. We give a simple example to show that these two conditions do not characterize target functions on trees. A new condition, called the neighborhood condition, is introduced and we prove that target functions on trees are the only location functions satisfying Pareto efficiency, replacement domination, and the neighborhood condition.

• View at Publisher
• View at Scopus