Abstract

A median (antimedian) of a profile of vertices on a graph $G$ is a vertex that minimizes (maximizes) the remoteness value, that is, the sum of the distances to the elements in the profile. The median (or antimedian) function has as output the set of medians (antimedians) of a profile. It is one of the basic models for the location of a desirable (or obnoxious) facility in a network. The median function is well studied. For instance it has been characterized axiomatically by three simple axioms on median graphs. The median function behaves nicely on many classes of graphs. In contrast the antimedian function does not have a nice behavior on most classes. So a nice axiomatic characterization may not be expected. In this paper an axiomatic characterization is obtained for the median and antimedian functions on complete graphs minus a perfect matching (also known as cocktail-party graphs). In addition a characterization of the antimedian function on complete graphs is presented.

, , , , , ,
Erasmus University Rotterdam
hdl.handle.net/1765/77639
Econometric Institute Research Papers
Erasmus School of Economics

Changat, M., Lekha, D., Mulder, M., & Subhamathi, A. (2014). Axiomatic Characterization of the Median and
Antimedian Functions on Cocktail-Party Graphs and
Complete Graphs (No. EI 2014-31). Econometric Institute Research Papers. Retrieved from http://hdl.handle.net/1765/77639