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.

Additional Metadata
Keywords Axioms, Location function, Median graph, Target function
Persistent URL dx.doi.org/10.1016/j.dam.2020.03.050, hdl.handle.net/1765/126174
Journal Discrete Applied Mathematics
Citation
Leach, T. (Trevor), McMorris, F.R, Mulder, H.M, & Powers, R.C. (2020). The target location function on finite trees. Discrete Applied Mathematics. doi:10.1016/j.dam.2020.03.050