If G is an undirected graph, V(G) is its vertex set and \(A\subseteq V(G)\), then a median of A is any vertex of G which has the minimal sum of distance from all vertices of A. If each subset of V(G) having three vertices has exactly one median, then G is called a median graph. The properties of median graphs are studied. The interrelation between median graphs and median semilattices is shown; a median semilattice is a meet semilattice \((X,\leq)\) such that every principle ideal \(\{\) \(x| x\leq a\}\) is a distributive lattice and any three elements have an upper bound whenever each pair of them does. At the end of the paper the concept of a local median is introduced and interrelations between medians and Condorcet vertices are described.
Recommendations
- scientific article; zbMATH DE number 4043892
- Median double graphs
- scientific article; zbMATH DE number 4204363
- Median of a graph with respect to edges
- The median procedure on median graphs
- Graphs with connected medians
- Mean graphs
- On median graphs and median grid graphs
- Median sets and median number of a graph
- scientific article; zbMATH DE number 3851138
Cites work
- Caracterisation Mediane Des Arbres
- Centers to centroids in graphs
- Discrete Ordered Sets whose Covering Graphs are Median
- scientific article; zbMATH DE number 3683305 (Why is no real title available?)
- scientific article; zbMATH DE number 3685543 (Why is no real title available?)
- scientific article; zbMATH DE number 3697163 (Why is no real title available?)
- scientific article; zbMATH DE number 3743325 (Why is no real title available?)
- scientific article; zbMATH DE number 3769710 (Why is no real title available?)
- scientific article; zbMATH DE number 3512145 (Why is no real title available?)
- scientific article; zbMATH DE number 3572228 (Why is no real title available?)
- scientific article; zbMATH DE number 3328106 (Why is no real title available?)
- Median algebras
- Median graphs and Helly hypergraphs
- Medians of arbitrary graphs
- Medians, Lattices, and Trees
- Metric Ternary Distributive Semi-Lattices
- New perspectives in competitive location theory
- Path length in the covering graph of a lattice
- The median procedure in cluster analysis and social choice theory
- Theorie De La Mediane Dans Les Treillis Distributes Finis Et Applications
Cited in
(70)- The median function on graphs with bounded profiles
- Comparing medians
- Networks with Condorcet solutions
- Distance-hereditary graphs
- Pseudo-modular graphs
- Distance center and centroid of a median graph
- A fixed cube theorem for median graphs
- On the use of ordered sets in problems of comparison and consensus of classifications
- Hereditary modular graphs
- A converse to the Sholander embedding
- Median graphs and tree analysis of dichotomous data, an approach to qualitative factor analysis
- Recognizing median graphs in subquadratic time
- Computing a median point of a simple rectilinear polygon
- A new characterization of median graphs
- Medians for weight metrics in the covering graphs of semilattices
- On the consistency of the plurality rule consensus function for molecular sequences
- The majority strategy on graphs
- Steiner intervals in graphs
- The median procedure on median graphs
- Median problem in some plane triangulations and quadrangulations.
- Arrowian characterizations of latticial federation consensus functions
- Absolute retracts of bipartite graphs
- The median procedure for n-trees
- The median function on distributive semilattices
- Medians and majorities in semimodular posets
- A multifacility location problem on median spaces
- Median sets and median number of a graph
- Understanding the generalized median stable matchings
- The median function on median graphs and semilattices
- Medians are below joins in semimodular lattices of breadth 2
- Medians in median graphs and their cube complexes in linear time
- Majority rule in the absence of a majority
- Majority judgment and strategy-proofness: a characterization
- Topes of oriented matroids and related structures
- Computing median and antimedian sets in median graphs
- Strategy-proof aggregation rules and single peakedness in bounded distributive lattices
- A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives
- Mean graphs
- Mediated digraphs and quantum nonlocality
- Local medians in chordal graphs
- Planar median graphs and cubesquare-graphs
- Nonmedian direct products of graphs with loops.
- Planar graded lattices and the \(c_1\)-median property
- scientific article; zbMATH DE number 3854827 (Why is no real title available?)
- Discrete Ordered Sets whose Covering Graphs are Median
- scientific article; zbMATH DE number 44763 (Why is no real title available?)
- scientific article; zbMATH DE number 1339499 (Why is no real title available?)
- Proximity and average eccentricity of a graph
- Condorcet winners on median spaces
- scientific article; zbMATH DE number 845614 (Why is no real title available?)
- Weakly unimodal domains, anti-exchange properties, and coalitional strategy-proofness of aggregation rules
- On condorcet and median points of simple rectilinear polygons
- Multimedian graphs and their properties
- What do trees and hypercubes have in common?
- Graph theory (algorithmic, algebraic, and metric problems)
- Graphs with \(G^p\)-connected medians
- Stable outcomes in simple cooperative games
- Core potentials: the consensus segmentation conjecture
- Medians and centres of polyominoes
- Medians in median graphs and their cube complexes in linear time
- Median graphs, parallelism and posets
- Lattice valuations, medians and majorities
- On a generalization of median graphs: k-median graphs
- On the semilattice of weak orders of a set
- From copair hypergraphs to median graphs with latent vertices
- The t-median function on graphs
- On cube-free median graphs
- Maximal proper subgraphs of median graphs
- Plural psychological developmental models: An ordinal generalization of the Guttman scale
- On the remoteness function in median graphs
This page was built for publication: Medians in median graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q791544)
