Graphs with connected medians
type: Item
instance of: scholarly article
zbMATH Open document ID: 1009.05055
DOI: 10.1137/S089548019936360X
author: Hans-Jürgen Bandelt
author: Victor Chepoi
published in: SIAM Journal on Discrete Mathematics
publication date: 2002-04-23T00:00:00Z
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 1732403
zbMATH Keywords: graphs
zbMATH Keywords: medians
zbMATH Keywords: local median
zbMATH Keywords: majority rule
zbMATH Keywords: LP duality
MaRDI profile type: Publication
title: Graphs with connected medians
review text: 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).
reviewed by: Ki Hang Kim
description: scientific article; zbMATH DE number 1732403