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.
|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|
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