Axiomatic characterization of the median and antimedian function on a complete graph minus a matching
| Autor: | Shilpa Mohandas, Henry Martyn Mulder, Divya Sindhu Lekha, Ajitha R. Subhamathi, Manoj Changat |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Median Applied Mathematics 010102 general mathematics Complete graph Astrophysics::Cosmology and Extragalactic Astrophysics 0102 computer and information sciences 01 natural sciences Graph Median function Vertex (geometry) Combinatorics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics 0101 mathematics Consensus function Axiom Mathematics |
| Zdroj: | Discrete Applied Mathematics. 228:50-59 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2016.04.013 |
| Popis: | A median (antimedian) of a profile of vertices on a graph G is a vertex that minimizes (maximizes) the sum of the distances to the elements in the profile. The median (antimedian) function has as output the set of medians (antimedians) of a profile. It is one of the basic models for the location of a desirable (obnoxious) facility in a network. The median function is well studied. For instance it has been characterized axiomatically by three simple axioms on median graphs. The median function behaves nicely on many classes of graphs. In contrast the antimedian function does not have a nice behavior on most classes. So a nice axiomatic characterization may not be expected. In this paper an axiomatic characterization is obtained for the median and antimedian function on complete graphs minus a matching. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect