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 0888.05025
Mulder, Henry Martyn
The majority strategy on graphs.
(English)
[J] Discrete Appl. Math. 80, No.1, 97-105 (1997). ISSN 0166-218X

An interval $I(u,v)$ in a graph $G$, where $u$, $v$ are vertices, is the set of all vertices $w$ of $G$ for which the equality $d(u, w)+ d(w,v)= d(u,v)$ holds, where $d$ denotes the distance. If for any three vertices $u$, $v$, $w$ of $G$ the intersection $I(u,v)\cap I(v, w)\cap I(w,u)$ consists of one vertex only, then $G$ is called a median graph. A profile of length $p$ on a graph $G$ is a finite sequence $v_1,v_2,\dots, v_p$ of vertices of $G$; its median is a vertex $x$ of $G$ for which $\sum^p_{i=1} d(x, v_i)$ is minimal. The set of all medians of a profile $\pi$ is the median set $M(\pi)$. In the paper a strategy for finding $M(\pi)$ for a given profile $\pi$ is described; it is called the majority strategy. It begins in a vertex of $G$ and consists of certain successive moves from one vertex to another along an edge. It is proved that the majority strategy produces the median set $M(\pi)$ for each profile $\pi$ of $G$, independently of the initial position, if and only if $G$ is a median graph.
MSC 2000:
*05C12 Distance in graphs
05C75 Structural characterization of types of graphs
05C99 Graph theory
90B80 Discrete location and assignment

Keywords: interval; median graph; profile; median set; majority strategy

Cited in: Zbl 1196.05024

Highlights
Master Server