Graphs with connected medians
For a nonnegative weight function \(\pi\) on vertices \(u\) of a finite connected graph \(G\), let NEWLINE\[NEWLINEF_{\pi} (x)=\sum_u \pi(u) d(u,x)NEWLINE\]NEWLINE where \(d\) denotes the distance. The median set consists of all vertices \(x\) which give a minimum of \(F_{\pi} (x)\). A local median is a vertex which gives a lower value of \(F_{\pi}(x)\) than any of its neighbors. This paper proves that the median set is connected for all \(\pi\) if and only if the median set always equals the local median set, if and only if any two vertices can be connected by a path along which \(F_{\pi}\) is peakless, as well as several other conditions. These are equivalent to a local condition which can be tested in polynomial time. These conditions are refined so that they can be applied to specific classes like the class of Helly graphs (it is proved that all Helly graphs satisfy them).
- The median function on graphs with bounded profiles
- Strongly distance-balanced graphs and graph products
- Median problem in some plane triangulations and quadrangulations.
- The median game
- Two relations for median graphs
- Median sets and median number of a graph
- Medians in median graphs and their cube complexes in linear time
- Two-ended regular median graphs
- Computing median and antimedian sets in median graphs
- A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives
- Local medians in chordal graphs
- Distance problems within Helly graphs and \(k\)-Helly graphs
- A metric space with independent median
- scientific article; zbMATH DE number 3854827 (Why is no real title available?)
- scientific article; zbMATH DE number 175723 (Why is no real title available?)
- The w‐median of a connected strongly chordal graph
- Technical note: The competitive facility location problem in a duopoly: advances beyond trees
- On graphs with prescribed median I
- On graphs with prescribed median I
- Recognizing pseudo-median graphs
- The diameter of AT‐free graphs
- Graphs with \(G^p\)-connected medians
- The median function of a block graph: axiomatic characterizations
- First-order logic axiomatization of metric graph theory
- The weight balance function on trees
- ABC(T)-graphs: an axiomatic characterization of the median procedure in graphs with connected and \(G^2\)-connected medians
- Core potentials: the consensus segmentation conjecture
- Medians in median graphs and their cube complexes in linear time
- Centrality in connected graphs via convexity or concavity
- Testing whether a subgraph is convex or isometric
- Medians in median graphs
- Axiomatic characterization of the median function of a block graph
- On the remoteness function in median graphs
This page was built for publication: Graphs with connected medians
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784516)
