# A simple axiomatization of the median procedure on median graphs

### Mulder, H.M. Novick, B.

Research Paper
This publication is part of collection
Related Files

(EI2011-25.pdf, 0.2MB)

A profile = (x1, ..., xk), of length k, in a finite connected graph G is a sequence of vertices of G, with repetitions allowed. A median x of is a vertex for which the sum of the distances from x to the vertices in the profile is minimum. The median function finds the set of all medians of a profile. Medians are important in location theory and consensus theory. A median graph is a graph for which every profile of length 3 has a unique median. Median graphs are well studied. They arise in many arenas, and have many applications. We establish a succinct axiomatic characterization of the median procedure on median graphs. This is a simplification of the characterization given by McMorris, Mulder and Roberts [17] in 1998. We show that the median procedure can be characterized on the class of all median graphs with only three simple and intuitively appealing axioms: anonymity, betweenness and consistency. We also extend a key result of the same paper, characterizing the median function for profiles of even length on median graphs.

Keywords

Automatically Extracted Terms
• graph
• function
• split
• axiom
• vertex
• location
• consensus
• theorem
• majority
• majority side
• subgraph
• vertice
• result
• mulder
• characterization
• ﬁle π xi
• split g 1
• ﬁle π
• property
• proof