Axiomatic Characterization of the Median and Antimedian Functions on Cocktail-Party Graphs and Complete Graphs

Autor:	Divya Sindhu Lekha, Manoj Changat, Ajitha R. Subhamathi, Henry Martyn Mulder
Rok vydání:	2015
Předmět:	Discrete mathematics Combinatorics Median Complete graph Cocktail party Consensus function Axiom Median function Graph Vertex (geometry) Mathematics
Zdroj:	Algorithms and Discrete Applied Mathematics ISBN: 9783319149738 CALDAM
DOI:	10.1007/978-3-319-14974-5_14
Popis:	A median (antimedian) of a profile of vertices on a graph G is a vertex that minimizes (maximizes) the remoteness value, that is, the sum of the distances to the elements in the profile. The median (or 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 (or 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 functions on cocktail-party graphs. In addition a characterization of the antimedian function on complete graphs is presented.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8d8a787932689c6d0a540cd50ff1f5e4 https://doi.org/10.1007/978-3-319-14974-5_14 Zobrazit plný text záznamu