An ABC-Problem for location and consensus functions on graphs

作者：McMorris F R; Mulder Henry Martyn^*; Novick Beth; Powers Robert C

来源：Discrete Applied Mathematics, 2016, 207: 15-28.

DOI：10.1016/j.dam.2015.12.008

• Median function
• Location function
• Consensus function
• Voting
• Consensus axiom
• ABC-Problem

A location problem can often be phrased as a consensus problem. The median function Med is a location/consensus function on a connected graph G that has the finite sequences of vertices of G as input. For each such sequence pi, Med returns the set of vertices that minimize the distance sum to the elements of pi. The median function satisfies three intuitively clear axioms: (A) Anonymity, (B) Betweenness and (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), (B) and (C)?
(ii) If some class of graphs has other ABC-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), (B) and (C)?
We call these questions, and related ones, the ABC-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 "ABC-function". For the second and third question we focus on K-n, with n >= 3. We construct various non-trivial ABC-functions amongst which is an infinite family on K-3. For some nice families we present a full axiomatic characterization.

• 出版日期2016-7-10