Axiomatic characterization of the center function. The case of universal axioms

The center function on a connected graph G has as input a sequence of vertices of G. The output is the set of vertices that minimize the maximum distance to the entries of the input. If the input is a sequence containing each vertex of G once, then the output is just the classical center of G. This paper studies the center function from the viewpoint of consensus theory. We present consensus axioms that are satisfied by the center function on all connected graphs. Next, we study classes of graphs on which the center function is characterized by such 'universal' axioms only. We present two instances: the graphs with a dominating vertex (that is, a vertex adjacent to all other vertices), and the paths. Trees in general do not fall into this category. But we show that trees with diameter at most five have such a characterization. Our approach is to highlight unexpected analogies between the center function and the median function.

• View at Publisher
• View at Scopus