An ABC-Problem for Location and Consensus Functions on Graphs

Martyn Mulder, FR McMorris, B Novick, RC Powers

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

Abstract

A location problem can often be phrased as a consensus problem. The median function View the MathML sourceMed 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 ??, View the MathML sourceMed 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 View the MathML sourceMed. This result raises a number of questions: (i) On what other classes of graphs is View the MathML sourceMed characterized by (A)(A), (B)(B) and (C)(C)? (ii) If some class of graphs has other ABCABC-functions besides View the MathML sourceMed, can we determine additional axioms that are needed to characterize View the MathML sourceMed? (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.
Original languageEnglish
Pages (from-to)15-28
Number of pages14
JournalDiscrete Applied Mathematics
Volume207
DOIs
Publication statusPublished - 29 Jan 2016

Fingerprint

Dive into the research topics of 'An ABC-Problem for Location and Consensus Functions on Graphs'. Together they form a unique fingerprint.

Cite this