Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1009.05055
Bandelt, Hans-Jürgen; Chepoi, Victor
Graphs with connected medians.
(English)
[J] SIAM J. Discrete Math. 15, No.2, 268-282 (2002). ISSN 0895-4801; ISSN 1095-7146/e

For a nonnegative weight function $\pi$ on vertices $u$ of a finite connected graph $G$, let $$F_{\pi} (x)=\sum_u \pi(u) d(u,x)$$ 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).
[Ki Hang Kim (Montgomery)]
MSC 2000:
*05C12 Distance in graphs
90C35 Network programming

Keywords: graphs; medians; local median; majority rule; LP duality

Highlights
Master Server