An ABCABC-Problem for location and consensus functions on graphs

A location problem can often be phrased as a consensus problem. The median function Med is a location/consensus function on a connected graph GG that has the finite sequences of vertices of GG as input. For each such sequence ππ, Med returns the set of vertices that minimize the distance sum to the elements of ππ. The median function satisfies three intuitively clear axioms: (A)(A) Anonymity, (B)(B) Betweenness and (C)(C) Consistency. Mulder and Novick showed in 2013 that on median graphs these three axioms actually characterize Med. This result raises a number of questions: (i)On what other classes of graphs is Med characterized by (A)(A), (B)(B) and (C)(C)?(ii)If some class of graphs has other ABCABC-functions besides Med, can we determine additional axioms that are needed to characterize Med?(iii)In the latter case, can we find characterizations of other functions that satisfy (A)(A), (B)(B) and (C)(C)?We call these questions, and related ones, the ABCABC-Problem   for consensus functions on graphs. In this paper we present first results. We construct a non-trivial class different from the median graphs, on which the median function is the unique “ABCABC-function”. For the second and third question we focus on KnKn with n≥3n≥3. We construct various non-trivial ABCABC-functions amongst which is an infinite family on K3K3. For some nice families we present a full axiomatic characterization.